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

《计算机程序设计艺术》第4卷第3分册有大量的这些可能比我描述的更适合你的特定情况。

格雷码

您将遇到的一个问题当然是内存，并且很快，您将在您的集合中遇到20个元素的问题——# eyz0c# EYZ1 = 1140。如果你想遍历这个集合，最好使用修改过的灰码算法，这样你就不会把它们都保存在内存中。这将从前一个组合中生成下一个组合并避免重复。有很多不同的用途。我们想要最大化连续组合之间的差异吗?最小化?等等。

一些描述灰色代码的原始论文:

1. 一些Hamilton路径和最小变化算法
2. 相邻交换组合生成算法

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

1. Eades、Hickey、Read相邻交换组合生成算法的高效实现 (PDF，带有Pascal格式代码)
2. 组合生成器
3. # EYZ0(后记)
4. 一个灰色编码算法

Chase's Twiddle(算法)

菲利普·J·蔡斯，《算法382:N个对象中M个对象的组合》(1970)

# EYZ0……

按字典顺序排列的组合索引(Buckles算法515)

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

所以，我们有一个集合{1,2,3,4,5,6}…我们需要三个元素。比方说{1,2,3}我们可以说元素之间的差值是1并且是最小的。{1,2,4}有一个变化，在字典上是第2。因此，最后一个位置的“变化”的数量说明了字典顺序的一次变化。第二个位置，有一个变化{1,3,4}有一个变化，但由于它在第二个位置(与原始集合中元素的数量成正比)，所以占了更多的变化。

1. 由于组合是无序的，{1,3,2}={1,2,3}——我们将它们按字典顺序排列。
2. 该方法有一个隐式的0来开始第一个差值集。

词典顺序组合索引(麦卡弗里)

有另一种方式:，它的概念更容易掌握和编程，但它没有Buckles的优化。幸运的是，它也不会产生重复的组合:

集合< img src = " https://i.stack.imgur.com/Txetz.gif " alt = " xk……x_1 in N" />使< img src = " https://i.stack.imgur.com/HOj5o.gif " alt = " i = C (x_1 k) + C (x_2, k - 1) +…xk + C(1)”/>最大化，其中。

例如: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 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)

一个小而简单的组合迭代器

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

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

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

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

假设你的字母数组是这样的:"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 k


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

一旦j达到G, i也开始变化。

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

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

如果你可以使用SQL语法——比如，如果你使用LINQ访问一个结构或数组的字段，或者直接访问一个数据库，其中有一个名为“Alphabet”的表，只有一个字符字段“Letter”，你可以适应以下代码:

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个字母的组合，不管你在表格“字母表”中有多少个字母(它可以是3,8,10,27等)。

如果你想要的是所有的排列，而不是组合(也就是说，你想要“ACB”和“ABC”被视为不同的，而不是只出现一次)，只需删除最后一行(and一行)，就完成了。

编辑后:重新阅读问题后，我意识到需要的是一般算法，而不仅仅是选择3个项目的特定情况。Adam Hughes的答案是完整的，不幸的是我还不能投票。这个答案很简单，但只适用于你想要三样东西的时候。

下面的递归算法从有序集中选取所有k元素组合:

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

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

为了避免重复，您必须选择比i大的其余元素。这样[3,5]将只被选中一次，即[3]与[5]结合，而不是两次(该条件消除了[5]+[3])。没有这个条件，你得到的是变化而不是组合。

这是我的命题在c++

我尽可能少地限制迭代器类型，所以这个解决方案假设只有前向迭代器，它可以是const_iterator。这应该适用于任何标准容器。在参数没有意义的情况下，它抛出std:: invalid_argument

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

我有一个用于project euler的排列算法，在python中:

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

在Python中像Andrea Ambu一样，但没有硬编码为选择三个

def combinations(list, k):
"""Choose combinations of list, choosing k elements(no repeats)"""
if len(list) < k:
return []
else:
seq = [i for i in range(k)]
while seq:
print [list[index] for index in seq]
seq = get_next_combination(len(list), k, seq)


def get_next_combination(num_elements, k, seq):
index_to_move = find_index_to_move(num_elements, seq)
if index_to_move == None:
return None
else:
seq[index_to_move] += 1


#for every element past this sequence, move it down
for i, elem in enumerate(seq[(index_to_move+1):]):
seq[i + 1 + index_to_move] = seq[index_to_move] + i + 1


return seq


def find_index_to_move(num_elements, seq):
"""Tells which index should be moved"""
for rev_index, elem in enumerate(reversed(seq)):
if elem < (num_elements - rev_index - 1):
return len(seq) - rev_index - 1
return None

我在SQL Server 2005中创建了一个解决方案，并将其发布在我的网站上: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)

在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

在c#中:< / p >

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

下面是我最近用Java写的一段代码，它计算并返回从“outOf”元素中“num”元素的所有组合

// author: Sourabh Bhat (heySourabh@gmail.com)


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

下面是一些简单的代码，打印所有C(n,m)组合。它通过初始化和移动一组指向下一个有效组合的数组下标来工作。索引被初始化为指向最低的m个索引(按字典顺序是最小的组合)。然后，从第m个指标开始，我们试着向前移动指标。如果一个索引已经达到了它的极限，我们尝试前一个索引(一直到索引1)。如果我们可以向前移动一个索引，那么我们重置所有更大的索引

m=(rand()%n)+1; // m will vary from 1 to n


for (i=0;i<n;i++) a[i]=i+1;


// we want to print all possible C(n,m) combinations of selecting m objects out of n
printf("Printing C(%d,%d) possible combinations ...\n", n,m);


// This is an adhoc algo that keeps m pointers to the next valid combination
for (i=0;i<m;i++) p[i]=i; // the p[.] contain indices to the a vector whose elements constitute next combination


done=false;
while (!done)
{
// print combination
for (i=0;i<m;i++) printf("%2d ", a[p[i]]);
printf("\n");


// update combination
// method: start with p[m-1]. try to increment it. if it is already at the end, then try moving p[m-2] ahead.
// if this is possible, then reset p[m-1] to 1 more than (the new) p[m-2].
// if p[m-2] can not also be moved, then try p[m-3]. move that ahead. then reset p[m-2] and p[m-1].
// repeat all the way down to p[0]. if p[0] can not also be moved, then we have generated all combinations.
j=m-1;
i=1;
move_found=false;
while ((j>=0) && !move_found)
{
if (p[j]<(n-i))
{
move_found=true;
p[j]++; // point p[j] to next index
for (k=j+1;k<m;k++)
{
p[k]=p[j]+(k-j);
}
}
else
{
j--;
i++;
}
}
if (!move_found) done=true;
}

下面是一个优雅的Scala通用实现，如99 Scala问题所述

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 :: _}
}
}

我可以给出这个问题的递归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:], length-1):
yield (elements[i],) + next
def choose(l, k):
return list(choose_iter(l, k))

使用示例:

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

我喜欢它的简洁。

这里你有一个用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));
}
}

希望这对你有帮助!

Lisp宏为所有值r(一次取)

