algorithm - 是否可以仅使用迭代器输出 1,...,n 的排列？

Question

这里有几个伪代码示例来说明我的意思。

这会产生 1,...,n 的组合(选择不考虑顺序，不重复)一次取 3 个。

Do[Print[i,j,k], {i,1...n-2}, {j,i+1...n-1}, {k,j+1...n}]

循环从左到右运行——对于每个 i，迭代器 j 将遍历它的值，对于每个 j，迭代器 k 将遍历它的值。通过添加更多变量并更改 n，我们可以概括上面的内容。

问题:我们可以对排列做同样的事情吗？换句话说，我们能否找到一种方法来调整迭代器以产生 P(n,k)=n!/(p-k)! 1,...,n 的排列？对于 k=3，

Do[Print[i,j,k], {i, f_1 , g_1(i,n)}, {j, f_2(i), g_2(i,j,n)}, {k, f_3(i,j), g_3(i,j,k,n)}]

仅使用基本的算术运算和模块化算术、floor/ceiling fcns 等东西。

因为这对您来说可能听起来像是家庭作业问题，所以我会选择"is"或“否”的答案；您对难度级别的估计对我也有帮助。

谢谢。

Answer 1

你的意思是迭代生成排列，而不是递归？是的，这是可能的:

http://en.wikipedia.org/wiki/Permutation

请参阅“生成排列的算法”部分

1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
3. Swap a[k] with a[l].
4. Reverse the sequence from a[k + 1] up to and including the final element a[n].

这遵循您只能使用基本算术运算的限制(如果您不喜欢交换，请知道您可以使用加法和减法交换两个数字)。