一种使用堆栈枚举数字 {1,2,...,n} 的所有排列的算法

Question

一种通过递归生成数字所有排列的算法，我意识到如果没有递归，该算法会非常复杂。

Answer 1

下面的代码returns可能的组合总数

if($n != 1){    
    $record = 1;
    for($i=2;$i<=$n;$i++){
        $record = $record * $i;
    }
    return $record;
}else{
    return 1;
}

Answer 2

我想我还没有厌倦这个问题。尝试考虑编码以下想法：

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.

Answer 3

考虑到该函数已经可以访问字符数组输入（如果您正在使用 java）或字符串输入，如果您使用的语言允许您编辑字符串中的字符。效率低于Heap算法，但更简单易懂

  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
}

Answer 4

基本上，您需要感觉从 0 开始的 n 个数字堆叠起来。然后将它们全部弹出以获得您的第一个排列。要得到第二个可能的排列，你需要做同样的事情，但这次从 1 到 n，你的最后一项将是位置 0 的那个。你需要一直这样做到 n。然后你必须反过来做，从 n 到 0 然后 n-1 到 0 最后一项是 n.

为了说明我的意思，让我们考虑 3 个整数 {1,2,3} 的集合。

我将使用 ( ) 显示堆栈，并使用 { } 显示弹出堆栈的所有元素后生成的排列。

(1|2|3) 弹出 {3,2,1}

(2|3|1) 弹出 {1,3,2}

(3|1|2) 弹出 {2,1,3}

现在反过来

(3|2|1) 弹出 {1,2,3}

(2|1|3) 弹出 {3,1,2}

(1|3|2) 弹出 {2,3,1}

Answer 5

另一种解决方案是清空堆栈，然后从清空内容中的索引开始将其填满。

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

每个堆栈都由前一个排列填充，从递增索引开始。它所填充的字母以粗体显示。请注意该排列后的堆栈是如何从该字母开始填充的。

这是第二次迭代的例子

abc -> bca

另外需要注意的是，排列的数量是n！ abc 的长度为 3，这意味着堆栈将被填充和清空 3x2x1 = 6 次，然后重复原始堆栈。

一种使用堆栈枚举数字 {1,2,...,n} 的所有排列的算法

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

algorithm

permutation

data-structures