# algorithm - 组合递归 - 算法从n返回k个元素的所有组合

## 数组的所有组合 (20)

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

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))))
``````

``````import Data.List

combinations 0 lst = [[]]
combinations n lst = do
(x:xs) <- tails lst
rest   <- combinations (n-1) xs
return \$ x : rest
``````

``````> combinations 3 "abcde"
``````

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

## 灰色代码

2. 组合发生器
3. 组合格雷码综述 （PostScript）
4. 一种灰色编码算法

## Chase的Twiddle（算法）

Phillip J Chase，“ Algorithm 382：M of N of N Objects组合 ”（1970）

## 字典顺序中的组合索引（扣扣算法515）

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

## 字典顺序中的组合索引（McCaffrey）

``````(* 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)
``````

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

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;``````

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.

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

Lets say your array of letters looks like this: "ABCDEFGH". You have three indices (i, j, k) indicating which letters you are going to use for the current word, You start with:

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

First you vary k, so the next step looks like that:

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

If you reached the end you go on and vary j and then k again.

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

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

Once you j reached G you start also to vary i.

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

A 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);
``````

Based on https://.com/a/127898/2628125 , but more abstract, for any size of pointers.

• 选择你的组合的第一个元素`i`
• `i`与从大于`i`的元素集合中递归选择的`k-1`元素的每个组合进行组合。

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

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

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

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

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

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

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

``````#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
``````

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

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

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

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

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

``````#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
result.push_back(std::vector<Fci>(current_combination.begin(),
current_combination.end() - 1));
}
}
``````

``````// author: Sourabh Bhat ([email protected])

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

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

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