3 ms·

Permutation Generation Methods [pdf]

66 points by qsort 4y ago

ur-whale 4y ago
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.
bArray 4y ago
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/Superpermutations.html https://www.gregegan.net/SCIENCE/Superpermutations/Superperm... [2] https://oeis.org/A180632/a180632.pdf https://oeis.org/A180632/a180632.pdf [3] https://groups.google.com/g/superpermutators https://groups.google.com/g/superpermutators [4] https://github.com/superpermutators/superperm/tree/master/superpermutations https://github.com/superpermutators/superperm/tree/master/su...
- WorkerBee28474 4y ago
  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 http://www.paulgraham.com/hiring.html
lkuty 4y ago
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 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 https://en.wikipedia.org/wiki/Factorial_number_system
- qsort 4y ago
  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/itertoolsmodule.c#L3356 https://github.com/python/cpython/blob/main/Modules/itertool...
  - 082349872349872 4y ago
    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 https://dl.acm.org/ft_gateway.cfm?id=1283935&type=pdf
nayuki 4y ago
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-algorithm https://www.nayuki.io/page/next-lexicographical-permutation-... This even works with duplicate values.
- fjfaase 4y ago
  For a C++ implementation see the iterator class Permutations in https://iwriteiam.nl/FSwNcolour_cpp.txt https://iwriteiam.nl/FSwNcolour_cpp.txt
llimllib 4y ago
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 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 https://billmill.org/permvis.html

66 points by qsort 4y ago

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.

bArray 4y ago

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/Superpermutations.html https://www.gregegan.net/SCIENCE/Superpermutations/Superperm... [2] https://oeis.org/A180632/a180632.pdf https://oeis.org/A180632/a180632.pdf [3] https://groups.google.com/g/superpermutators https://groups.google.com/g/superpermutators [4] https://github.com/superpermutators/superperm/tree/master/superpermutations https://github.com/superpermutators/superperm/tree/master/su...

WorkerBee28474 4y ago
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 http://www.paulgraham.com/hiring.html

lkuty 4y ago

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 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 https://en.wikipedia.org/wiki/Factorial_number_system

qsort 4y ago
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/itertoolsmodule.c#L3356 https://github.com/python/cpython/blob/main/Modules/itertool...
- 082349872349872 4y ago
  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 https://dl.acm.org/ft_gateway.cfm?id=1283935&type=pdf

nayuki 4y ago

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-algorithm https://www.nayuki.io/page/next-lexicographical-permutation-... This even works with duplicate values.

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

llimllib 4y ago

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 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 https://billmill.org/permvis.html