Non-recursive algorithm for full permutation with repetitive elements?

Question

I usually use the recursive algorithm as follows in Python:

def permutate(array, t, n):             

    if t == n:
       for i in range(n):
            print array[i]

       return

   for j in range(t,n):
      flag = 1
      for r in range(t,j):
          if array[r] == array[j]:
              flag = 0
              break

      if flag == 0:
          continue
      else:
          array[j],array[t] = array[t],array[j]
          permutate(array,t+1,n)
          array[j],array[t] = array[t],array[j]

This one is neat. But I hope to find a convenient, non-recursive algorithm to do full permutation with repetitive elements?

You could always do a `while(notDone)` loop ;) Though this requires figuring out when you're actually done.. Recursion is definitely the best way to do this, so if it's academic, you should head over to http://programmers.stackexchange.com/ — Christopher Wirt, Jul 09 '14 at 23:30
http://stackoverflow.com/questions/18227931/iterative-solution-for-finding-string-permutations ? — גלעד ברקן, Jul 10 '14 at 00:28
Does "with repetitive elements" means that if you array is (1, 1, 3), the permutation (1, 3, 1) is counted twice ? — Brainless, Jul 10 '14 at 03:05
@Brainless No, it's only counted once. Otherwise the algorithm would be the same as permutating an array with no repetitive elements. — Biu, Jul 10 '14 at 03:46

Brainless · Accepted Answer · 2014-07-10T04:27:57.750

Here is a generic way to "un-recursify" a recursive function : Let's say we have the following recursive function :

RecFunc (parameters)
    ...
    ...
    var x = RecFunc (other parameters)
    ...
    ...
EndFunc

To "un-recursify" it, you can use a stack like this :

NonRecFunc (parameters)
    stack MyStack;
    MyStack.push (InitialValue);
    While (MyStack is non empty)
       var S = MyStack.pop;
       # begin operations with S
       ....
       # results are x_1, ..., x_n
       for x_i = x_1 to x_n
           MyStack.push (x_i);
       endfor
   endWhile
EndFunc

In your case, the stack contains a pair consisting of an array and an int. The initial value is the array in input and the int m=0. The operations could look like this

for i = m to n
    for j = i+1 to n
       if array[i] == array[j]
           continue
       endif
       array_c = copy of array
       permute entries i and j in array_c
       push (array_c, m+1) in the stack
    endfor
endfor

Good luck !

Non-recursive algorithm for full permutation with repetitive elements?

1 Answers1

Linked