Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 ]

share|improve this question

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

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

    
have you checked en.wikipedia.org/wiki/… also, googoling en.wikipedia.org/wiki/Wikipedia:Reference_desk/Mathematics 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/Mathematics –  Pietro Majer Sep 6 '10 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 '10 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 '10 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 '10 at 9:24
2  
MathOverflow is not for homework help. Please read mathoverflow.net/faq#whatnot. –  Tsuyoshi Ito Sep 6 '10 at 10:56
show 1 more comment

2 Answers 2

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.

share|improve this answer
    
@AVS: This is off-topic, but what became of the model behind you on your site? –  Eric Tressler Sep 6 '10 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 '10 at 10:10
add comment

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.

share|improve this answer
add comment

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