简短的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/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支持，它足以满足我的需求

递归，一个很简单的答案，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”处理为每个组合生成的产品数组。

下面是一个使用宏的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)
...

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

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

如果你想用不同或更长的字母显示元素，那么改变*字母参数以指向不同于"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;
}

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

组合:从“7选4”中选择。

《计算机编程艺术，卷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;
}