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

Question

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

我想写一个函数，它将一个字母数组作为参数，并选择一些字母。

假设您提供了8个字母的数组，并希望从中选择3个字母。然后你应该得到：

8! / ((8 - 3)! * 3!) = 56

数组（或单词）返回，每个包含3个字母。

Answer 1

计算机编程艺术第4卷：分册3有很多这些可能比我描述的更适合你的特殊情况。格雷码你会遇到的一个问题当然是记忆而且非常快，你的组中有20个元素会出现问题 -&nbsp;20&nbsp;C&nbsp;3&nbsp;= 1140.如果你想迭代这个集合，最好使用修改后的灰色代码算法，所以你没有把所有这些都保存在内存中。这些产生了前一个的下一个组合，避免重复。其中有许多用于不同的用途。我们是否希望最大化连续组合之间的差异？最小化？等等。一些描述格雷码的原始论文：一些Hamilton路径和一个最小变换算法相邻交换组合生成算法以下是一些涉及该主题的其他文章：Eades，Hickey，读取相邻交换组合生成算法的有效实现（PDF，代码为Pascal）组合发电机组合灰度代码调查（PostScript）一种格雷码算法Chase's Twiddle（算法）Phillip J Chase，“&nbsp;算法382：N个物体中M的组合&nbsp;”（1970）C中的算法&nbsp;...字典顺序中的组合索引（带扣算法515）您还可以通过其索引（按字典顺序）引用组合。根据索引意识到索引应该是从右到左的一些变化，我们可以构造一些应该恢复组合的东西。所以，我们有一套{1,2,3,4,5,6} ......我们需要三个元素。让我们说{1,2,3}我们可以说元素之间的差异是一个，有序和最小。{1,2,4}有一个变化，按字典顺序排列第2位。因此，最后一个地方的“变化”数量占字典顺序的一个变化。第二个位置，只有一个变化{1,3,4}有一个变化，但由于它位于第二位（与原始集合中的元素数量成比例），因此会有更多变化。我所描述的方法是解构，似乎从设置到索引，我们需要反向 - 这更加棘手。这就是Buckles如何解决这个问题。我写了一些C来计算它们，只需稍作修改 - 我使用集合的索引而不是数字范围来表示集合，所以我们总是从0 ... n开始工作。注意：由于组合是无序的，{1,3,2} = {1,2,3} - 我们将它们命名为词典。此方法具有隐式0以启动第一个差异的集合。字典顺序中的组合索引（McCaffrey）还有另外一种方法：它的概念更易于掌握和编程，但它没有Buckles的优化。幸运的是，它也不会产生重复的组合：最大化的集合在哪里举个例子：27 = C(6,4) + C(5,3) + C(2,2) + C(1,1)。因此，第四十七个词典组合的四个事物是：{1,2,5,6}，这些是你想要看的任何集合的索引。下面的示例（OCaml）需要choose功能，留给读者：(*&nbsp;this&nbsp;will&nbsp;find&nbsp;the&nbsp;[x]&nbsp;combination&nbsp;of&nbsp;a&nbsp;[set]&nbsp;list&nbsp;when&nbsp;taking&nbsp;[k]&nbsp;elements&nbsp;*)let&nbsp;combination_maccaffery&nbsp;set&nbsp;k&nbsp;x&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;maximize&nbsp;function&nbsp;--&nbsp;maximize&nbsp;a&nbsp;that&nbsp;is&nbsp;aCb&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*) &nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;return&nbsp;largest&nbsp;c&nbsp;where&nbsp;c&nbsp;<&nbsp;i&nbsp;and&nbsp;choose(c,i)&nbsp;<=&nbsp;z&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*) &nbsp;&nbsp;&nbsp;&nbsp;let&nbsp;rec&nbsp;maximize&nbsp;a&nbsp;b&nbsp;x&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(choose&nbsp;a&nbsp;b&nbsp;)&nbsp;<=&nbsp;x&nbsp;then&nbsp;a&nbsp;else&nbsp;maximize&nbsp;(a-1)&nbsp;b&nbsp;x&nbsp;&nbsp;&nbsp;&nbsp;in &nbsp;&nbsp;&nbsp;&nbsp;let&nbsp;rec&nbsp;iterate&nbsp;n&nbsp;x&nbsp;i&nbsp;=&nbsp;match&nbsp;i&nbsp;with &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;0&nbsp;->&nbsp;[] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;i&nbsp;-> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;let&nbsp;max&nbsp;=&nbsp;maximize&nbsp;n&nbsp;i&nbsp;x&nbsp;in &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;max&nbsp;::&nbsp;iterate&nbsp;n&nbsp;(x&nbsp;-&nbsp;(choose&nbsp;max&nbsp;i))&nbsp;(i-1) &nbsp;&nbsp;&nbsp;&nbsp;in &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;x&nbsp;<&nbsp;0&nbsp;then&nbsp;failwith&nbsp;"errors"&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;let&nbsp;idxs&nbsp;=&nbsp;&nbsp;iterate&nbsp;(List.length&nbsp;set)&nbsp;x&nbsp;k&nbsp;in &nbsp;&nbsp;&nbsp;&nbsp;List.map&nbsp;(List.nth&nbsp;set)&nbsp;(List.sort&nbsp;(-)&nbsp;idxs)一个小而简单的组合迭代器提供以下两种算法用于教学目的。它们实现了迭代器和（更一般的）文件夹整体组合。它们尽可能快，具有复杂度O（n&nbsp;C&nbsp;k）。内存消耗受到约束k。我们将从迭代器开始，它将为每个组合调用用户提供的函数let&nbsp;iter_combs&nbsp;n&nbsp;k&nbsp;f&nbsp;= &nbsp;&nbsp;let&nbsp;rec&nbsp;iter&nbsp;v&nbsp;s&nbsp;j&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;j&nbsp;=&nbsp;k&nbsp;then&nbsp;f&nbsp;v &nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;for&nbsp;i&nbsp;=&nbsp;s&nbsp;to&nbsp;n&nbsp;-&nbsp;1&nbsp;do&nbsp;iter&nbsp;(i::v)&nbsp;(i+1)&nbsp;(j+1)&nbsp;done&nbsp;in &nbsp;&nbsp;iter&nbsp;[]&nbsp;0&nbsp;0更通用的版本将从初始状态开始调用用户提供的函数以及状态变量。因为我们需要在不同状态之间传递状态，所以我们不会使用for循环，而是使用递归，let&nbsp;fold_combs&nbsp;n&nbsp;k&nbsp;f&nbsp;x&nbsp;= &nbsp;&nbsp;let&nbsp;rec&nbsp;loop&nbsp;i&nbsp;s&nbsp;c&nbsp;x&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;i&nbsp;<&nbsp;n&nbsp;then &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;loop&nbsp;(i+1)&nbsp;s&nbsp;c&nbsp;@@ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;let&nbsp;c&nbsp;=&nbsp;i::c&nbsp;and&nbsp;s&nbsp;=&nbsp;s&nbsp;+&nbsp;1&nbsp;and&nbsp;i&nbsp;=&nbsp;i&nbsp;+&nbsp;1&nbsp;in &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;s&nbsp;<&nbsp;k&nbsp;then&nbsp;loop&nbsp;i&nbsp;s&nbsp;c&nbsp;x&nbsp;else&nbsp;f&nbsp;c&nbsp;x &nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;x&nbsp;in &nbsp;&nbsp;loop&nbsp;0&nbsp;0&nbsp;[]&nbsp;x

