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

我想写一个函数，把一个字母数组作为参数和一些这些字母来select。

假设你提供了一个8个字母的数组，并希望从中select3个字母。 那么你应该得到：

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

数组（或单词），每个由3个字母组成。

Answer 1

计算机编程艺术第4卷：分类3有很多这些可能适合你的特定情况比我如何描述。

灰色代码

一个你会遇到的问题当然是记忆，而且很快，你会遇到20个元素的问题 – ²⁰ C ₃ = 1140.如果你想迭代这个集合，最好使用修改的灰色代码algorithm，所以你不把它们全部放在内存中。 这些从前一个产生下一个组合，并避免重复。 有很多这些用于不同的用途。 我们想要最大化连续组合之间的差异吗？ 最小化？ 等等。

一些描述灰色代码的原始文件：

1. 一些Hamiltonpath和一个最小变化algorithm
2. 相邻交换组合生成algorithm

这里有一些其他的论文涉及到这个话题：

1. Eades，Hickey，Read相邻交换组合生成algorithm的高效实现 （PDF，代码采用Pascal）
2. 组合发生器
3. 组合格雷码综述 （PostScript）
4. 一种灰色编码algorithm

追逐的旋转（algorithm）

Phillip J Chase，“ algorithm382：N个对象中的M个组合 ”（1970）

algorithm在C …

字典顺序中的组合索引（扣扣algorithm515）

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

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

我所描述的方法是一种解构，就像从设置到索引那样，我们需要做相反的事情 – 这是非常棘手的。 这就是Buckles如何解决这个问题。 我写了一些C来计算它们 ，只有很小的变化 – 我使用集合的索引而不是数字范围来表示集合，所以我们总是从0 … n开始工作。 注意：

1. 由于组合无序，{1,3,2} = {1,2,3} – 我们命令它们是字典。
2. 这个方法有一个隐含的0来启动第一个差异的集合。

字典顺序组合索引（McCaffrey）

还有另外一个方法 ：它的概念更易于掌握和编程，但是没有Buckles的优化。 幸运的是，它也不会产生重复的组合：

集合 最大化 ，在哪里 。

例如： 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1) 。 所以，第二十七个词汇组合是：{1,2,5,6}，这些是你想要看的任何集合的索引。 下面的例子（OCaml），需要choosefunction，留给读者：

 (* this will find the [x] combination of a [set] list when taking [k] elements *) let combination_maccaffery set kx = (* maximize function -- maximize a that is aCb *) (* return largest c where c < i and choose(c,i) <= z *) let rec maximize abx = if (choose ab ) <= x then a else maximize (a-1) bx in let rec iterate nxi = match i with | 0 -> [] | i -> let max = maximize nix in max :: iterate n (x - (choose max i)) (i-1) in if x < 0 then failwith "errors" else let idxs = iterate (List.length set) xk in List.map (List.nth set) (List.sort (-) idxs) 

Answer 2

在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 

Answer 3

我可以提出我的recursionPython解决scheme到这个问题？

 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 

我喜欢它的简单性。

Answer 4

短的java解决scheme：

 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] 

Answer 5

让我们说你的字母数组看起来像这样：“ABCDEFGH”。 您有三个索引（i，j，k），表示您将要用于当前单词的哪些字母，您从以下开始：

 ABCDEFGH
 ^ ^ ^
 IJK

首先你改变k，所以下一步看起来是这样的：

 ABCDEFGH
 ^ ^ ^
 IJK

如果你到了最后，你继续改变，然后再改变k。

 ABCDEFGH
 ^ ^ ^
 IJK

 ABCDEFGH
 ^ ^ ^
 IJK

一旦你到达G，你也开始改变我。

 ABCDEFGH
   ^ ^ ^
   IJK

 ABCDEFGH
   ^ ^ ^
   IJK
 ...

用代码编写，看起来像这样

 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]); } } } 

Answer 6

下面的recursionalgorithm从有序集合中选取所有的k元素组合：

• select你的组合的第一个元素i
• 将i与从大于i的元素集合中recursionselect的k-1元素的每个组合进行组合。

