算法从n返回k个元素的所有组合
我想写一个函数，它将一个字母数组作为参数和一些要选择的字母。
假设您提供了8个字母的数组，并且希望从中选择3个字母。 那么你应该得到：
8! / ((8 - 3)! * 3!) = 56
数组（或单词）由3个字母组成。
计算机编程艺术第4卷：Fascicle 3有很多这些可能比我描述的更适合您的特殊情况。
灰色代码
一个你会遇到的问题当然是记忆，而且很快，你的设置中会有20个元素出现问题 - 20C3 = 1140。如果你想遍历该集合，最好使用修改的灰色代码算法所以你并没有把它们都放在记忆里。 这些从上一个产生下一个组合并避免重复。 有许多这些用于不同的用途。 我们想要最大化连续组合之间的差异吗？ 最小化？ 等等。
一些描述灰色代码的原始论文：
以下是一些其他论文，涉及该主题：
Chase的Twiddle（算法）
Phillip J Chase，“Algorithm 382：M of N of N Objects的组合”（1970）
算法在C ...
字典顺序中的组合索引（扣扣算法515）
您也可以通过其索引（按字典顺序）参考组合。 意识到索引应该是基于索引从右到左的一些变化，我们可以构建一些应该恢复组合的东西。
所以，我们有一组{1,2,3,4,5,6} ...并且我们需要三个元素。 假设{1,2,3}我们可以说元素之间的差异是一个，并且是最小的。 {1,2,4}有一个变化，并且按照字典顺序排列编号2.因此，最后一个位置的“变化”数量在辞典排序中占一个变化。 第二个变化{1,3,4}有一个变化，但由于它在第二位（与原始组中元素的数量成比例），所以变化更大。
我所描述的方法是一种解构，就像从设置到索引那样，我们需要做相反的处理 - 这更加棘手。 这就是扣扣解决问题的方法。 我写了一些C来计算它们，只做了很小的修改 - 我用集合的索引而不是数字范围来表示集合，所以我们总是从0 ... n开始工作。 注意：
字典顺序中的组合索引（McCaffrey）
还有另外一种方法：它的概念更易于掌握和编程，但它没有Buckles的优化。 幸运的是，它也不会产生重复的组合：
集合 最大化 ，在哪里 。
例如： 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1) 。 所以，第二十七个词汇组合是：{1,2,5,6}，这些是你想要看的任何集合的索引。 下面的例子（OCaml），需要choose功能，留给读者：
(* this will find the [x] combination of a [set] list when taking [k] elements *)
let combination_maccaffery set k x =
(* maximize function -- maximize a that is aCb *)
(* return largest c where c < i and choose(c,i) <= z *)
let rec maximize a b x =
if (choose a b ) <= x then a else maximize (a-1) b x
in
let rec iterate n x i = match i with
| 0 -> []
| i ->
let max = maximize n i x in
max :: iterate n (x - (choose max i)) (i-1)
in
if x < 0 then failwith "errors" else
let idxs = iterate (List.length set) x k in
List.map (List.nth set) (List.sort (-) idxs)
在C＃中：
public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
return k == 0 ? new[] { new T[0] } :
elements.SelectMany((e, i) =>
elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}
用法：
var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);
结果：
123
124
125
134
135
145
234
235
245
345
我可以提出我的递归Python解决方案来解决这个问题吗？
def choose_iter(elements, length):
for i in xrange(len(elements)):
if length == 1:
yield (elements[i],)
else:
for next in choose_iter(elements[i+1:len(elements)], length-1):
yield (elements[i],) + next
def choose(l, k):
return list(choose_iter(l, k))
用法示例：
>>> len(list(choose_iter("abcdefgh",3)))
56
我喜欢它的简单性。
链接地址: http://www.djcxy.com/p/84557.html上一篇: Algorithm to return all combinations of k elements from n