-1

Is there any algorithm to generate all permutations of the integers 1 to n [ Hint: The set of permutations of the integers 1 to n can be obtained from the set of permutations of the integers 1 to n-1 by inserting n in each possible positions of each permutation ]

flag
have you checked en.wikipedia.org/wiki/… also, googoling en.wikipedia.org/wiki/Wikipedia:Reference_desk/… gives plenty of results. In particular, nice explanations in the archives of the wiki Ref Desk (plug "generating permutations") en.wikipedia.org/wiki/Wikipedia:Reference_desk/… – Pietro Majer Sep 6 2010 at 9:03
1 
 The phrase "That hint they only provided" makes this question sound like this is some kind of exercise or homework assignment. Is this the case? – Yemon Choi Sep 6 2010 at 9:18
1 
 The section "Systematic generation of all permutations" in the Wikipedia article on permutations gives a complete step-by-step algorithm. I doubt anyone here will give a more detailed answer than that (and if you want an actual computer program, you should ask elsewhere). I'm voting to close. – Sergei Ivanov Sep 6 2010 at 9:23
5 
 This question is not appropriate for MO. You are asking us to solve a basic programming exercise. – Andrej Bauer Sep 6 2010 at 9:24
2 
 MathOverflow is not for homework help. Please read mathoverflow.net/faq#whatnot. – Tsuyoshi Ito Sep 6 2010 at 10:56
show 1 more comment

closed as off topic by Sergei Ivanov, Victor Protsak, Andrew Stacey, Charles Matthews, José Figueroa-O'Farrill Sep 6 2010 at 11:09

2 Answers

4

Knuth's The Art of Computer Programming, Volume 4, Fascicle 2: Generating all Tuples and Permutations gives efficient (non-recursive) solutions to this and many other combinatorial enumeration problems.

Section 7.2.1.2 contains 36 pages of material devoted to precisely the question you ask.

link|flag
@AVS: This is off-topic, but what became of the model behind you on your site? – Eric Tressler Sep 6 2010 at 9:35
@Eric Tressler: 'twas but an ephemeral shadow of the 4-dimensional object we were chasing, and such things are not meant to last. But I trust that its components have since been used to build even bigger and better things. – AVS Sep 6 2010 at 10:10
1

Hint: If you understand recursion, you just answered your own question. You may also want to look at the C++ implementation of next_permutation in the STL. I was going to explain it, but http://wordaligned.org/articles/next-permutation does a fantastic job.

link|flag

Not the answer you're looking for? Browse other questions tagged or ask your own question.