下面是一个方法，它从一个随机长度的字符串中给出指定大小的所有组合。类似于昆玛斯的解，但适用于不同的输入和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

简短快速的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;
}

下面是一个简单易懂的递归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
}

我正在为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, ' ';

源

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

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>

通过这种方式(减少i和unshift())，它以递减的顺序生成组合和组合内的元素，有点赏心悦目。 测试在1秒后停止，因此输入奇怪的数字是相对安全的。

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