CODEWITHSUNDEEP
algorithmdata-structurespermutation
ibadia
ibadia

Reputation: 919

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

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

Upvotes: 3

Views: 3924

Answers (5)

Andrey Karmanov
Andrey Karmanov

Reputation: 11

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.

Upvotes: 0

Pedram
Pedram

Reputation: 53

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}

Upvotes: 0

ibadia
ibadia

Reputation: 919

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
}

Upvotes: 1

xpeiro
xpeiro

Reputation: 760

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;
}

Upvotes: 1

גלעד ברקן
גלעד ברקן

Reputation: 23945

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.

Upvotes: 2

Related Questions