我通常在Python中使用以下递归算法:
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?
推荐答案这是取消递归"递归函数的一种通用方法:假设我们具有以下递归函数:
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在您的情况下,堆栈包含一个由数组和一个int组成的对.初始值为输入中的数组,并且int m = 0.操作看起来像这样
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祝你好运!
更多推荐
使用重复元素进行全置换的非递归算法?
发布评论