Permutation Generation Methods [pdf]

bArray · on Aug 23, 2022

A related interesting problem is superpermutations [1]. This is the same problem that an anonymous 4chan poster helped bring some light to lower bounds on shortest superpatterns [2]. The Google group is worth a shout for their efforts [3].

Surprisingly, we only have optimal superpermutations for really low values on N [4].

I tried my hand at auto-generating symmetric patterns (which turn out to not be optimal after some value of N (6?)), but the problem is quite tough. Currently the best approaches appear to be achieved by using a TSP solver.

[1] https://www.gregegan.net/SCIENCE/Superpermutations/Superperm...

[2] https://oeis.org/A180632/a180632.pdf

[3] https://groups.google.com/g/superpermutators

[4] https://github.com/superpermutators/superperm/tree/master/su...

WorkerBee28474 · on Aug 23, 2022

Wow, I never thought I would ever see "Anonymous 4chan Poster" credited as the co-author of a paper.

I guess it makes sense as an implication of the idea that "On the Internet, nobody knows you're a dog." [0]

[0] http://www.paulgraham.com/hiring.html

llimllib · on Aug 23, 2022

I only looked very briefly, but Knuth's fascicle 2b covers similar material. You can read a draft version here: https://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz (or purchase the real one, obviously)

I was surprised when I went to implement some of them a decade ago that it's actually very readable, if Knuth's reputation scares you.

I made visualizations of a few of them way back then: https://billmill.org/permvis.html

lkuty · on Aug 23, 2022

Reminds of the french article by Laisant published in 1888 about the factorial number system (factoradic) and its application to permutations. http://www.numdam.org/item/?id=BSMF_1888__16__176_0

I also found an article by James McCaffrey named "Using Permutations in .NET for Improved Systems Security" but I can't find it again.

I used them a few years ago to enumarate all possible permutations to find the best solution to a small sample of TSP and compare it to the approximate solution found by an algorithm.

EDIT: looks like my source was just https://en.wikipedia.org/wiki/Factorial_number_system

qsort · on Aug 23, 2022

Interestingly, this is basically what CPython does to implement its native permutations function. The C source is, as always, extremely easy to understand: https://github.com/python/cpython/blob/main/Modules/itertool...

082349872349872 · on Aug 23, 2022

nice find in Numdam; chouette !

IIRC Iverson presents the isomorphism between factoradic ([R]adix) and indexed ([D]irect) permutation representations in his Turing Award Lecture[0] (p456, via a pair of APL functions):

    DFR:ω[1],X+ω[1]≤X←DFR 1↓ω:O=pω:ω
    RFD:ω[1],RFD X-ω[1]≤X←1↓ω:O=pω:ω

[0] https://dl.acm.org/ft_gateway.cfm?id=1283935&type=pdf

nayuki · on Aug 23, 2022

My preferred method:

    int[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    do {
        print(array);
    } while (nextPermutation(array));

https://www.nayuki.io/page/next-lexicographical-permutation-...

This even works with duplicate values.

fjfaase · on Aug 23, 2022

For a C++ implementation see the iterator class Permutations in https://iwriteiam.nl/FSwNcolour_cpp.txt

ur-whale · on Aug 23, 2022

Article is a scan so can't be searched.

Any mention of symmetric crypto in there?

After all, permutation generation is what a sizable chunk symmetric crypto is about.

[edit]: and now that I've skimmed through the paper, I see it is not really about permutation generation but rather permutation enumeration, so symmetric crypto is out.