Timeline for Generating All Permutations Without Repetition Using Two Generators
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 17, 2012 at 14:34 | comment | added | Ng Yong Hao | @Benjamin: My apologies for my ignorance, but I am not sure if I understood what you wrote. Please correct me if I am wrong: Do you mean that each of the $n$ cell holds 1 alphabet and hence it is possible that the generation requires enumeration of up to $2^n$ words? | |
| Jun 17, 2012 at 3:04 | comment | added | Benjamin Steinberg | Linear space is not as nice as it sounds. For instance in n cells with a 2 letter alphabet you can write successively all 2^n words. | |
| Jun 16, 2012 at 20:51 | comment | added | Ng Yong Hao | I would like to also add that by searching for related papers, I found "A Survery of Combinatorial Gray Codes", where on page 13 the authors commented that the algorithm by R.C. Compton and S.G. Williamson is rather complex. So unfortunately it appears that this cannot be used for practical purposes. | |
| Jun 16, 2012 at 20:27 | comment | added | Ng Yong Hao | This is exactly what I was looking for! Thank you. I wanted to try this for "recreation" but I was worried that it may turn out to be a very difficult problem. I can see the first part of the paper which quotes: "The existence of such a code seems to be a very nontrivial problem" so the authors seem to agree. Nevertheless it is still nice to know that such a nice result exists. | |
| Jun 16, 2012 at 20:13 | vote | accept | Ng Yong Hao | ||
| Jun 16, 2012 at 19:56 | history | answered | John Wiltshire-Gordon | CC BY-SA 3.0 |