为i中的每个i重复上述过程。

select其余的元素比i ，这是至关重要的，以避免重复。 这样[3,5]将被选中一次，如[3]结合[5]，而不是两次（条件消除[5] + [3]）。 没有这个条件，你会得到变化，而不是组合。

Answer 7

我发现这个线程有用，并认为我会添加一个Javascript解决scheme，你可以popup到Firebug。 根据您的JS引擎，如果起始string很大，可能需要一些时间。

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

输出应如下所示：

 abc ab ac a bc b c 

Answer 8

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

这将打印以下内容：

 123 124 125 134 135 145 234 235 245 345 

Answer 9

 static IEnumerable<string> Combinations(List<string> characters, int length) { for (int i = 0; i < characters.Count; i++) { // only want 1 character, just return this one if (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 combinations else foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1)) yield return characters[i] + next; } } 

Answer 10

Haskell中简单的recursionalgorithm

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

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

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

rest从xsselectn - 1元素，使用recursion调用combinations 。 函数的最终结果是一个列表，其中每个元素都是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"] 

Answer 11

Python中的简短例子：

 def comb(sofar, rest, n): if n == 0: print sofar else: for i in range(len(rest)): comb(sofar + rest[i], rest[i+1:], n-1) >>> comb("", "abcde", 3) abc abd abe acd ace ade bcd bce bde cde 

为了说明，recursion方法用下面的例子来描述：

例如：ABCDE
3的所有组合将是：

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

Answer 12

 And here comes granddaddy COBOL, the much maligned language. Let's assume an array of 34 elements of 8 bytes each (purely arbitrary selection.) The idea is to enumerate all possible 4-element combinations and load them into an array. We use 4 indices, one each for each position in the group of 4 The array is processed like this: idx1 = 1 idx2 = 2 idx3 = 3 idx4 = 4 We vary idx4 from 4 to the end. For each idx4 we get a unique combination 

四人组。 当idx4到达数组的末尾时，我们将idx3加1并将idx4设置为idx3 + 1。 然后我们再次运行idx4到最后。 我们以这种方式进行，分别增加idx3，idx2和idx1，直到idx1的位置从数组末尾小于4。 这完成了algorithm。

 1 --- pos.1 2 --- pos 2 3 --- pos 3 4 --- pos 4 5 6 7 etc. First iterations: 1234 1235 1236 1237 1245 1246 1247 1256 1257 1267 etc. A COBOL example: 01 DATA_ARAY. 05 FILLER PIC X(8) VALUE "VALUE_01". 05 FILLER PIC 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_SEARCH PIC 99 COMP. 

---

 * Stop the search when IDX1 is on the third last array element: COMPUTE WHERE_TO_STOP_SEARCH = MAX_VALUE - 3 MOVE 1 TO IDX1 PERFORM UNTIL IDX1 > WHERE_TO_STOP_SEARCH COMPUTE IDX2 = IDX1 + 1 PERFORM UNTIL IDX2 > MAX_NUM COMPUTE IDX3 = IDX2 + 1 PERFORM UNTIL IDX3 > MAX_NUM COMPUTE IDX4 = IDX3 + 1 PERFORM UNTIL IDX4 > MAX_NUM ADD 1 TO OUT_IDX STRING ARAY_ITEM(IDX1) ARAY_ITEM(IDX2) ARAY_ITEM(IDX3) ARAY_ITEM(IDX4) INTO OUTPUT_ARAY(OUT_IDX) ADD 1 TO IDX4 END-PERFORM ADD 1 TO IDX3 END-PERFORM ADD 1 TO IDX2 END_PERFORM ADD 1 TO IDX1 END-PERFORM. 

Answer 13

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

 object P26 { def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] = ls match { case Nil => Nil case 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 :: _} } } 

Answer 14

如果您可以使用SQL语法 – 比方说，如果您使用LINQ来访问结构或数组的字段，或者直接访问只有一个字符字段“Letter”的名为“Alphabet”的表的数据库，则可以使用码：

 SELECT A.Letter, B.Letter, C.Letter FROM Alphabet AS A, Alphabet AS B, Alphabet AS C WHERE A.Letter<>B.Letter AND A.Letter<>C.Letter AND B.Letter<>C.Letter AND A.Letter<B.Letter AND B.Letter<C.Letter 

