Permutation algorithm using an explicit stack

Asked Jan 06 '15 at 19:35

Active Jan 06 '15 at 20:11

Viewed 917 times

I was reading the chapter of stack in my book and there is this question in the exercise :

Describe a nonrecursive algorithm for enumerating all permutations of the
numbers {1, 2, . . . , n} using an explicit stack.

Understanding and implementing the recursive algorithm was easy. But I am not getting how to implement it with an explicit stack. What would be a possible solution for this? If you think that the hints would be self sufficient to solve this, please provide them only so that I can give it one more try!!

edited Jan 06 '15 at 20:00

mbomb007

3,788
3
39
68

asked Jan 06 '15 at 19:35

thisisashwani

1,748
2
18
25

Basically, you need to find an iterative method of doing this (using `for` loops, for example). – mbomb007 Jan 06 '15 at 19:44
Also, what do you mean by explicit stack? – mbomb007 Jan 06 '15 at 19:53
By explicit stack, I mean a stack defined by the user, instead of an implicit one that the program uses in case of recursion. – thisisashwani Jan 06 '15 at 20:00
What operations would be allowed on the stack? Python doesn't appear to have a `swap()` operation, just `append()` and `pop()`. – mbomb007 Jan 06 '15 at 20:19
@mbomb007 there is no such restriction that you can't build another definition as per your need. – thisisashwani Jan 07 '15 at 09:57
Not sure if this question is a duplicate of this: http://stackoverflow.com/questions/6479779/generate-permutation-using-a-single-stack – mbomb007 Jan 07 '15 at 14:34

Permutation algorithm using an explicit stack

0 Answers0