我可以给出这个问题的递归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

我喜欢它的简洁。

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

$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++中为组合创建了一个通用类。 它是这样使用的。

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

我的库ncr[i]从1返回，而不是从0返回。 这就是为什么数组中有0。 如果你想考虑订单，只需将nCr class改为nPr即可。 用法是相同的。

结果

美国广播公司 ABD 安倍 沛富 ABG ABH 澳洲牧牛犬 王牌 ACF ACG 呵呀 正面 ADF ADG 抗利尿激素 时 AEG AEH 二自由度陀螺仪 AFH 啊 BCD 公元前 供应量 波士顿咨询公司 BCH 12 快速公车提供 BDG BDH 性能试验 求 本· 高炉煤气 BFH 使用BGH CDE 提供 CDG 鼎晖 欧共体语言教学大纲的 CEG 另一 CFG CFH 全息 DEF 度 电气设施 脱硫 干扰 DGH EFG EFH EGH FGH

下面是头文件。

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

这是一个c++解决方案，我提出使用递归和位移位。它也可以在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);
}

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

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

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