这将返回3个字母的所有组合，尽pipe在“Alphabet”表中有多less个字母（可以是3,8,10,27等）。

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

后编辑：重读这个问题后，我意识到需要的是一般algorithm，而不仅仅是select3项的具体情况。 亚当·休斯的答案是完整的，不幸的是我不能投票（还）。 这个答案很简单，但只适用于当你想要3件物品的时候。

Answer 15

在这里，你有一个懒惰的评估版本的algorithm在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)); } } 

和testing部分：

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

希望这对你有所帮助！

Answer 16

https://gist.github.com/3118596

有一个JavaScript的实现。 它具有获得k-组合和任何对象数组的所有组合的function。 例子：

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

Answer 17

我有一个用于python的项目euler的排列algorithm：

 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 

Answer 18

另一个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 indices var combIndices = new int[k]; for (var i = 0; i < k; i++) { combIndices[i] = i; } while (true) { // return next combination var combination = new T[k]; for (var i = 0; i < k; i++) { combination[i] = values[combIndices[i]]; } yield return combination; // find first index to update var indexToUpdate = k - 1; while (indexToUpdate >= 0 && combIndices[indexToUpdate] >= values.Length - k + indexToUpdate) { indexToUpdate--; } if (indexToUpdate < 0) yield break; // done // update combination indices for (var combIndex = combIndices[indexToUpdate] + 1; indexToUpdate < k; indexToUpdate++, combIndex++) { combIndices[indexToUpdate] = combIndex; } } } 

testing代码：

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

输出：

 abc abd abe acd ace ade bcd bce bde cde 

Answer 19

 Array.prototype.combs = 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; } 

Answer 20

我为此在SQL Server 2005中创build了一个解决scheme，并将其发布到我的网站上： http : //www.jessemclain.com/downloads/code/sql/fn_GetMChooseNCombos.sql.htm

这里是一个示例来显示用法：

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

结果：

 Word ---- AB AC AD BC BD CD (6 row(s) affected) 

Answer 21

这是我在C ++中的主张

我试图对迭代器types施加尽可能小的限制，所以这个解决scheme假设只是前向迭代器，它可以是一个const_iterator。 这应该适用于任何标准容器。 如果参数没有意义，则会抛出std :: invalid_argumnent

 #include <vector> #include <stdexcept> template <typename Fci> // Fci - forward const iterator std::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 combinations if(combination_size == 0u) return result; // there is exactly one combination of // size 0 - emty set std::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 that for(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 set current_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 first do // iterator to change, simply by scaning { // from right to left and looking for the tmp = 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 combination while(++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)); } } 

Answer 22

所有说和做完这里的是O'caml的代码。 algorithm从代码中是明显的

 let combi n lst = let rec comb lc = if( List.length c = n) then [c] else match l with [] -> [] | (h::t) -> (combi t (h::c))@(combi tc) in combi lst [] ;; 

Answer 23

Clojure版本：

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

Answer 24

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

 // author: Sourabh Bhat ([e-mail]) 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 part for (int i = 1; i < num; i++) { if (counter[i] >= outOf - (num - 1 - i)) counter[i] = counter[i - 1] + 1; } // Testing part for (int i = 0; i < num; i++) { if (counter[i] < outOf) { continue; } else { break breakLoop; } } // Innermost part combinations[arrayPointer] = counter.clone(); arrayPointer++; // Incrementing part counter[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); } } 

Answer 25

一个简洁的Javascript解决scheme：

 Array.prototype.combine=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=toCombine.combine(4); 

Answer 26

Here is a method which gives you all combinations of specified size from a random length string. Similar to quinmars' solution, but works for varied input and k.

The code can be changed to wrap around, ie 'dab' from input 'abcd' wk=3.

 public void run(String data, int howMany){ choose(data, howMany, new StringBuffer(), 0); } //n choose k private 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); } } 

