含重复元素的全排列非递归算法？

Question

我通常在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]

这个方法挺不错的。

不过我希望能找到一个方便的、不用递归的算法，来处理带有重复元素的全排列。

Answer 1

这里有一种通用的方法可以把递归函数变成非递归的方式：假设我们有一个这样的递归函数：

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

要把它变成非递归的，你可以使用一个栈，像这样：

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

在你的例子中，这个栈里包含了一对东西，一个是数组，另一个是一个整数。初始值是输入的数组和整数 m=0。操作可能看起来像这样：

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

祝你好运！