**jm + permutation**
4

Sci-Fi Writer Greg Egan and 4chan anon Math Whiz Advance Permutation Problem | Quanta Magazine

mathematics
internet
math
greg-egan
anime
bizarre
4chan
superpermutation
permutation
proofs

4 weeks ago by jm

On September 16, 2011, an anime fan posted a math question to the online bulletin board 4chan about the cult classic television series 'The Melancholy of Haruhi Suzumiya'. Season one of the show, which involves time travel, had originally aired in non-chronological order, and a re-broadcast and a DVD version had each further rearranged the episodes. Fans were arguing online about the best order to watch the episodes, and the 4chan poster wondered: If viewers wanted to see the series in every possible order, what is the shortest list of episodes they’d have to watch?

In less than an hour, an anonymous person offered an answer — not a complete solution, but a lower bound on the number of episodes required. The argument, which covered series with any number of episodes, showed that for the 14-episode first season of Haruhi, viewers would have to watch at least 93,884,313,611 episodes to see all possible orderings. “Please look over [the proof] for any loopholes I might have missed,” the anonymous poster wrote.

The proof slipped under the radar of the mathematics community for seven years — apparently only one professional mathematician spotted it at the time, and he didn’t check it carefully. But in a plot twist last month, the Australian science fiction novelist Greg Egan proved a new upper bound on the number of episodes required. Egan’s discovery renewed interest in the problem and drew attention to the lower bound posted anonymously in 2011. Both proofs are now being hailed as significant advances on a puzzle mathematicians have been studying for at least 25 years.

4 weeks ago by jm

Sattolo's algorithm

august 2017 by jm

produces a randomized permutation of a list, with exactly one cycle (which guarantees that we will reach every element of the list even though we’re traversing it in random order)

algorithms
lists
permutation
random
randomization
cycles
august 2017 by jm

algorithm - Generating shuffled range using a PRNG rather than shuffling - Stack Overflow

december 2011 by jm

some reasonably good answers on using an LFSR or LCG to generate a full-cycle permutation with no repeats

lfsr
lcg
algorithms
permutation
shuffling
december 2011 by jm

Using a Feistel Network for full-cycle permutation

december 2011 by jm

nice algorithm. requires that the permuted set's size be a power of 2 however - although for smaller sets you can just skip to the next output value, since they're not going to repeat

feistel-network
full-cycle
permutation
shuffling
algorithms
december 2011 by jm

Copy this bookmark: