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

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

选择组合中的第一个元素I 将I与从大于I的元素集中递归选择的k-1个元素的组合组合。

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

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

也许我错过了重点(你需要的是算法，而不是现成的解决方案)，但看起来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)

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

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

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

作为迭代器对象实现的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()); }

输出: 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