算法:

从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节。https://ocw.mit.edu/courses/electrical -工程-和-计算机- science/6 - 042 j -数学- -计算机科学-下降- 2010/readings/)

我的实现在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支持，它足以满足我的需求

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

So,

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> 

And,

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> 

我想提出我的解决方案。在next中没有递归调用，也没有嵌套循环。 代码的核心是next()方法。

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

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

这是一个优雅的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 :: _}
    }
}