Output for "abcde":

abc abd abe acd ace ade bcd bce bde cde

Answer 27

I have written a class to handle common functions for working with the binomial coefficient, which is the type of problem that your problem falls under. It performs the following tasks:

1. Outputs all the K-indexes in a nice format for any N choose K to a file. The K-indexes can be substituted with more descriptive strings or letters. This method makes solving this type of problem quite trivial.

2. Converts the K-indexes to the proper index of an entry in the sorted binomial coefficient table. This technique is much faster than older published techniques that rely on iteration. It does this by using a mathematical property inherent in Pascal's Triangle. My paper talks about this. I believe I am the first to discover and publish this technique, but I could be wrong.

3. Converts the index in a sorted binomial coefficient table to the corresponding K-indexes.

4. Uses Mark Dominus method to calculate the binomial coefficient, which is much less likely to overflow and works with larger numbers.

5. The class is written in .NET C# and provides a way to manage the objects related to the problem (if any) by using a generic list. The constructor of this class takes a bool value called InitTable that when true will create a generic list to hold the objects to be managed. If this value is false, then it will not create the table. The table does not need to be created in order to perform the 4 above methods. Accessor methods are provided to access the table.

6. There is an associated test class which shows how to use the class and its methods. It has been extensively tested with 2 cases and there are no known bugs.

To read about this class and download the code, see Tablizing The Binomial Coeffieicent .

It should not be hard to convert this class to C++.

Answer 28

Here's my JavaScript solution that is a little more functional through use of reduce/map, which eliminates almost all variables

 function combinations(arr, size) { var len = arr.length; if (size > len) return []; if (!size) return [[]]; if (size == len) return [arr]; return arr.reduce(function (acc, val, i) { var res = combinations(arr.slice(i + 1), size - 1) .map(function (comb) { return [val].concat(comb); }); return acc.concat(res); }, []); } var combs = combinations([1,2,3,4,5,6,7,8],3); combs.map(function (comb) { document.body.innerHTML += comb.toString() + '<br />'; }); document.body.innerHTML += '<br /> Total combinations = ' + combs.length; 

Answer 29

Jumping on the bandwagon, and posting another solution. This is a generic Java implementation. Input: (int k) is number of elements to choose and (List<T> list) is the list to choose from. Returns a list of combinations (List<List<T>>) .

 public static <T> List<List<T>> getCombinations(int k, List<T> list) { List<List<T>> combinations = new ArrayList<List<T>>(); if (k == 0) { combinations.add(new ArrayList<T>()); return combinations; } for (int i = 0; i < list.size(); i++) { T element = list.get(i); List<T> rest = getSublist(list, i+1); for (List<T> previous : getCombinations(k-1, rest)) { previous.add(element); combinations.add(previous); } } return combinations; } public static <T> List<T> getSublist(List<T> list, int i) { List<T> sublist = new ArrayList<T>(); for (int j = i; j < list.size(); j++) { sublist.add(list.get(j)); } return sublist; } 

Answer 30

And here's a Clojure version that uses the same algorithm I describe in my OCaml implementation answer:

 (defn select ([items] (select items 0 (inc (count items)))) ([items n1 n2] (reduce concat (map #(select % items) (range n1 (inc n2))))) ([n items] (let [ lmul (fn [a list-of-lists-of-bs] (map #(cons a %) list-of-lists-of-bs)) ] (if (= n (count items)) (list items) (if (empty? items) items (concat (select n (rest items)) (lmul (first items) (select (dec n) (rest items))))))))) 

It provides three ways to call it:

(a) for exactly n selected items as the question demands:

  user=> (count (select 3 "abcdefgh")) 56 

(b) for between n1 and n2 selected items:

 user=> (select '(1 2 3 4) 2 3) ((3 4) (2 4) (2 3) (1 4) (1 3) (1 2) (2 3 4) (1 3 4) (1 2 4) (1 2 3)) 

(c) for between 0 and the size of the collection selected items:

 user=> (select '(1 2 3)) (() (3) (2) (1) (2 3) (1 3) (1 2) (1 2 3))