(defmacro txaat (some-list taken-at-a-time)
(let* ((vars (reverse (truncate-list '(a b c d e f g h i j) taken-at-a-time))))
`(
,@(loop for i below taken-at-a-time
for j in vars
with nested = nil
finally (return nested)
do
(setf
nested
`(loop for ,j from
,(if (< i (1- (length vars)))
`(1+ ,(nth (1+ i) vars))
0)
below (- (length ,some-list) ,i)
,@(if (equal i 0)
`(collect
(list
,@(loop for k from (1- taken-at-a-time) downto 0
append `((nth ,(nth k vars) ,some-list)))))
`(append ,nested))))))))

所以,

CL-USER> (macroexpand-1 '(txaat '(a b c d) 1))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 1)
COLLECT (LIST (NTH A '(A B C D))))
T
CL-USER> (macroexpand-1 '(txaat '(a b c d) 2))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 2)
APPEND (LOOP FOR B FROM (1+ A) TO (- (LENGTH '(A B C D)) 1)
COLLECT (LIST (NTH A '(A B C D)) (NTH B '(A B C D)))))
T
CL-USER> (macroexpand-1 '(txaat '(a b c d) 3))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 3)
APPEND (LOOP FOR B FROM (1+ A) TO (- (LENGTH '(A B C D)) 2)
APPEND (LOOP FOR C FROM (1+ B) TO (- (LENGTH '(A B C D)) 1)
COLLECT (LIST (NTH A '(A B C D))
(NTH B '(A B C D))
(NTH C '(A B C D))))))
T


CL-USER>

而且,

CL-USER> (txaat '(a b c d) 1)
((A) (B) (C) (D))
CL-USER> (txaat '(a b c d) 2)
((A B) (A C) (A D) (B C) (B D) (C D))
CL-USER> (txaat '(a b c d) 3)
((A B C) (A B D) (A C D) (B C D))
CL-USER> (txaat '(a b c d) 4)
((A B C D))
CL-USER> (txaat '(a b c d) 5)
NIL
CL-USER> (txaat '(a b c d) 0)
NIL
CL-USER>

我发现这个线程很有用，我想我会添加一个Javascript解决方案，你可以弹出到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");

输出如下:

abc
ab
ac
a
bc
b
c

下面是一个方法，它从一个随机长度的字符串中给出指定大小的所有组合。类似于quinmars的解，但适用于不同的输入和k。

代码可以更改为换行，即'dab'从输入'abcd' w k=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);
}
}

"abcde"的输出:

ABC abd ace ade BCD bce bde cde

在Python中，利用递归的优势和所有事情都是通过引用完成的事实。对于非常大的集合，这将占用大量内存，但其优点是初始集合可以是一个复杂的对象。

import copy


def find_combinations( length, set, combinations = None, candidate = None ):
# recursive function to calculate all unique combinations of unique values
# from [set], given combinations of [length].  The result is populated
# into the 'combinations' list.
#
if combinations == None:
combinations = []
if candidate == None:
candidate = []


for item in set:
if item in candidate:
# this item already appears in the current combination somewhere.
# skip it
continue


attempt = copy.deepcopy(candidate)
attempt.append(item)
# sorting the subset is what gives us completely unique combinations,
# so that [1, 2, 3] and [1, 3, 2] will be treated as equals
attempt.sort()


if len(attempt) < length:
# the current attempt at finding a new combination is still too
# short, so add another item to the end of the set
# yay recursion!
find_combinations( length, set, combinations, attempt )
else:
# the current combination attempt is the right length.  If it
# already appears in the list of found combinations then we'll
# skip it.
if attempt in combinations:
continue
else:
# otherwise, we append it to the list of found combinations
# and move on.
combinations.append(attempt)
continue
return len(combinations)

你可以这样使用它。传递'result'是可选的，所以你可以用它来获取可能组合的数量…尽管这样做效率很低(最好通过计算来完成)。

size = 3
set = [1, 2, 3, 4, 5]
result = []


num = find_combinations( size, set, result )
print "size %d results in %d sets" % (size, num)
print "result: %s" % (result,)

您应该从测试数据中得到以下输出:

size 3 results in 10 sets
result: [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]

如果你的集合是这样的，它也会工作得很好:

set = [
[ 'vanilla', 'cupcake' ],
[ 'chocolate', 'pudding' ],
[ 'vanilla', 'pudding' ],
[ 'chocolate', 'cookie' ],
[ 'mint', 'cookie' ]
]

Haskell中的简单递归算法

import Data.List


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

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

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

rest通过递归调用combinations从xs中选取n - 1元素。函数的最终结果是一个列表，其中每个元素都是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"]

这是一个递归程序，生成集合中nCk.Elements的组合，假设从1到n

#include<stdio.h>
#include<stdlib.h>


int nCk(int n,int loopno,int ini,int *a,int k)
{
static int count=0;
int i;
loopno--;
if(loopno<0)
{
a[k-1]=ini;
for(i=0;i<k;i++)
{
printf("%d,",a[i]);
}
printf("\n");
count++;
return 0;
}
for(i=ini;i<=n-loopno-1;i++)
{
a[k-1-loopno]=i+1;
nCk(n,loopno,i+1,a,k);
}
if(ini==0)
return count;
else
return 0;
}


void main()
{
int n,k,*a,count;
printf("Enter the value of n and k\n");
scanf("%d %d",&n,&k);
a=(int*)malloc(k*sizeof(int));
count=nCk(n,k,0,a,k);
printf("No of combinations=%d\n",count);
}

在VB。Net，该算法从一组数字(PoolArray)中收集n个数字的所有组合。例如，“8,10,20,33,41,44,47”中的5个选择的所有组合

Sub CreateAllCombinationsOfPicksFromPool(ByVal PicksArray() As UInteger, ByVal PicksIndex As UInteger, ByVal PoolArray() As UInteger, ByVal PoolIndex As UInteger)
If PicksIndex < PicksArray.Length Then
For i As Integer = PoolIndex To PoolArray.Length - PicksArray.Length + PicksIndex
PicksArray(PicksIndex) = PoolArray(i)
CreateAllCombinationsOfPicksFromPool(PicksArray, PicksIndex + 1, PoolArray, i + 1)
Next
Else
' completed combination. build your collections using PicksArray.
End If
End Sub


Dim PoolArray() As UInteger = Array.ConvertAll("8,10,20,33,41,44,47".Split(","), Function(u) UInteger.Parse(u))
Dim nPicks as UInteger = 5
Dim Picks(nPicks - 1) As UInteger
CreateAllCombinationsOfPicksFromPool(Picks, 0, PoolArray, 0)

由于没有提到编程语言，我假设列表也是可以的。下面是一个OCaml版本，适用于短列表(非尾递归)。给定一个由任何类型的元素组成的列表l < em > < / em >和一个整数< em > n < / em >，如果我们假设结果列表中元素的顺序被忽略，它将返回一个包含l < em > < / em >类型的< em > n < / em >元素的所有可能列表的列表，即列表['a';'b']与['b';'a']相同，并且将报告一次。因此，结果列表的大小将是((list。长度l)选择n).

递归的直观原理如下:取列表的头，然后进行两次递归调用:

• 递归调用1 (RC1):到列表的尾部，但选择n-1个元素
• 递归调用2 (RC2):到列表的尾部，但选择n个元素

要组合递归结果，list-乘(请使用奇数名称)列表的头部与RC1的结果，然后附加(@)RC2的结果。List-multiply是下面的操作lmul:

a lmul [ l1 ; l2 ; l3] = [a::l1 ; a::l2 ; a::l3]

lmul在下面的代码中实现为

List.map (fun x -> h::x)

当列表的大小等于您想要选择的元素数量时，递归将终止，在这种情况下，您只需返回列表本身。

下面是OCaml中实现上述算法的四行代码:

    let rec choose l n = match l, (List.length l) with
| _, lsize  when n==lsize  -> [l]
| h::t, _ -> (List.map (fun x-> h::x) (choose t (n-1))) @ (choose t n)
| [], _ -> []

这是我在javascript中的贡献(没有递归)

set = ["q0", "q1", "q2", "q3"]
collector = []




function comb(num) {
results = []
one_comb = []
for (i = set.length - 1; i >= 0; --i) {
tmp = Math.pow(2, i)
quotient = parseInt(num / tmp)
results.push(quotient)
num = num % tmp
}
k = 0
for (i = 0; i < results.length; ++i)
if (results[i]) {
++k
one_comb.push(set[i])
}
if (collector[k] == undefined)
collector[k] = []
collector[k].push(one_comb)
}




sum = 0
for (i = 0; i < set.length; ++i)
sum += Math.pow(2, i)
for (ii = sum; ii > 0; --ii)
comb(ii)
cnt = 0
for (i = 1; i < collector.length; ++i) {
n = 0
for (j = 0; j < collector[i].length; ++j)
document.write(++cnt, " - " + (++n) + " - ", collector[i][j], "<br>")
document.write("<hr>")
}

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

https://gist.github.com/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]]

void combine(char a[], int N, int M, int m, int start, char result[]) {
if (0 == m) {
for (int i = M - 1; i >= 0; i--)
std::cout << result[i];
std::cout << std::endl;
return;
}
for (int i = start; i < (N - m + 1); i++) {
result[m - 1] = a[i];
combine(a, N, M, m-1, i+1, result);
}
}


void combine(char a[], int N, int M) {
char *result = new char[M];
combine(a, N, M, M, 0, result);
delete[] result;
}

在第一个函数中，m表示还需要选择多少个，start表示必须从数组中的哪个位置开始选择。

我的实现在c/c++

#include <unistd.h>
#include <stdio.h>
#include <iconv.h>
#include <string.h>
#include <errno.h>
#include <stdlib.h>


int main(int argc, char **argv)
{
int opt = -1, min_len = 0, max_len = 0;
char ofile[256], fchar[2], tchar[2];
ofile[0] = 0;
fchar[0] = 0;
tchar[0] = 0;
while((opt = getopt(argc, argv, "o:f:t:l:L:")) != -1)
{
switch(opt)
{
case 'o':
strncpy(ofile, optarg, 255);
break;
case 'f':
strncpy(fchar, optarg, 1);
break;
case 't':
strncpy(tchar, optarg, 1);
break;
case 'l':
min_len = atoi(optarg);
break;
case 'L':
max_len = atoi(optarg);
break;
default:
printf("usage: %s -oftlL\n\t-o output file\n\t-f from char\n\t-t to char\n\t-l min seq len\n\t-L max seq len", argv[0]);
}
}
if(max_len < 1)
{
printf("error, length must be more than 0\n");
return 1;
}
if(min_len > max_len)
{
printf("error, max length must be greater or equal min_length\n");
return 1;
}
if((int)fchar[0] > (int)tchar[0])
{
printf("error, invalid range specified\n");
return 1;
}
FILE *out = fopen(ofile, "w");
if(!out)
{
printf("failed to open input file with error: %s\n", strerror(errno));
return 1;
}
int cur_len = min_len;
while(cur_len <= max_len)
{
char buf[cur_len];
for(int i = 0; i < cur_len; i++)
buf[i] = fchar[0];
fwrite(buf, cur_len, 1, out);
fwrite("\n", 1, 1, out);
while(buf[0] != (tchar[0]+1))
{
while(buf[cur_len-1] < tchar[0])
{
(int)buf[cur_len-1]++;
fwrite(buf, cur_len, 1, out);
fwrite("\n", 1, 1, out);
}
if(cur_len < 2)
break;
if(buf[0] == tchar[0])
{
bool stop = true;
for(int i = 1; i < cur_len; i++)
{
if(buf[i] != tchar[0])
{
stop = false;
break;
}
}
if(stop)
break;
}
int u = cur_len-2;
for(; u>=0 && buf[u] >= tchar[0]; u--)
;
(int)buf[u]++;
for(int i = u+1; i < cur_len; i++)
buf[i] = fchar[0];
fwrite(buf, cur_len, 1, out);
fwrite("\n", 1, 1, out);
}
cur_len++;
}
fclose(out);
return 0;
}

这里我的实现在c++，它写所有的组合到指定的文件，但行为可以改变，我在生成各种字典，它接受最小和最大长度和字符范围，目前只有ANSI支持，它足以满足我的需求

我已经编写了一个类来处理处理二项式系数的常见函数，这是您的问题属于的问题类型。它执行以下任务:

1. 将所有的K个索引以良好的格式输出到任意N选K的文件中。k索引可以用更具描述性的字符串或字母代替。这种方法使得解决这类问题相当简单。

2. 将k索引转换为已排序的二项式系数表中某项的适当索引。这种技术比以前发布的依赖迭代的技术要快得多。它通过使用帕斯卡三角形中固有的数学性质来做到这一点。我的论文谈到了这一点。我相信我是第一个发现并发表这种技术的人，但我也可能错了。

3. 将已排序的二项式系数表中的索引转换为相应的k索引。

4. 使用Mark Dominus方法来计算二项式系数，该方法不太可能溢出，并且适用于较大的数字。

5. 这个类是用。net c#编写的，它提供了一种方法来管理与问题相关的对象(如果有的话)，方法是使用一个通用列表。该类的构造函数接受一个名为InitTable的bool值，当该值为true时，将创建一个泛型列表来保存要管理的对象。如果该值为false，则不会创建表。执行上述4种方法不需要创建表。提供了访问器方法来访问表。

6. 有一个相关的测试类，它展示了如何使用类及其方法。它已经在2个案例中进行了广泛的测试，没有已知的错误。

要阅读这个类并下载代码，请参阅二项式系数的表化。

将这个类转换为c++应该不难。

现在又出现了祖辈COBOL，一种饱受诟病的语言。

让我们假设一个包含34个元素的数组，每个元素8个字节(完全是任意选择)。其思想是枚举所有可能的4元素组合，并将它们加载到一个数组中。

我们使用4个指标，每个指标代表4个组中的每个位置

数组是这样处理的:

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

我们改变idx4从4到结束。对于每个idx4，我们得到一个唯一的组合 四人一组。当idx4到达数组的末尾时，我们将idx3增加1，并将idx4设置为idx3+1。然后再次运行idx4到最后。我们以这种方式继续，分别增加idx3、idx2和idx1，直到idx1的位置距离数组末端小于4。

1          --- pos.1
2          --- pos 2
3          --- pos 3
4          --- pos 4
5
6
7
etc.

第一次迭代:

1234
1235
1236
1237
1245
1246
1247
1256
1257
1267
etc.

一个COBOL的例子:

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.

这个答案怎么样……这将打印所有长度为3的组合…它可以推广到任何长度… 工作代码…

#include<iostream>
#include<string>
using namespace std;


void combination(string a,string dest){
int l = dest.length();
if(a.empty() && l  == 3 ){
cout<<dest<<endl;}
else{
if(!a.empty() && dest.length() < 3 ){
combination(a.substr(1,a.length()),dest+a[0]);}
if(!a.empty() && dest.length() <= 3 ){
combination(a.substr(1,a.length()),dest);}
}


}


int main(){
string demo("abcd");
combination(demo,"");
return 0;
}

这里是一个Clojure版本，它使用了我在OCaml实现中描述的相同算法:

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

它提供了三种调用方法:

(一)恰好是n所选项目的问题要求:

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

n1和n2之间选择的项目:

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)用于在0和所选项目的集合大小之间:

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

短快C实现

#include <stdio.h>


void main(int argc, char *argv[]) {
const int n = 6; /* The size of the set; for {1, 2, 3, 4} it's 4 */
const int p = 4; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
int comb[40] = {0}; /* comb[i] is the index of the i-th element in the combination */


int i = 0;
for (int j = 0; j <= n; j++) comb[j] = 0;
while (i >= 0) {
if (comb[i] < n + i - p + 1) {
comb[i]++;
if (i == p - 1) { for (int j = 0; j < p; j++) printf("%d ", comb[j]); printf("\n"); }
else            { comb[++i] = comb[i - 1]; }
} else i--; }
}

要查看它有多快，请使用这段代码并测试它

#include <time.h>
#include <stdio.h>


void main(int argc, char *argv[]) {
const int n = 32; /* The size of the set; for {1, 2, 3, 4} it's 4 */
const int p = 16; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
int comb[40] = {0}; /* comb[i] is the index of the i-th element in the combination */


int c = 0; int i = 0;
for (int j = 0; j <= n; j++) comb[j] = 0;
while (i >= 0) {
if (comb[i] < n + i - p + 1) {
comb[i]++;
/* if (i == p - 1) { for (int j = 0; j < p; j++) printf("%d ", comb[j]); printf("\n"); } */
if (i == p - 1) c++;
else            { comb[++i] = comb[i - 1]; }
} else i--; }
printf("%d!%d == %d combination(s) in %15.3f second(s)\n ", p, n, c, clock()/1000.0);
}

使用cmd.exe (windows)测试:

Microsoft Windows XP [Version 5.1.2600]
(C) Copyright 1985-2001 Microsoft Corp.


c:\Program Files\lcc\projects>combination
16!32 == 601080390 combination(s) in          5.781 second(s)


c:\Program Files\lcc\projects>

祝你有愉快的一天。

简短的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]

还有另一个递归解决方案(你应该能够使用字母而不是数字)使用堆栈，虽然比大多数更短:

stack = []
def choose(n,x):
r(0,0,n+1,x)


def r(p, c, n,x):
if x-c == 0:
print stack
return


for i in range(p, n-(x-1)+c):
stack.append(i)
r(i+1,c+1,n,x)
stack.pop()

4选3或者我想要从0到4的所有3种数字组合

choose(4,3)


[0, 1, 2]
[0, 1, 3]
[0, 1, 4]
[0, 2, 3]
[0, 2, 4]
[0, 3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]

下面是coffeescript实现

combinations: (list, n) ->
permuations = Math.pow(2, list.length) - 1
out = []
combinations = []


while permuations
out = []


for i in [0..list.length]
y = ( 1 << i )
if( y & permuations and (y isnt permuations))
out.push(list[i])


if out.length <= n and out.length > 0
combinations.push(out)


permuations--


return combinations

这是我的Scala方案:

def combinations[A](s: List[A], k: Int): List[List[A]] =
if (k > s.length) Nil
else if (k == 1) s.map(List(_))
else combinations(s.tail, k - 1).map(s.head :: _) ::: combinations(s.tail, k)

#include <stdio.h>


unsigned int next_combination(unsigned int *ar, size_t n, unsigned int k)
{
unsigned int finished = 0;
unsigned int changed = 0;
unsigned int i;


if (k > 0) {
for (i = k - 1; !finished && !changed; i--) {
if (ar[i] < (n - 1) - (k - 1) + i) {
/* Increment this element */
ar[i]++;
if (i < k - 1) {
/* Turn the elements after it into a linear sequence */
unsigned int j;
for (j = i + 1; j < k; j++) {
ar[j] = ar[j - 1] + 1;
}
}
changed = 1;
}
finished = i == 0;
}
if (!changed) {
/* Reset to first combination */
for (i = 0; i < k; i++) {
ar[i] = i;
}
}
}
return changed;
}


typedef void(*printfn)(const void *, FILE *);


void print_set(const unsigned int *ar, size_t len, const void **elements,
const char *brackets, printfn print, FILE *fptr)
{
unsigned int i;
fputc(brackets[0], fptr);
for (i = 0; i < len; i++) {
print(elements[ar[i]], fptr);
if (i < len - 1) {
fputs(", ", fptr);
}
}
fputc(brackets[1], fptr);
}


int main(void)
{
unsigned int numbers[] = { 0, 1, 2 };
char *elements[] = { "a", "b", "c", "d", "e" };
const unsigned int k = sizeof(numbers) / sizeof(unsigned int);
const unsigned int n = sizeof(elements) / sizeof(const char*);


do {
print_set(numbers, k, (void*)elements, "[]", (printfn)fputs, stdout);
putchar('\n');
} while (next_combination(numbers, n, k));
getchar();
return 0;
}

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

为了解释，递归方法用下面的例子描述:

示例:A B C D E
所有3的组合将是:

• A与其余2的所有组合(B C D E)
• B与其余2的所有组合(C D E)
• C与其余2的所有组合(D E)

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

说了这么多，做了这么多，这就是奥卡姆的代码。 算法是显而易见的代码..

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

也许我错过了重点(你需要的是算法，而不是现成的解决方案)，但看起来scala已经开箱即用了:

def combis(str:String, k:Int):Array[String] = {
str.combinations(k).toArray
}

使用这样的方法:

  println(combis("abcd",2).toList)

会产生:

  List(ab, ac, ad, bc, bd, cd)

简短快速的c#实现

public static IEnumerable<IEnumerable<T>> Combinations<T>(IEnumerable<T> elements, int k)
{
return Combinations(elements.Count(), k).Select(p => p.Select(q => elements.ElementAt(q)));
}


public static List<int[]> Combinations(int setLenght, int subSetLenght) //5, 3
{
var result = new List<int[]>();


var lastIndex = subSetLenght - 1;
var dif = setLenght - subSetLenght;
var prevSubSet = new int[subSetLenght];
var lastSubSet = new int[subSetLenght];
for (int i = 0; i < subSetLenght; i++)
{
prevSubSet[i] = i;
lastSubSet[i] = i + dif;
}


while(true)
{
//add subSet ad result set
var n = new int[subSetLenght];
for (int i = 0; i < subSetLenght; i++)
n[i] = prevSubSet[i];


result.Add(n);


if (prevSubSet[0] >= lastSubSet[0])
break;


//start at index 1 because index 0 is checked and breaking in the current loop
int j = 1;
for (; j < subSetLenght; j++)
{
if (prevSubSet[j] >= lastSubSet[j])
{
prevSubSet[j - 1]++;


for (int p = j; p < subSetLenght; p++)
prevSubSet[p] = prevSubSet[p - 1] + 1;


break;
}
}


if (j > lastIndex)
prevSubSet[lastIndex]++;
}


return result;
}

一个简洁的Javascript解决方案:

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

这是一个c++解决方案，我提出使用递归和位移位。

void r_nCr(unsigned int startNum, unsigned int bitVal, unsigned int testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
unsigned int n = (startNum - bitVal) << 1;
n += bitVal ? 1 : 0;


for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
cout << (n >> (i - 1) & 1);
cout << endl;


if (!(n & testNum) && n != startNum)
r_nCr(n, bitVal, testNum);


if (bitVal && bitVal < testNum)
r_nCr(startNum, bitVal >> 1, testNum);
}

您可以在在这里中找到这是如何工作的解释。

c#简单算法。 (我发布它是因为我试图使用你们上传的那个，但由于某种原因我无法编译它——扩展一个类?所以我自己写了一个，以防别人遇到和我一样的问题)。 顺便说一下，除了基本的编程，我对c#并不太感兴趣，但这个工作得很好

public static List<List<int>> GetSubsetsOfSizeK(List<int> lInputSet, int k)
{
List<List<int>> lSubsets = new List<List<int>>();
GetSubsetsOfSizeK_rec(lInputSet, k, 0, new List<int>(), lSubsets);
return lSubsets;
}


public static void GetSubsetsOfSizeK_rec(List<int> lInputSet, int k, int i, List<int> lCurrSet, List<List<int>> lSubsets)
{
if (lCurrSet.Count == k)
{
lSubsets.Add(lCurrSet);
return;
}


if (i >= lInputSet.Count)
return;


List<int> lWith = new List<int>(lCurrSet);
List<int> lWithout = new List<int>(lCurrSet);
lWith.Add(lInputSet[i++]);


GetSubsetsOfSizeK_rec(lInputSet, k, i, lWith, lSubsets);
GetSubsetsOfSizeK_rec(lInputSet, k, i, lWithout, lSubsets);
}

用法:# EYZ0

您可以修改它以遍历您正在处理的任何内容。

好运！

短php算法返回所有k元素的组合从n(二项式系数)基于java解决方案:

$array = array(1,2,3,4,5);


$array_result = NULL;


$array_general = NULL;


function combinations($array, $len, $start_position, $result_array, $result_len, &$general_array)
{
if($len == 0)
{
$general_array[] = $result_array;
return;
}


for ($i = $start_position; $i <= count($array) - $len; $i++)
{
$result_array[$result_len - $len] = $array[$i];
combinations($array, $len-1, $i+1, $result_array, $result_len, $general_array);
}
}


combinations($array, 3, 0, $array_result, 3, $array_general);


echo "<pre>";
print_r($array_general);
echo "</pre>";

相同的解决方案，但在javascript:

var newArray = [1, 2, 3, 4, 5];
var arrayResult = [];
var arrayGeneral = [];


function combinations(newArray, len, startPosition, resultArray, resultLen, arrayGeneral) {
if(len === 0) {
var tempArray = [];
resultArray.forEach(value => tempArray.push(value));
arrayGeneral.push(tempArray);
return;
}
for (var i = startPosition; i <= newArray.length - len; i++) {
resultArray[resultLen - len] = newArray[i];
combinations(newArray, len-1, i+1, resultArray, resultLen, arrayGeneral);
}
}


combinations(newArray, 3, 0, arrayResult, 3, arrayGeneral);


console.log(arrayGeneral);

这是我想出的解决这个问题的算法。它是用c++编写的，但可以适应几乎任何支持位操作的语言

void r_nCr(const unsigned int &startNum, const unsigned int &bitVal, const unsigned int &testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
unsigned int n = (startNum - bitVal) << 1;
n += bitVal ? 1 : 0;


for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
cout << (n >> (i - 1) & 1);
cout << endl;


if (!(n & testNum) && n != startNum)
r_nCr(n, bitVal, testNum);


if (bitVal && bitVal < testNum)
r_nCr(startNum, bitVal >> 1, testNum);
}

您可以看到它如何工作的解释在这里。

简短的python代码，产生索引位置

def yield_combos(n,k):
# n is set size, k is combo size


i = 0
a = [0]*k


while i > -1:
for j in range(i+1, k):
a[j] = a[j-1]+1
i=j
yield a
while a[i] == i + n - k:
i -= 1
a[i] += 1

另一个具有组合索引惰性生成的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;
}
}
}

测试代码:

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

输出:

a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e

下面是我的JavaScript解决方案，通过使用reduce/map，它消除了几乎所有变量，功能更强大

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;

计算机编程的艺术，卷4A:组合算法，第1部分第7.2.1.3节中算法L(字典组合)的C代码:

#include <stdio.h>
#include <stdlib.h>


void visit(int* c, int t)
{
// for (int j = 1; j <= t; j++)
for (int j = t; j > 0; j--)
printf("%d ", c[j]);
printf("\n");
}


int* initialize(int n, int t)
{
// c[0] not used
int *c = (int*) malloc((t + 3) * sizeof(int));


for (int j = 1; j <= t; j++)
c[j] = j - 1;
c[t+1] = n;
c[t+2] = 0;
return c;
}


void comb(int n, int t)
{
int *c = initialize(n, t);
int j;


for (;;) {
visit(c, t);
j = 1;
while (c[j]+1 == c[j+1]) {
c[j] = j - 1;
++j;
}
if (j > t)
return;
++c[j];
}
free(c);
}


int main(int argc, char *argv[])
{
comb(5, 3);
return 0;
}

赶时髦，发布另一个解决方案。这是一个通用的Java实现。输入:(int k)是要选择的元素数量，(List<T> list)是要选择的列表。返回(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;
}

递归地，一个非常简单的答案，combo，在Free Pascal中。

    procedure combinata (n, k :integer; producer :oneintproc);


procedure combo (ndx, nbr, len, lnd :integer);
begin
for nbr := nbr to len do begin
productarray[ndx] := nbr;
if len < lnd then
combo(ndx+1,nbr+1,len+1,lnd)
else
producer(k);
end;
end;


begin
combo (0, 0, n-k, n-1);
end;

“producer”处理为每个组合生成的产品数组。

我正在为PHP寻找类似的解决方案，遇到了以下情况

class Combinations implements Iterator
{
protected $c = null;
protected $s = null;
protected $n = 0;
protected $k = 0;
protected $pos = 0;


function __construct($s, $k) {
if(is_array($s)) {
$this->s = array_values($s);
$this->n = count($this->s);
} else {
$this->s = (string) $s;
$this->n = strlen($this->s);
}
$this->k = $k;
$this->rewind();
}
function key() {
return $this->pos;
}
function current() {
$r = array();
for($i = 0; $i < $this->k; $i++)
$r[] = $this->s[$this->c[$i]];
return is_array($this->s) ? $r : implode('', $r);
}
function next() {
if($this->_next())
$this->pos++;
else
$this->pos = -1;
}
function rewind() {
$this->c = range(0, $this->k);
$this->pos = 0;
}
function valid() {
return $this->pos >= 0;
}


protected function _next() {
$i = $this->k - 1;
while ($i >= 0 && $this->c[$i] == $this->n - $this->k + $i)
$i--;
if($i < 0)
return false;
$this->c[$i]++;
while($i++ < $this->k - 1)
$this->c[$i] = $this->c[$i - 1] + 1;
return true;
}
}




foreach(new Combinations("1234567", 5) as $substring)
echo $substring, ' ';

< a href = " https://stackoverflow.com/a/3742837/563247 " > < / >来源

我不确定这个类有多高效，但我只是把它用作种子程序。

不需要进行集合操作。这个问题几乎和循环K个嵌套循环一样，但你必须小心索引和边界(忽略Java和OOP的东西):

 public class CombinationsGen {
private final int n;
private final int k;
private int[] buf;


public CombinationsGen(int n, int k) {
this.n = n;
this.k = k;
}


public void combine(Consumer<int[]> consumer) {
buf = new int[k];
rec(0, 0, consumer);
}


private void rec(int index, int next, Consumer<int[]> consumer) {
int max = n - index;


if (index == k - 1) {
for (int i = 0; i < max && next < n; i++) {
buf[index] = next;
next++;
consumer.accept(buf);
}
} else {
for (int i = 0; i < max && next + index < n; i++) {
buf[index] = next;
next++;
rec(index + 1, next, consumer);
}
}
}
}

像这样使用:

 CombinationsGen gen = new CombinationsGen(5, 2);


AtomicInteger total = new AtomicInteger();
gen.combine(arr -> {
System.out.println(Arrays.toString(arr));
total.incrementAndGet();
});
System.out.println(total);

获得预期的结果:

[0, 1]
[0, 2]
[0, 3]
[0, 4]
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
10

最后，将索引映射到您可能拥有的任何数据集。

public class Combinations {
final int pos[];
final List<Object> set;


public Combinations(List<?> l, int k) {
pos = new int[k];
set=new ArrayList<Object>(l);
reset();
}
public void reset() {
for (int i=0; i < pos.length; ++i) pos[i]=i;
}
public boolean next() {
int i = pos.length-1;
for (int maxpos = set.size()-1; pos[i] >= maxpos; --maxpos) {
if (i==0) return false;
--i;
}
++pos[i];
while (++i < pos.length)
pos[i]=pos[i-1]+1;
return true;
}


public void getSelection(List<?> l) {
@SuppressWarnings("unchecked")
List<Object> ll = (List<Object>)l;
if (ll.size()!=pos.length) {
ll.clear();
for (int i=0; i < pos.length; ++i)
ll.add(set.get(pos[i]));
}
else {
for (int i=0; i < pos.length; ++i)
ll.set(i, set.get(pos[i]));
}
}
}

用法示例:

static void main(String[] args) {
List<Character> l = new ArrayList<Character>();
for (int i=0; i < 32; ++i) l.add((char)('a'+i));
Combinations comb = new Combinations(l,5);
int n=0;
do {
++n;
comb.getSelection(l);
//Log.debug("%d: %s", n, l.toString());
} while (comb.next());
Log.debug("num = %d", n);
}

简单但缓慢的c++回溯算法。

#include <iostream>


void backtrack(int* numbers, int n, int k, int i, int s)
{
if (i == k)
{
for (int j = 0; j < k; ++j)
{
std::cout << numbers[j];
}
std::cout << std::endl;


return;
}


if (s > n)
{
return;
}


numbers[i] = s;
backtrack(numbers, n, k, i + 1, s + 1);
backtrack(numbers, n, k, i, s + 1);
}


int main(int argc, char* argv[])
{
int n = 5;
int k = 3;


int* numbers = new int[k];


backtrack(numbers, n, k, 0, 1);


delete[] numbers;


return 0;
}

用c#的另一个解决方案:

 static List<List<T>> GetCombinations<T>(List<T> originalItems, int combinationLength)
{
if (combinationLength < 1)
{
return null;
}


return CreateCombinations<T>(new List<T>(), 0, combinationLength, originalItems);
}


static List<List<T>> CreateCombinations<T>(List<T> initialCombination, int startIndex, int length, List<T> originalItems)
{
List<List<T>> combinations = new List<List<T>>();
for (int i = startIndex; i < originalItems.Count - length + 1; i++)
{
List<T> newCombination = new List<T>(initialCombination);
newCombination.Add(originalItems[i]);
if (length > 1)
{
List<List<T>> newCombinations = CreateCombinations(newCombination, i + 1, length - 1, originalItems);
combinations.AddRange(newCombinations);
}
else
{
combinations.Add(newCombination);
}
}


return combinations;
}

用法示例:

   List<char> initialArray = new List<char>() { 'a','b','c','d'};
int combinationLength = 3;
List<List<char>> combinations = GetCombinations(initialArray, combinationLength);

算法:

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

在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部分。)

(有关证明，请参阅麻省理工学院免费课件计算机科学数学，雷曼等，第11.2.2节。# EYZ0)

假设你的字母数组是这样的:"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 k


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

一旦j达到G, 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);

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

我们可以用比特的概念来做这个。假设我们有一个字符串“abc”，我们想要所有长度为2的元素的组合(即“ab”，“ac”，“bc”)。

我们可以在1到2^n(排他性)的数字中找到集合位。这里是1到7，只要我们设置了bits = 2，我们就可以从string中输出相应的值。

例如:

• 1 - 001
• 2 - 010
• 3 - 011 -> # eyz0
• 4 - 100
• 5 - 101 -> # eyz0
• 6 - 110 -> # eyz0
• 7 - 111。

public class StringCombinationK {
static void combk(String s , int k){
int n = s.length();
int num = 1<<n;
int j=0;
int count=0;


for(int i=0;i<num;i++){
if (countSet(i)==k){
setBits(i,j,s);
count++;
System.out.println();
}
}


System.out.println(count);
}


static void setBits(int i,int j,String s){ // print the corresponding string value,j represent the index of set bit
if(i==0){
return;
}


if(i%2==1){
System.out.print(s.charAt(j));
}


setBits(i/2,j+1,s);
}


static int countSet(int i){ //count number of set bits
if( i==0){
return 0;
}


return (i%2==0? 0:1) + countSet(i/2);
}


public static void main(String[] arhs){
String s = "abcdefgh";
int k=3;
combk(s,k);
}
}

char ar[] = "0ABCDEFGH";
nCr ncr(8, 3);
while(ncr.next()) {
for(int i=0; i<ncr.size(); i++) cout << ar[ncr[i]];
cout << ' ';
}

结果

下面是头文件。

#pragma once
#include <exception>


class NRexception : public std::exception
{
public:
virtual const char* what() const throw() {
return "Combination : N, R should be positive integer!!";
}
};


class Combination
{
public:
Combination(int n, int r);
virtual ~Combination() { delete [] ar;}
int& operator[](unsigned i) {return ar[i];}
bool next();
int size() {return r;}
static int factorial(int n);


protected:
int* ar;
int n, r;
};


class nCr : public Combination
{
public:
nCr(int n, int r);
bool next();
int count() const;
};


class nTr : public Combination
{
public:
nTr(int n, int r);
bool next();
int count() const;
};


class nHr : public nTr
{
public:
nHr(int n, int r) : nTr(n,r) {}
bool next();
int count() const;
};


class nPr : public Combination
{
public:
nPr(int n, int r);
virtual ~nPr() {delete [] on;}
bool next();
void rewind();
int count() const;


private:
bool* on;
void inc_ar(int i);
};

以及执行。

#include "combi.h"
#include <set>
#include<cmath>


Combination::Combination(int n, int r)
{
//if(n < 1 || r < 1) throw NRexception();
ar = new int[r];
this->n = n;
this->r = r;
}


int Combination::factorial(int n)
{
return n == 1 ? n : n * factorial(n-1);
}


int nPr::count() const
{
return factorial(n)/factorial(n-r);
}


int nCr::count() const
{
return factorial(n)/factorial(n-r)/factorial(r);
}


int nTr::count() const
{
return pow(n, r);
}


int nHr::count() const
{
return factorial(n+r-1)/factorial(n-1)/factorial(r);
}


nCr::nCr(int n, int r) : Combination(n, r)
{
if(r == 0) return;
for(int i=0; i<r-1; i++) ar[i] = i + 1;
ar[r-1] = r-1;
}


nTr::nTr(int n, int r) : Combination(n, r)
{
for(int i=0; i<r-1; i++) ar[i] = 1;
ar[r-1] = 0;
}


bool nCr::next()
{
if(r == 0) return false;
ar[r-1]++;
int i = r-1;
while(ar[i] == n-r+2+i) {
if(--i == -1) return false;
ar[i]++;
}
while(i < r-1) ar[i+1] = ar[i++] + 1;
return true;
}


bool nTr::next()
{
ar[r-1]++;
int i = r-1;
while(ar[i] == n+1) {
ar[i] = 1;
if(--i == -1) return false;
ar[i]++;
}
return true;
}


bool nHr::next()
{
ar[r-1]++;
int i = r-1;
while(ar[i] == n+1) {
if(--i == -1) return false;
ar[i]++;
}
while(i < r-1) ar[i+1] = ar[i++];
return true;
}


nPr::nPr(int n, int r) : Combination(n, r)
{
on = new bool[n+2];
for(int i=0; i<n+2; i++) on[i] = false;
for(int i=0; i<r; i++) {
ar[i] = i + 1;
on[i] = true;
}
ar[r-1] = 0;
}


void nPr::rewind()
{
for(int i=0; i<r; i++) {
ar[i] = i + 1;
on[i] = true;
}
ar[r-1] = 0;
}


bool nPr::next()
{
inc_ar(r-1);


int i = r-1;
while(ar[i] == n+1) {
if(--i == -1) return false;
inc_ar(i);
}
while(i < r-1) {
ar[++i] = 0;
inc_ar(i);
}
return true;
}


void nPr::inc_ar(int i)
{
on[ar[i]] = false;
while(on[++ar[i]]);
if(ar[i] != n+1) on[ar[i]] = true;
}

作为迭代器对象实现的MetaTrader MQL4非常快速的组合。

代码很容易理解。

我对很多算法进行了基准测试，这个算法真的非常快——大约比大多数next_combination()函数快3倍。

class CombinationsIterator
{
private:
int input_array[];  // 1 2 3 4 5
int index_array[];  // i j k
int m_elements;     // N
int m_indices;      // K


public:
CombinationsIterator(int &src_data[], int k)
{
m_indices = k;
m_elements = ArraySize(src_data);
ArrayCopy(input_array, src_data);
ArrayResize(index_array, m_indices);


// create initial combination (0..k-1)
for (int i = 0; i < m_indices; i++)
{
index_array[i] = i;
}
}


// https://stackoverflow.com/questions/5076695
// bool next_combination(int &item[], int k, int N)
bool advance()
{
int N = m_elements;
for (int i = m_indices - 1; i >= 0; --i)
{
if (index_array[i] < --N)
{
++index_array[i];
for (int j = i + 1; j < m_indices; ++j)
{
index_array[j] = index_array[j - 1] + 1;
}
return true;
}
}
return false;
}


void getItems(int &items[])
{
// fill items[] from input array
for (int i = 0; i < m_indices; i++)
{
items[i] = input_array[index_array[i]];
}
}
};

测试上述迭代器类的驱动程序:

//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
// driver program to test above class


#define N 5
#define K 3


void OnStart()
{
int myset[N] = {1, 2, 3, 4, 5};
int items[K];


CombinationsIterator comboIt(myset, K);


do
{
comboIt.getItems(items);


printf("%s", ArrayToString(items));


} while (comboIt.advance());


}

Output:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

这是一个简单的JS解决方案:

function getAllCombinations(n, k, f1) {
indexes = Array(k);
for (let i =0; i< k; i++) {
indexes[i] = i;
}
var total = 1;
f1(indexes);
while (indexes[0] !== n-k) {
total++;
getNext(n, indexes);
f1(indexes);
}
return {total};
}


function getNext(n, vec) {
const k = vec.length;
vec[k-1]++;
for (var i=0; i<k; i++) {
var currentIndex = k-i-1;
if (vec[currentIndex] === n - i) {
var nextIndex = k-i-2;
vec[nextIndex]++;
vec[currentIndex] = vec[nextIndex] + 1;
}
}


for (var i=1; i<k; i++) {
if (vec[i] === n - (k-i - 1)) {
vec[i] = vec[i-1] + 1;
}
}
return vec;
}






let start = new Date();
let result = getAllCombinations(10, 3, indexes => console.log(indexes));
let runTime = new Date() - start;


console.log({
result, runTime
});

下面是一个使用宏的Lisp方法。这适用于Common Lisp，也适用于其他Lisp方言。

下面的代码创建了“n”个嵌套循环，并为列表lst中的“n”个元素的每个组合执行任意代码块(存储在body变量中)。变量var指向一个包含用于循环的变量的列表。

(defmacro do-combinations ((var lst num) &body body)
(loop with syms = (loop repeat num collect (gensym))
for i on syms
for k = `(loop for ,(car i) on (cdr ,(cadr i))
do (let ((,var (list ,@(reverse syms)))) (progn ,@body)))
then `(loop for ,(car i) on ,(if (cadr i) `(cdr ,(cadr i)) lst) do ,k)
finally (return k)))

让我们看看…

(macroexpand-1 '(do-combinations (p '(1 2 3 4 5 6 7) 4) (pprint (mapcar #'car p))))


(LOOP FOR #:G3217 ON '(1 2 3 4 5 6 7) DO
(LOOP FOR #:G3216 ON (CDR #:G3217) DO
(LOOP FOR #:G3215 ON (CDR #:G3216) DO
(LOOP FOR #:G3214 ON (CDR #:G3215) DO
(LET ((P (LIST #:G3217 #:G3216 #:G3215 #:G3214)))
(PROGN (PPRINT (MAPCAR #'CAR P))))))))


(do-combinations (p '(1 2 3 4 5 6 7) 4) (pprint (mapcar #'car p)))


(1 2 3 4)
(1 2 3 5)
(1 2 3 6)
...

由于默认情况下不存储组合，因此存储空间保持在最小值。选择body代码而不是存储所有结果的可能性也提供了更大的灵活性。

遵循Haskell代码计算同时进行组合数和组合，由于Haskell的懒惰，您可以得到其中的一部分而无需计算另一部分。

import Data.Semigroup
import Data.Monoid


data Comb = MkComb {count :: Int, combinations :: [[Int]]} deriving (Show, Eq, Ord)


instance Semigroup Comb where
(MkComb c1 cs1) <> (MkComb c2 cs2) = MkComb (c1 + c2) (cs1 ++ cs2)


instance Monoid Comb where
mempty = MkComb 0 []


addElem :: Comb -> Int -> Comb
addElem (MkComb c cs) x = MkComb c (map (x :) cs)


comb :: Int -> Int -> Comb
comb n k | n < 0 || k < 0 = error "error in `comb n k`, n and k should be natural number"
comb n k | k == 0 || k == n = MkComb 1 [(take k [k-1,k-2..0])]
comb n k | n < k = mempty
comb n k = comb (n-1) k <> (comb (n-1) (k-1) `addElem` (n-1))

它是这样工作的:

*Main> comb 0 1
MkComb {count = 0, combinations = []}


*Main> comb 0 0
MkComb {count = 1, combinations = [[]]}


*Main> comb 1 1
MkComb {count = 1, combinations = [[0]]}


*Main> comb 4 2
MkComb {count = 6, combinations = [[1,0],[2,0],[2,1],[3,0],[3,1],[3,2]]}


*Main> count (comb 10 5)
252

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>

我知道这个问题已经有很多答案了，但我想在JavaScript中添加我自己的贡献，它由两个函数组成——一个生成原始n元素集的所有可能不同的k子集，另一个使用第一个函数生成原始n元素集的幂集。

下面是这两个函数的代码:

//Generate combination subsets from a base set of elements (passed as an array). This function should generate an
//array containing nCr elements, where nCr = n!/[r! (n-r)!].


//Arguments:


//[1] baseSet :     The base set to create the subsets from (e.g., ["a", "b", "c", "d", "e", "f"])
//[2] cnt :         The number of elements each subset is to contain (e.g., 3)


function MakeCombinationSubsets(baseSet, cnt)
{
var bLen = baseSet.length;
var indices = [];
var subSet = [];
var done = false;
var result = [];        //Contains all the combination subsets generated
var done = false;
var i = 0;
var idx = 0;
var tmpIdx = 0;
var incr = 0;
var test = 0;
var newIndex = 0;
var inBounds = false;
var tmpIndices = [];
var checkBounds = false;


//First, generate an array whose elements are indices into the base set ...


for (i=0; i<cnt; i++)


indices.push(i);


//Now create a clone of this array, to be used in the loop itself ...


tmpIndices = [];


tmpIndices = tmpIndices.concat(indices);


//Now initialise the loop ...


idx = cnt - 1;      //point to the last element of the indices array
incr = 0;
done = false;
while (!done)
{
//Create the current subset ...


subSet = [];    //Make sure we begin with a completely empty subset before continuing ...


for (i=0; i<cnt; i++)


subSet.push(baseSet[tmpIndices[i]]);    //Create the current subset, using items selected from the
//base set, using the indices array (which will change as we
//continue scanning) ...


//Add the subset thus created to the result set ...


result.push(subSet);


//Now update the indices used to select the elements of the subset. At the start, idx will point to the
//rightmost index in the indices array, but the moment that index moves out of bounds with respect to the
//base set, attention will be shifted to the next left index.


test = tmpIndices[idx] + 1;


if (test >= bLen)
{
//Here, we're about to move out of bounds with respect to the base set. We therefore need to scan back,
//and update indices to the left of the current one. Find the leftmost index in the indices array that
//isn't going to  move out of bounds with respect to the base set ...


tmpIdx = idx - 1;
incr = 1;


inBounds = false;       //Assume at start that the index we're checking in the loop below is out of bounds
checkBounds = true;


while (checkBounds)
{
if (tmpIdx < 0)
{
checkBounds = false;    //Exit immediately at this point
}
else
{
newIndex = tmpIndices[tmpIdx] + 1;
test = newIndex + incr;


if (test >= bLen)
{
//Here, incrementing the current selected index will take that index out of bounds, so
//we move on to the next index to the left ...


tmpIdx--;
incr++;
}
else
{
//Here, the index will remain in bounds if we increment it, so we
//exit the loop and signal that we're in bounds ...


inBounds = true;
checkBounds = false;


//End if/else
}


//End if
}
//End while
}
//At this point, if we'er still in bounds, then we continue generating subsets, but if not, we abort immediately.


if (!inBounds)
done = true;
else
{
//Here, we're still in bounds. We need to update the indices accordingly. NOTE: at this point, although a
//left positioned index in the indices array may still be in bounds, incrementing it to generate indices to
//the right may take those indices out of bounds. We therefore need to check this as we perform the index
//updating of the indices array.


tmpIndices[tmpIdx] = newIndex;


inBounds = true;
checking = true;
i = tmpIdx + 1;


while (checking)
{
test = tmpIndices[i - 1] + 1;   //Find out if incrementing the left adjacent index takes it out of bounds


if (test >= bLen)
{
inBounds = false;           //If we move out of bounds, exit NOW ...
checking = false;
}
else
{
tmpIndices[i] = test;       //Otherwise, update the indices array ...


i++;                        //Now move on to the next index to the right in the indices array ...


checking = (i < cnt);       //And continue until we've exhausted all the indices array elements ...
//End if/else
}
//End while
}
//At this point, if the above updating of the indices array has moved any of its elements out of bounds,
//we abort subset construction from this point ...
if (!inBounds)
done = true;
//End if/else
}
}
else
{
//Here, the rightmost index under consideration isn't moving out of bounds with respect to the base set when
//we increment it, so we simply increment and continue the loop ...
tmpIndices[idx] = test;
//End if
}
//End while
}
return(result);
//End function
}




function MakePowerSet(baseSet)
{
var bLen = baseSet.length;
var result = [];
var i = 0;
var partialSet = [];


result.push([]);    //add the empty set to the power set


for (i=1; i<bLen; i++)
{
partialSet = MakeCombinationSubsets(baseSet, i);
result = result.concat(partialSet);
//End i loop
}
//Now, finally, add the base set itself to the power set to make it complete ...


partialSet = [];
partialSet.push(baseSet);
result = result.concat(partialSet);


return(result);
//End function
}

我用集合["a"， "b"， "c"， "d"， "e"， "f"]作为基本集进行了测试，并运行代码以产生以下幂集:

[]
["a"]
["b"]
["c"]
["d"]
["e"]
["f"]
["a","b"]
["a","c"]
["a","d"]
["a","e"]
["a","f"]
["b","c"]
["b","d"]
["b","e"]
["b","f"]
["c","d"]
["c","e"]
["c","f"]
["d","e"]
["d","f"]
["e","f"]
["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"]
["a","b","c","d"]
["a","b","c","e"]
["a","b","c","f"]
["a","b","d","e"]
["a","b","d","f"]
["a","b","e","f"]
["a","c","d","e"]
["a","c","d","f"]
["a","c","e","f"]
["a","d","e","f"]
["b","c","d","e"]
["b","c","d","f"]
["b","c","e","f"]
["b","d","e","f"]
["c","d","e","f"]
["a","b","c","d","e"]
["a","b","c","d","f"]
["a","b","c","e","f"]
["a","b","d","e","f"]
["a","c","d","e","f"]
["b","c","d","e","f"]
["a","b","c","d","e","f"]

只要复制和粘贴这两个函数，你就有了提取n元素集的不同k子集所需的基本知识，如果你愿意，而且生成n元素集的幂集。

我并不是说这很优雅，只是说它在经过大量的测试(并在调试阶段将空气变为蓝色:)之后可以工作。

简短javascript版本(es5)

let combine = (list, n) =>
n == 0 ?
[[]] :
list.flatMap((e, i) =>
combine(
list.slice(i + 1),
n - 1
).map(c => [e].concat(c))
);


let res = combine([1,2,3,4], 3);
res.forEach(e => console.log(e.join()));

下面是一个c++中的迭代算法，不使用的STL既不递归也不条件嵌套循环。这样更快，它不执行任何元素交换，也不会给堆栈带来递归负担，也可以通过分别用new、delete和std::cout替换mallloc()、free()和printf()轻松移植到ANSI C

如果您想显示字母不同或更长的元素，则更改*alphabet参数以指向与"abcdefg"不同的字符串。

void OutputArrayChar(unsigned int* ka, size_t n, const char *alphabet) {
for (int i = 0; i < n; i++)
std::cout << alphabet[ka[i]] << ",";
std::cout << endl;
}
    



void GenCombinations(const unsigned int N, const unsigned int K, const char *alphabet) {
unsigned int *ka = new unsigned int [K];  //dynamically allocate an array of UINTs
unsigned int ki = K-1;                    //Point ki to the last elemet of the array
ka[ki] = N-1;                             //Prime the last elemet of the array.
    

while (true) {
unsigned int tmp = ka[ki];  //Optimization to prevent reading ka[ki] repeatedly


while (ki)                  //Fill to the left with consecutive descending values (blue squares)
ka[--ki] = --tmp;
OutputArrayChar(ka, K, alphabet);
    

while (--ka[ki] == ki) {    //Decrement and check if the resulting value equals the index (bright green squares)
OutputArrayChar(ka, K, alphabet);
if (++ki == K) {      //Exit condition (all of the values in the array are flush to the left)
delete[] ka;
return;
}
}
}
}
    



int main(int argc, char *argv[])
{
GenCombinations(7, 4, "abcdefg");
return 0;
}

重要提示:*alphabet参数必须指向至少有N个字符的字符串。你也可以传递一个在其他地方定义的字符串地址。

组合:Out of "7选择4; # EYZ0 < / p >

下面是一个简单易懂的递归c++解决方案:

#include<vector>
using namespace std;


template<typename T>
void ksubsets(const vector<T>& arr, unsigned left, unsigned idx,
vector<T>& lst, vector<vector<T>>& res)
{
if (left < 1) {
res.push_back(lst);
return;
}
for (unsigned i = idx; i < arr.size(); i++) {
lst.push_back(arr[i]);
ksubsets(arr, left - 1, i + 1, lst, res);
lst.pop_back();
}
}


int main()
{
vector<int> arr = { 1, 2, 3, 4, 5 };
unsigned left = 3;
vector<int> lst;
vector<vector<int>> res;
ksubsets<int>(arr, left, 0, lst, res);
// now res has all the combinations
}

另一种python递归解决方案。

def combination_indicies(n, k, j = 0, stack = []):
if len(stack) == k:
yield list(stack)
return
        

for i in range(j, n):
stack.append(i)
for x in combination_indicies(n, k, i + 1, stack):
yield x
stack.pop()
        

list(combination_indicies(5, 3))

输出:

[[0, 1, 2],
[0, 1, 3],
[0, 1, 4],
[0, 2, 3],
[0, 2, 4],
[0, 3, 4],
[1, 2, 3],
[1, 2, 4],
[1, 3, 4],
[2, 3, 4]]

最近在IronScripter网站上有一个PowerShell挑战，需要一个n-选择k的解决方案。我在那里发布了一个解决方案，但这里有一个更通用的版本。

• AllK开关用于控制输出是长度为ChooseK的组合，还是长度为1到ChooseK的组合。
• Prefix参数实际上是输出字符串的累加器，但其效果是为初始调用传递的值实际上会为每一行输出添加前缀。

function Get-NChooseK
{


[CmdletBinding()]


Param
(


[String[]]
$ArrayN


,   [Int]
$ChooseK


,   [Switch]
$AllK


,   [String]
$Prefix = ''


)


PROCESS
{
# Validate the inputs
$ArrayN = $ArrayN | Sort-Object -Unique


If ($ChooseK -gt $ArrayN.Length)
{
Write-Error "Can't choose $ChooseK items when only $($ArrayN.Length) are available." -ErrorAction Stop
}


# Control the output
$firstK = If ($AllK) { 1 } Else { $ChooseK }


# Get combinations
$firstK..$ChooseK | ForEach-Object {


$thisK = $_


$ArrayN[0..($ArrayN.Length-($thisK--))] | ForEach-Object {
If ($thisK -eq 0)
{
Write-Output ($Prefix+$_)
}
Else
{
Get-NChooseK -Array ($ArrayN[($ArrayN.IndexOf($_)+1)..($ArrayN.Length-1)]) -Choose $thisK -AllK:$false -Prefix ($Prefix+$_)
}
}


}
}


}

例如:

PS C:\>$ArrayN  = 'E','B','C','A','D'
PS C:\>$ChooseK = 3
PS C:\>Get-NChooseK -ArrayN $ArrayN -ChooseK $ChooseK
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE

PowerShell解决方案:

function Get-NChooseK
{
<#
.SYNOPSIS
Returns all the possible combinations by choosing K items at a time from N possible items.


.DESCRIPTION
Returns all the possible combinations by choosing K items at a time from N possible items.
The combinations returned do not consider the order of items as important i.e. 123 is considered to be the same combination as 231, etc.


.PARAMETER ArrayN
The array of items to choose from.


.PARAMETER ChooseK
The number of items to choose.


.PARAMETER AllK
Includes combinations for all lesser values of K above zero i.e. 1 to K.


.PARAMETER Prefix
String that will prefix each line of the output.


.EXAMPLE
PS C:\> Get-NChooseK -ArrayN '1','2','3' -ChooseK 3
123


.EXAMPLE
PS C:\> Get-NChooseK -ArrayN '1','2','3' -ChooseK 3 -AllK
1
2
3
12
13
23
123


.EXAMPLE
PS C:\> Get-NChooseK -ArrayN '1','2','3' -ChooseK 2 -Prefix 'Combo: '
Combo: 12
Combo: 13
Combo: 23


.NOTES
Author : nmbell
#>


# Use cmdlet binding
[CmdletBinding()]


# Declare parameters
Param
(


[String[]]
$ArrayN


,   [Int]
$ChooseK


,   [Switch]
$AllK


,   [String]
$Prefix = ''


)


BEGIN
{
}


PROCESS
{
# Validate the inputs
$ArrayN = $ArrayN | Sort-Object -Unique


If ($ChooseK -gt $ArrayN.Length)
{
Write-Error "Can't choose $ChooseK items when only $($ArrayN.Length) are available." -ErrorAction Stop
}


# Control the output
$firstK = If ($AllK) { 1 } Else { $ChooseK }


# Get combinations
$firstK..$ChooseK | ForEach-Object {


$thisK = $_


$ArrayN[0..($ArrayN.Length-($thisK--))] | ForEach-Object {
If ($thisK -eq 0)
{
Write-Output ($Prefix+$_)
}
Else
{
Get-NChooseK -Array ($ArrayN[($ArrayN.IndexOf($_)+1)..($ArrayN.Length-1)]) -Choose $thisK -AllK:$false -Prefix ($Prefix+$_)
}
}


}
}


END
{
}


}

例如:

PS C:\>Get-NChooseK -ArrayN 'A','B','C','D','E' -ChooseK 3
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE

最近在IronScripter网站上发布了一个类似于这个问题的挑战，在那里你可以找到我的和其他一些解决方案的链接。

你可以使用Asif算法来生成所有可能的组合。这可能是最简单和最有效的方法。你可以查看媒体文章在这里。

让我们看看JavaScript中的实现。

function Combinations( arr, r ) {
// To avoid object referencing, cloning the array.
arr = arr && arr.slice() || [];


var len = arr.length;


if( !len || r > len || !r )
return [ [] ];
else if( r === len )
return [ arr ];


if( r === len ) return arr.reduce( ( x, v ) => {
x.push( [ v ] );


return x;
}, [] );


var head = arr.shift();


return Combinations( arr, r - 1 ).map( x => {
x.unshift( head );


return x;
} ).concat( Combinations( arr, r ) );
}


// Now do your stuff.


console.log( Combinations( [ 'a', 'b', 'c', 'd', 'e' ], 3 ) );