An algorithm for enumerating all permutations of the numbers {1,2,...,n} using an stack

Question

An algorithm to generate all permutations of the numbers through recursion,, I realized that the algorithm would be pretty complex without recursion.

Recursive method call internally uses stack for placing the previous call. You can try to implement the same with iterative approach. — YoungHobbit, Sep 07 '15 at 17:14
Check out the answers to this question, especially Filip Nguyen's: http://stackoverflow.com/questions/2799078/permutation-algorithm-without-recursion-java — m69's been on strike for years, Sep 08 '15 at 03:04

score 2 · Answer 1 · answered Sep 07 '15 at 19:50

2

I guess I have yet to tire of this question. Try to think about coding the following idea:

Add to the stack a call with each number in every space of each previous stack call.
As in,

  {}
  {1}
  {2,1} {1,2}
  {3,2,1} {2,3,1} {2,1,3} {3,1,2} {1,3,2} {1,2,3}
  ...etc.

answered Sep 07 '15 at 19:50

גלעד ברקן

23,602
3
25
61

I may have confused stack with queue here; adding the sets to the beginning of the queue makes more sense as they get larger and the smaller ones get popped off. – גלעד ברקן Dec 13 '15 at 09:30

score 1 · Answer 2 · edited Sep 07 '15 at 22:01

1

The code below returns the total number of possible combinations

if($n != 1){    
    $record = 1;
    for($i=2;$i<=$n;$i++){
        $record = $record * $i;
    }
    return $record;
}else{
    return 1;
}

edited Sep 07 '15 at 22:01

hex494D49

9,109
3
38
47

answered Sep 07 '15 at 17:43

xpeiro

733
5
21

1

What is that supposed to do? – poke Sep 07 '15 at 18:19
returns the total number of possible combinations – xpeiro Sep 07 '15 at 19:52
OP wants to *enumerate* the *permutations*. – poke Sep 08 '15 at 06:40
Ouch! Sorry! I did not realize it. – xpeiro Sep 08 '15 at 08:57

score 1 · Accepted Answer · answered Sep 12 '15 at 10:07

Considering that the function already have access to character array input (if you are using java) or string input if the language you are using allows you to edit the characters in string. Its less efficient than Heap algorithm but more simple and easy to understand

  void permutate(int i){
  //starts  
      //  n is the size of input.
     n = input.size
    if(i==n){
        print(input);

    }
    else {
        for(int j=i; j<n; j++){

            swap( input[i] , input[j] );
            permutate( i+1 );
            swap( input[i] , input[j]);

        }
    }
    //end
}

score 0 · Answer 4 · answered Feb 22 '19 at 21:31

Basically, you need to feel there stack up with the n numbers starting from 0. then pop them all to get your first permutation. to get the second possible permutation you need to do the same thing but this time start from 1 to n and your last item will be the one at position 0. you need to do it all the way to the n. and then you have to do it the other way around, starting from n to 0 and then n-1 to 0 with the last item being n.

To illustrate what I mean by this lets consider the set of 3 integers {1,2,3}.

I will use ( ) to show stack and { } to show the resulting permutation after poping all the elemets of the stack.

(1|2|3) pop {3,2,1}

(2|3|1) pop {1,3,2}

(3|1|2) pop {2,1,3}

now the other way around

(3|2|1) pop {1,2,3}

(2|1|3) pop {3,1,2}

(1|3|2) pop {2,3,1}

What about 4 integers, doing this way, I am only getting 8 but 4! is 24 — SHAH MD IMRAN HOSSAIN, Jan 17 '23 at 17:34

score 0 · Answer 5 · answered Jun 02 '21 at 21:33

Another solution is to empty a stack and fill it back up starting from an index in the emptied contents.

iteration	stack	permutation	fill from index
1	abc	cba	0
2	cba	abc	1
3	bca	acb	2
4	bac	cab	0
5	cab	bac	1
6	acb	bca	2

Each stack is filled by the previous permutation, starting from an incrementing index. The letter that it is filling from is bolded. Notice how the stack following that permutation is filled starting from that letter.

Here is an example from the second iteration

abc -> bca

Another thing to note is that the amount of permutations is n! abc is length of 3, meaning the stack will be filled and emptied 3x2x1 = 6 times before repeating the original stack.

An algorithm for enumerating all permutations of the numbers {1,2,...,n} using an stack

5 Answers5