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

我想编写一个函数，该函数采用字母数组作为参数，并选择多个字母。

假设您提供8个字母的数组，并希望从中选择3个字母。 然后您将获得：

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

返回由3个字母组成的数组（或单词）。

#1楼

我为此在SQL Server 中创建了一个解决方案，并将其发布在我的网站上： http : ///downloads/code/sql/fn_GetMChooseNCombos.sql.htm

这是显示用法的示例：

SELECT * FROM dbo.fn_GetMChooseNCombos('ABCD', 2, '')

结果：

Word----ABACADBCBDCD(6 row(s) affected)

#2楼

bs = function(num) {var str = this,length = str.length,of = Math.pow(2, length) - 1,out, combinations = [];while(of) {out = [];for(var i = 0, y; i < length; i++) {y = (1 << i);if(y & of && (y !== of))out.push(str[i]);}if (out.length >= num) {combinations.push(out);}of--;}return combinations;}

#3楼

/3118596

有一个JavaScript实现。 它具有获取k组合以及任何对象数组的所有组合的功能。 例子：

k_combinations([1,2,3], 2)-> [[1,2], [1,3], [2,3]]combinations([1,2,3])-> [[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

#4楼

我编写了一个类来处理使用二项式系数的常用函数，这是您的问题所属的问题的类型。 它执行以下任务：

将所有N选择K的所有K索引以一种不错的格式输出到文件。 K索引可以替换为更具描述性的字符串或字母。 这种方法使解决这类问题变得非常简单。

将K索引转换为已排序的二项式系数表中条目的适当索引。 该技术比依赖迭代的较早发布的技术要快得多。 它通过使用Pascal三角形固有的数学属性来实现此目的。 我的论文谈到了这一点。 我相信我是第一个发现和发布这项技术的人，但是我可能是错的。

将排序后的二项式系数表中的索引转换为相应的K索引。

使用Mark Dominus方法计算二项式系数，该二项式系数溢出的可能性小得多，并且适用于较大的数字。

该类用.NET C＃编写，并提供了一种使用通用列表来管理与问题相关的对象（如果有）的方法。 此类的构造函数采用一个名为InitTable的布尔值，当该布尔值为true时，将创建一个通用列表来保存要管理的对象。 如果该值为false，则不会创建表。 无需创建表即可执行上述4种方法。 提供了访问器方法来访问表。

有一个关联的测试类，显示了如何使用该类及其方法。 它已经通过2种情况进行了广泛的测试，并且没有已知的错误。

要了解有关该类的信息并下载代码，请参见将二项式系数制表 。

将此类转换为C ++应该不难。

#5楼

《计算机编程艺术》第4卷：分册3比我所描述的更适合您的特定情况。

格雷码

您会遇到的一个问题当然是记忆力，而且很快，您的集合中会有20个元素出现问题-20 C 3 =1140。而且，如果要遍历集合，最好使用修改后的灰色代码算法，因此您不必将所有代码都保存在内存中。 这些将根据前一个生成下一个组合，并避免重复。 其中有许多用于不同用途。 我们是否要最大化连续组合之间的差异？ 最小化？ 等等。

一些描述格雷码的原始论文：

某些汉密尔顿路径和最小变化算法 相邻立交组合生成算法

以下是涉及该主题的其他一些论文：

Eades，Hickey，Read相邻互换组合生成算法 （PDF，带有Pascal中的代码）的有效实现 组合发电机 组合格雷码调查 （PostScript） 格雷码算法

蔡斯的小提琴（算法）

菲利普·蔡斯（Phillip J Chase），“ 算法382：N个对象中M个的组合 ”（1970年）

C语言中的算法

词典顺序的组合索引（Buckles算法515）

您也可以按组合索引（按字典顺序）引用组合。 意识到索引应该是基于索引从右到左的一些变化，我们可以构造一些应该恢复组合的东西。

因此，我们有一组{1,2,3,4,5,6} ...并且我们想要三个元素。 假设{1,2,3}，我们可以说元素之间的差异是一个，并且顺序是最小的。 {1,2,4}有一个变化，按字典顺序是第2个。因此，最后一位的“变化”数量占字典顺序的一个变化。 具有更改{1,3,4}的第二个位置具有一个更改，但是由于它位于第二个位置（与原始集中元素的数量成正比），因此说明了更多更改。

我所描述的方法似乎是一种解构，从设置到索引，我们需要做相反的事情-这要复杂得多。 这是扣具解决问题的方法。 我写了一些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)。 因此，第四件事情的第27个词典组合为：{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 xinlet rec iterate n x i = match i with| 0 -> []| i ->let max = maximize n i x inmax :: iterate n (x - (choose max i)) (i-1)inif x < 0 then failwith "errors" elselet idxs = iterate (List.length set) x k inList.map (List.nth set) (List.sort (-) idxs)

一个简单的组合迭代器

出于教学目的，提供了以下两种算法。 它们实现了迭代器和（更通用的）文件夹的整体组合。 它们尽可能快，具有复杂度O（ n C k ）。 内存消耗由k约束。

我们将从迭代器开始，该迭代器将为每个组合调用用户提供的函数

let iter_combs n k f =let rec iter v s j =if j = k then f velse for i = s to n - 1 do iter (i::v) (i+1) (j+1) done initer [] 0 0

从初始状态开始，更通用的版本将调用用户提供的函数以及状态变量。 由于我们需要在不同状态之间传递状态，因此我们不会使用for循环，而是使用递归，

let fold_combs n k f x =let rec loop i s c x =if i < n thenloop (i+1) s c @@let c = i::c and s = s + 1 and i = i + 1 inif s < k then loop i s c x else f c xelse x inloop 0 0 [] x

#6楼

假设您的字母数组如下所示：“ ABCDEFGH”。 您有三个索引（i，j，k），它们指示当前单词要使用的字母，您从以下位置开始：

A B C D E F G H^ ^ ^i j k

首先，您改变k，因此下一步看起来像这样：

A B C D E F G H^ ^ ^i j k

如果到达末尾，则继续并依次改变j和k。

A B C D E F G H^ ^ ^i j kA B C D E F G H^ ^ ^i j k

j达到G后，您也开始改变i。

A B C D E F G H^ ^ ^i j kA B C D E F G H^ ^ ^i j k...

用代码写的看起来像这样

void print_combinations(const char *string){int i, j, k;int len = strlen(string);for (i = 0; i < len - 2; i++){for (j = i + 1; j < len - 1; j++){for (k = j + 1; k < len; k++)printf("%c%c%c\n", string[i], string[j], string[k]);}}}

#7楼

static IEnumerable<string> Combinations(List<string> characters, int length){for (int i = 0; i < characters.Count; i++){// only want 1 character, just return this oneif (length == 1)yield return characters[i];// want more than one character, return this one plus all combinations one shorter// only use characters after the current one for the rest of the combinationselseforeach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))yield return characters[i] + next;}}

#8楼

如果您可以使用SQL语法-举例来说，如果您使用LINQ来访问结构或数组的字段，或者直接访问具有仅包含一个字符字段“ Letter”的名为“ Alphabet”的表的数据库，则可以调整以下内容码：

SELECT A.Letter, B.Letter, C.LetterFROM Alphabet AS A, Alphabet AS B, Alphabet AS CWHERE A.Letter<>B.Letter AND A.Letter<>C.Letter AND B.Letter<>C.LetterAND A.Letter<B.Letter AND B.Letter<C.Letter

尽管您在“字母”表中有多少个字母（可以是3、8、10、27等），这将返回3个字母的所有组合。

如果您想要的是所有排列，而不是组合（即，您希望“ ACB”和“ ABC”算作不同，而不是只出现一次），只需删除最后一行（AND），就可以了。

编辑后：重新阅读问题后，我意识到需要的是通用算法，而不是针对选择3个项目的特定算法。 亚当·休斯（Adam Hughes）的回答是完整的，很遗憾，我还不能投票赞成。 这个答案很简单，但仅适用于您只需要3个项目的情况。

#9楼

以下递归算法从有序集合中选择所有k元素组合：

选择的第一要素i的组合 将i与从大于i的元素集中递归选择的k-1元素的每种组合结合起来。

对集合中的每个i进行上述迭代。

请务必选择大于i的其余元素，以避免重复。 这样，[3,5]将仅被选择一次，因为[3]与[5]组合，而不是两次（条件消除了[5] + [3]）。 没有这种条件，您将获得变化而不是组合。

#10楼

这是我在C ++中的主张

我试图对迭代器类型施加尽可能小的限制，因此此解决方案仅假定转发迭代器，并且它可以是const_iterator。 这适用于任何标准容器。 如果参数没有意义，则抛出std :: invalid_argumnent

#include <vector>#include <stdexcept>template <typename Fci> // Fci - forward const iteratorstd::vector<std::vector<Fci> >enumerate_combinations(Fci begin, Fci end, unsigned int combination_size){if(begin == end && combination_size > 0u)throw std::invalid_argument("empty set and positive combination size!");std::vector<std::vector<Fci> > result; // empty set of combinationsif(combination_size == 0u) return result; // there is exactly one combination of// size 0 - emty setstd::vector<Fci> current_combination;current_combination.reserve(combination_size + 1u); // I reserve one aditional slot// in my vector to store// the end sentinel there.// The code is cleaner thanks to thatfor(unsigned int i = 0u; i < combination_size && begin != end; ++i, ++begin){current_combination.push_back(begin); // Construction of the first combination}// Since I assume the itarators support only incrementing, I have to iterate over// the set to get its size, which is expensive. Here I had to itrate anyway to // produce the first cobination, so I use the loop to also check the size.if(current_combination.size() < combination_size)throw std::invalid_argument("combination size > set size!");result.push_back(current_combination); // Store the first combination in the results setcurrent_combination.push_back(end); // Here I add mentioned earlier sentinel to// simplyfy rest of the code. If I did it // earlier, previous statement would get ugly.while(true){unsigned int i = combination_size;Fci tmp; // Thanks to the sentinel I can find firstdo // iterator to change, simply by scaning{// from right to left and looking for thetmp = current_combination[--i]; // first "bubble". The fact, that it's ++tmp;// a forward iterator makes it ugly but I}// can't help it.while(i > 0u && tmp == current_combination[i + 1u]);// Here is probably my most obfuscated expression.// Loop above looks for a "bubble". If there is no "bubble", that means, that// current_combination is the last combination, Expression in the if statement// below evaluates to true and the function exits returning result.// If the "bubble" is found however, the ststement below has a sideeffect of // incrementing the first iterator to the left of the "bubble".if(++current_combination[i] == current_combination[i + 1u])return result;// Rest of the code sets posiotons of the rest of the iterstors// (if there are any), that are to the right of the incremented one,// to form next combinationwhile(++i < combination_size){current_combination[i] = current_combination[i - 1u];++current_combination[i];}// Below is the ugly side of using the sentinel. Well it had to haave some // disadvantage. Try without it.result.push_back(std::vector<Fci>(current_combination.begin(),current_combination.end() - 1));}}

#11楼

我在python中有一个用于项目euler的置换算法：

def missing(miss,src):"Returns the list of items in src not present in miss"return [i for i in src if i not in miss]def permutation_gen(n,l):"Generates all the permutations of n items of the l list"for i in l:if n<=1: yield [i]r = [i]for j in permutation_gen(n-1,missing([i],l)): yield r+j

如果

n<len(l)

您应该没有重复地拥有所有需要的组合，您需要吗？

它是一个生成器，因此您可以在以下方式中使用它：

for comb in permutation_gen(3,list("ABCDEFGH")):print comb

#12楼

到这里来的是爷爷COBOL，这是一门恶毒的语言。

让我们假设一个由34个元素组成的数组，每个元素8个字节（纯粹是任意选择）。其想法是枚举所有可能的4元素组合并将它们加载到数组中。

我们使用4个索引，每个索引在4组中每个位置

数组的处理如下：

idx1 = 1idx2 = 2idx3 = 3idx4 = 4

我们将idx4从4更改为末尾。 对于每个idx4，我们得到四个一组的唯一组合。 当idx4到达数组末尾时，我们将idx3加1，并将idx4设置为idx3 + 1。 然后，我们再次运行idx4。 我们以这种方式进行操作，分别增加idx3，idx2和idx1，直到idx1的位置从数组末尾开始小于4。 这样就完成了算法。

1--- pos.12--- pos 23--- pos 34--- pos 4567etc.

第一次迭代：

1234123512361237124512461247125612571267etc.

一个COBOL示例：

01 DATA_ARAY.05 FILLERPIC X(8) VALUE "VALUE_01".05 FILLERPIC X(8) VALUE "VALUE_02".etc.01 ARAY_DATA OCCURS 34.05 ARAY_ITEM PIC X(8).01 OUTPUT_ARAY OCCURS 50000 PIC X(32).01 MAX_NUM PIC 99 COMP VALUE 34.01 INDEXXES COMP.05 IDX1 PIC 99.05 IDX2 PIC 99.05 IDX3 PIC 99.05 IDX4 PIC 99.05 OUT_IDX PIC 9(9).01 WHERE_TO_STOP_SEARCHPIC 99 COMP.

* Stop the search when IDX1 is on the third last array element:COMPUTE WHERE_TO_STOP_SEARCH = MAX_VALUE - 3MOVE 1 TO IDX1PERFORM UNTIL IDX1 > WHERE_TO_STOP_SEARCHCOMPUTE IDX2 = IDX1 + 1PERFORM UNTIL IDX2 > MAX_NUMCOMPUTE IDX3 = IDX2 + 1PERFORM UNTIL IDX3 > MAX_NUMCOMPUTE IDX4 = IDX3 + 1PERFORM UNTIL IDX4 > MAX_NUMADD 1 TO OUT_IDXSTRING ARAY_ITEM(IDX1)ARAY_ITEM(IDX2)ARAY_ITEM(IDX3)ARAY_ITEM(IDX4)INTO OUTPUT_ARAY(OUT_IDX)ADD 1 TO IDX4END-PERFORMADD 1 TO IDX3END-PERFORMADD 1 TO IDX2END_PERFORMADD 1 TO IDX1END-PERFORM.

#13楼

在C ++中，以下例程将生成范围[first，last）之间的长度距离（first，k）的所有组合：

#include <algorithm>template <typename Iterator>bool next_combination(const Iterator first, Iterator k, const Iterator last){/* Credits: Mark Nelson http://marknelson.us */if ((first == last) || (first == k) || (last == k))return false;Iterator i1 = first;Iterator i2 = last;++i1;if (last == i1)return false;i1 = last;--i1;i1 = k;--i2;while (first != i1){if (*--i1 < *i2){Iterator j = k;while (!(*i1 < *j)) ++j;std::iter_swap(i1,j);++i1;++j;i2 = k;std::rotate(i1,j,last);while (last != j){++j;++i2;}std::rotate(k,i2,last);return true;}}std::rotate(first,k,last);return false;}

可以这样使用：

#include <string>#include <iostream>int main(){std::string s = "12345";std::size_t comb_size = 3;do{std::cout << std::string(s.begin(), s.begin() + comb_size) << std::endl;} while (next_combination(s.begin(), s.begin() + comb_size, s.end()));return 0;}

这将打印以下内容：

123124125134135145234235245345

#14楼

简短的Java解决方案：

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

结果将是

[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]

#15楼

Python中的简短示例：

def comb(sofar, rest, n):if n == 0:print sofarelse:for i in range(len(rest)):comb(sofar + rest[i], rest[i+1:], n-1)>>> comb("", "abcde", 3)abcabdabeacdaceadebcdbcebdecde

为了说明起见，下面的示例描述了递归方法：

示例：ABCDE

3的所有组合为：

A，其余2个的所有组合（BCDE） B与其余2的所有组合（CDE） C与其余2的所有组合（DE）

#16楼

在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);

结果：

123124125134135145234235245345

#17楼

Clojure版本：

(defn comb [k l](if (= 1 k) (map vector l)(apply concat(map-indexed#(map (fn [x] (conj x %2))(comb (dec k) (drop (inc %1) l)))l))))

#18楼

所有人都说过并在这里完成的是O'caml代码。 从代码中可以明显看出算法。

let combi n lst =let rec comb l c =if( List.length c = n) then [c] elsematch l with[] -> []| (h::t) -> (combi t (h::c))@(combi t c)incombi lst [];;

#19楼

这是我最近用Java写的代码，该代码计算并返回“ outOf”元素中“ num”元素的所有组合。

// author: Sourabh Bhat (heySourabh@)public class Testing{public static void main(String[] args){// Test case num = 5, outOf = 8.int num = 5;int outOf = 8;int[][] combinations = getCombinations(num, outOf);for (int i = 0; i < combinations.length; i++){for (int j = 0; j < combinations[i].length; j++){System.out.print(combinations[i][j] + " ");}System.out.println();}}private static int[][] getCombinations(int num, int outOf){int possibilities = get_nCr(outOf, num);int[][] combinations = new int[possibilities][num];int arrayPointer = 0;int[] counter = new int[num];for (int i = 0; i < num; i++){counter[i] = i;}breakLoop: while (true){// Initializing partfor (int i = 1; i < num; i++){if (counter[i] >= outOf - (num - 1 - i))counter[i] = counter[i - 1] + 1;}// Testing partfor (int i = 0; i < num; i++){if (counter[i] < outOf){continue;} else{break breakLoop;}}// Innermost partcombinations[arrayPointer] = counter.clone();arrayPointer++;// Incrementing partcounter[num - 1]++;for (int i = num - 1; i >= 1; i--){if (counter[i] >= outOf - (num - 1 - i))counter[i - 1]++;}}return combinations;}private static int get_nCr(int n, int r){if(r > n){throw new ArithmeticException("r is greater then n");}long numerator = 1;long denominator = 1;for (int i = n; i >= r + 1; i--){numerator *= i;}for (int i = 2; i <= n - r; i++){denominator *= i;}return (int) (numerator / denominator);}}

#20楼

这是Scala中一个优雅的通用实现，如99 Scala Problems中所述 。

object P26 {def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] = ls match {case Nil => Nilcase sublist@(_ :: tail) => f(sublist) ::: flatMapSublists(tail)(f)}def combinations[A](n: Int, ls: List[A]): List[List[A]] =if (n == 0) List(Nil)else flatMapSublists(ls) { sl =>combinations(n - 1, sl.tail) map {sl.head :: _}}}

#21楼

简洁的Javascript解决方案：

bine=function combine(k){ var toCombine=this;var last;function combi(n,comb){ var combs=[];for ( var x=0,y=comb.length;x<y;x++){for ( var l=0,m=toCombine.length;l<m;l++){combs.push(comb[x]+toCombine[l]); }}if (n<k-1){n++;combi(n,combs);} else{last=combs;}}combi(1,toCombine);return last;}// Example:// var toCombine=['a','b','c'];// var results=bine(4);

#22楼

我可以提出我的递归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],) + nextdef choose(l, k):return list(choose_iter(l, k))

用法示例：

>>> len(list(choose_iter("abcdefgh",3)))56

我喜欢它的简单性。

#23楼

带有懒惰组合索引生成的另一个C＃版本。 此版本维护一个索引数组，以定义所有值的列表与当前组合的值之间的映射，即在整个运行期间不断使用O（k）额外空间。 该代码以O（k）时间生成单个组合，包括第一个组合。

public static IEnumerable<T[]> Combinations<T>(this T[] values, int k){if (k < 0 || values.Length < k)yield break; // invalid parameters, no combinations possible// generate the initial combination indicesvar combIndices = new int[k];for (var i = 0; i < k; i++){combIndices[i] = i;}while (true){// return next combinationvar combination = new T[k];for (var i = 0; i < k; i++){combination[i] = values[combIndices[i]];}yield return combination;// find first index to updatevar indexToUpdate = k - 1;while (indexToUpdate >= 0 && combIndices[indexToUpdate] >= values.Length - k + indexToUpdate){indexToUpdate--;}if (indexToUpdate < 0)yield break; // done// update combination indicesfor (var combIndex = combIndices[indexToUpdate] + 1; indexToUpdate < k; indexToUpdate++, combIndex++){combIndices[indexToUpdate] = combIndex;}}}

测试代码：

foreach (var combination in new[] {'a', 'b', 'c', 'd', 'e'}.Combinations(3)){System.Console.WriteLine(String.Join(" ", combination));}

输出：

a b ca b da b ea c da c ea d eb c db c eb d ec d e

#24楼

算法：

从1到2 ^ n计数。 将每个数字转换为其二进制表示形式。 根据位置将每个“上”位转换为集合中的元素。

在C＃中：

void Main(){var set = new [] {"A", "B", "C", "D" }; //, "E", "F", "G", "H", "I", "J" };var kElement = 2;for(var i = 1; i < Math.Pow(2, set.Length); i++) {var result = Convert.ToString(i, 2).PadLeft(set.Length, '0');var cnt = Regex.Matches(Regex.Escape(result), "1").Count; if (cnt == kElement) {for(int j = 0; j < set.Length; j++)if ( Char.GetNumericValue(result[j]) == 1)Console.Write(set[j]);Console.WriteLine();}}}

为什么行得通？

n个元素集的子集与n位序列之间存在双射。

这意味着我们可以通过对序列进行计数来找出有多少个子集。

例如，下面的四个元素集可以用{0,1} X {0，1} X {0，1} X {0，1}（或2 ^ 4）不同序列表示。

所以-我们要做的就是从1到2 ^ n计数以找到所有组合。（我们忽略空集。）接下来，将数字转换为其二进制表示形式。 然后将集合中的元素替换为“ on”位。

如果仅需要k个元素结果，则仅在k位为“ on”时打印。

（如果要所有子集而不是k个长度子集，请删除cnt / kElement部分。）

（有关证明，请参阅MIT免费课程软件“计算机科学数学”，雷曼等人，第11.2.2节。https: //ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics- for-computer-science-fall- / readings / ）

#25楼

假设您的字母数组如下所示：“ ABCDEFGH”。 您有三个索引（i，j，k），它们指示当前单词要使用的字母，您从以下位置开始：

A B C D E F G H^ ^ ^i j k

首先，您改变k，因此下一步看起来像这样：

A B C D E F G H^ ^ ^i j k

如果到达末尾，则继续并依次改变j和k。

A B C D E F G H^ ^ ^i j kA B C D E F G H^ ^ ^i j k

j达到G后，您也开始改变i。

A B C D E F G H^ ^ ^i j kA B C D E F G H^ ^ ^i j k...

function initializePointers($cnt) {$pointers = [];for($i=0; $i<$cnt; $i++) {$pointers[] = $i;}return $pointers;}function incrementPointers(&$pointers, &$arrLength) {for($i=0; $i<count($pointers); $i++) {$currentPointerIndex = count($pointers) - $i - 1;$currentPointer = $pointers[$currentPointerIndex];if($currentPointer < $arrLength - $i - 1) {++$pointers[$currentPointerIndex];for($j=1; ($currentPointerIndex+$j)<count($pointers); $j++) {$pointers[$currentPointerIndex+$j] = $pointers[$currentPointerIndex]+$j;}return true;}}return false;}function getDataByPointers(&$arr, &$pointers) {$data = [];for($i=0; $i<count($pointers); $i++) {$data[] = $arr[$pointers[$i]];}return $data;}function getCombinations($arr, $cnt){$len = count($arr);$result = [];$pointers = initializePointers($cnt);do {$result[] = getDataByPointers($arr, $pointers);} while(incrementPointers($pointers, count($arr)));return $result;}$result = getCombinations([0, 1, 2, 3, 4, 5], 3);print_r($result);

基于/a/127898/2628125 ，但更抽象，适用于任何大小的指针。

#26楼

在这里，您有一个用C＃编码的算法的惰性评估版：

static bool nextCombination(int[] num, int n, int k){bool finished, changed;changed = finished = false;if (k > 0){for (int i = k - 1; !finished && !changed; i--){if (num[i] < (n - 1) - (k - 1) + i){num[i]++;if (i < k - 1){for (int j = i + 1; j < k; j++){num[j] = num[j - 1] + 1;}}changed = true;}finished = (i == 0);}}return changed;}static IEnumerable Combinations<T>(IEnumerable<T> elements, int k){T[] elem = elements.ToArray();int size = elem.Length;if (k <= size){int[] numbers = new int[k];for (int i = 0; i < k; i++){numbers[i] = i;}do{yield return numbers.Select(n => elem[n]);}while (nextCombination(numbers, size, k));}}

并测试部分：

static void Main(string[] args){int k = 3;var t = new[] { "dog", "cat", "mouse", "zebra"};foreach (IEnumerable<string> i in Combinations(t, k)){Console.WriteLine(string.Join(",", i));}}

希望这对您有所帮助！

#27楼

JavaScript，基于生成器的递归方法：

function *nCk(n,k){ for(var i=n-1;i>=k-1;--i) if(k===1) yield [i]; else for(var temp of nCk(i,k-1)){ temp.unshift(i); yield temp; } } function test(){ try{ var n=parseInt(ninp.value); var k=parseInt(kinp.value); log.innerText=""; var stop=Date.now()+1000; if(k>=1) for(var res of nCk(n,k)) if(Date.now()<stop) log.innerText+=JSON.stringify(res)+" "; else{ log.innerText+="1 second passed, stopping here."; break; } }catch(ex){} }

n:<input id="ninp" oninput="test()"> &gt;= k:<input id="kinp" oninput="test()"> &gt;= 1 <div id="log"></div>

通过这种方式（减小i和unshift()），它会以降序生成组合和组合内的元素，从而使眼睛有些悦目。

测试在1秒钟后停止，因此输入怪异数字相对安全。

#28楼

我发现此线程很有用，并认为我会添加一个Java脚本解决方案，然后将其弹出Firebug。 如果起始字符串很大，则可能需要一些时间，具体取决于您的JS引擎。

function string_recurse(active, rest) {if (rest.length == 0) {console.log(active);} else {string_recurse(active + rest.charAt(0), rest.substring(1, rest.length));string_recurse(active, rest.substring(1, rest.length));}}string_recurse("", "abc");

输出应如下所示：

abcabacabcbc

#29楼

这是一种为您提供随机长度字符串中指定大小的所有组合的方法。 类似于quinmars的解决方案，但适用于各种输入和k。

可以更改代码以换行，即从输入“ abcd” wk = 3中获得“ dab”。

public void run(String data, int howMany){choose(data, howMany, new StringBuffer(), 0);}//n choose kprivate void choose(String data, int k, StringBuffer result, int startIndex){if (result.length()==k){System.out.println(result.toString());return;}for (int i=startIndex; i<data.length(); i++){result.append(data.charAt(i));choose(data,k,result, i+1);result.setLength(result.length()-1);}}

输出“ abcde”：

abc abd abe acd ace ade bcd bce bde cde

#30楼

Haskell中的简单递归算法

import Data.Listcombinations 0 lst = [[]]combinations n lst = do(x:xs) <- tails lstrest <- combinations (n-1) xsreturn $ x : rest

我们首先定义特殊情况，即选择零元素。 它产生一个结果，它是一个空列表（即一个包含空列表的列表）。

对于n> 0，x遍历列表的每个元素，而xs是x之后的每个元素。

rest使用对combinations的递归调用从xs选择n - 1元素。 该函数的最终结果是一个列表，其中每个元素都是x : rest每个x和rest不同值的x : rest（即，以x为首，rest为尾的列表）。

> combinations 3 "abcde"["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]

当然，由于Haskell是惰性的，因此该列表会根据需要逐渐生成，因此您可以部分评估指数级的大组合。

> let c = combinations 8 "abcdefghijklmnopqrstuvwxyz"> take 10 c["abcdefgh","abcdefgi","abcdefgj","abcdefgk","abcdefgl","abcdefgm","abcdefgn","abcdefgo","abcdefgp","abcdefgq"]