从 N 生成长度为 K 的所有无序排列的快速算法

Question

我有大小为 N 的数组，我需要从该数组生成所有大小为 K 的排列变体。变体 [1 2 3] 和 [3 1 2] 是不同的。我发现的标准解决方案是

1) 只是排列，在这里我获得了与数组相同大小的所有重新排序。

2) 只是组合，我从大小为 N 的数组中获得大小为 K 的所有组合，但是对于这些算法 [1 2 6] 和 [6 1 2] 是相同的，而我需要它们不同.

你能帮我找到一个有效的解决方案吗？

我应该在 Matlab 上实现它，但我希望我能够从其他语言翻译您的解决方案。

Answer 1

基本上，在任何可以从 1:N 生成所有大小为 K 的无序子集并且可以生成 1:K 的所有排列的任何语言中，获取所有有序子集就像迭代一样简单子集并使用每个 K 排列对它们进行排列。

在 Julia 语言中：

using Combinatorics, Iterators, Base.Iterators

N = 4
K = 2

collect(flatten(permutations(subset) for subset in subsets(1:N,K)))

给出：

12-element Array{Array{Int64,1},1}:
 [1, 2]
 [2, 1]
 [1, 3]
 [3, 1]
 [1, 4]
 [4, 1]
 [2, 3]
 [3, 2]
 [2, 4]
 [4, 2]
 [3, 4]
 [4, 3]

Answer 2

合并您找到的两个解决方案。这是 python 代码：

allPermutations = list()
combinations=getCombinations(arr, K)
for comb in combinations:
    allPermutations.extend(getPermutations(comb))

1.arr 是输入数组。

2.getCombinations 是一个 returns 大小为 K 的 arr 中所有组合列表的函数。

3.getPermutations returns 作为输入给出的数组的所有排列。

Fast algorithm to generate all nonordered permutations of lenght K from N