Answer 2

在C＃中：public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k){&nbsp; return k == 0 ? new[] { new T[0] } :&nbsp; &nbsp; elements.SelectMany((e, i) =>&nbsp; &nbsp; &nbsp; elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));}用法：var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);结果：123124125134135145234235245345

Answer 3

短java解决方案：import java.util.Arrays;public class Combination {&nbsp; &nbsp; public static void main(String[] args){&nbsp; &nbsp; &nbsp; &nbsp; String[] arr = {"A","B","C","D","E","F"};&nbsp; &nbsp; &nbsp; &nbsp; combinations2(arr, 3, 0, new String[3]);&nbsp; &nbsp; }&nbsp; &nbsp; static void combinations2(String[] arr, int len, int startPosition, String[] result){&nbsp; &nbsp; &nbsp; &nbsp; if (len == 0){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println(Arrays.toString(result));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; for (int i = startPosition; i <= arr.length-len; i++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result[result.length - len] = arr[i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; combinations2(arr, len-1, i+1, result);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp;}结果将是[A, B, C][A, B, D][A, B, E][A, B, F][A, C, D][A, C, E][A, C, F][A, D, E][A, D, F][A, E, F][B, C, D][B, C, E][B, C, F][B, D, E][B, D, F][B, E, F][C, D, E][C, D, F][C, E, F][D, E, F]

Answer 4

我可以提出我的递归Python解决方案来解决这个问题吗？def choose_iter(elements, length):&nbsp; &nbsp; for i in xrange(len(elements)):&nbsp; &nbsp; &nbsp; &nbsp; if length == 1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield (elements[i],)&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for next in choose_iter(elements[i+1:len(elements)], length-1):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield (elements[i],) + nextdef choose(l, k):&nbsp; &nbsp; return list(choose_iter(l, k))用法示例：>>> len(list(choose_iter("abcdefgh",3)))56我喜欢它的简单性。