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

兹隆

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

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

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

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

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

丹·盖兹

基本上,在任何可以从 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]

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

生成长度为N的所有数字排列

从给定的单词列表中生成长度为“ N”的所有可能组合(寻找不重复)

kdb / q:生成长度为N的所有可能的“字符串”

仅生成长度为n且最大k个连续零的二进制字符串

如何从带有条件的字母表中生成长度为N的所有单词

如何在Prolog中使用DCG生成长度为n-1的所有二进制字符串的语言

在O(n log n)时间生成具有n个长度和k个反转数的数组的算法?

查找长度为k的向量的所有非等价排列,并取n个可能值

如何生成长度为n的Java中的SecureRandom的字符串?

通过步骤m生成长度为n的可迭代滑动窗口

生成所有长度为n的True / False排列?

生成长度为6的字母和数字的所有可能组合时出现MemoryError

在C ++中生成N选择K排列

从C中的n生成k个排列

散列函数具有定义其输出生成长度的能力

如何在Postgres 9.6+中生成长度为N的随机,唯一的字母数字ID?

从n返回k个元素的所有组合的算法

Python:找到所有长度为k的回文序列,总和为n

使用所有可能的顺序创建最大长度 K 的 N 个列表

生成具有所有唯一k位子序列的所有n位序列。

从n个长度为k的数中生成递增的子序列

如何生成长度为 N 的随机二进制数 0 或 1,并可以选择控制出现 0 或 1 的概率?

生成n个项的k元组的算法,以便每个项至少被使用一次(k> n)

生成列表a(n)的形式不是素数+ a(k),k <n

递归生成char数组中所有字符(长度为k)的组合的字符串数组

生成所有可能的n维k * k * ... * k数组,每个数组沿轴均带有一线

生成所有n个字母的排列

快速算法以生成常规数

一种方法生成长度为30的数组,使用JS在两个日期之间具有随机时间?