不需要进行集合操作。这个问题几乎和循环K个嵌套循环一样，但你必须小心索引和边界(忽略Java和OOP的东西):

 public class CombinationsGen {
    private final int n;
    private final int k;
    private int[] buf;

    public CombinationsGen(int n, int k) {
        this.n = n;
        this.k = k;
    }

    public void combine(Consumer<int[]> consumer) {
        buf = new int[k];
        rec(0, 0, consumer);
    }

    private void rec(int index, int next, Consumer<int[]> consumer) {
        int max = n - index;

        if (index == k - 1) {
            for (int i = 0; i < max && next < n; i++) {
                buf[index] = next;
                next++;
                consumer.accept(buf);
            }
        } else {
            for (int i = 0; i < max && next + index < n; i++) {
                buf[index] = next;
                next++;
                rec(index + 1, next, consumer);
            }
        }
    }
}

像这样使用:

 CombinationsGen gen = new CombinationsGen(5, 2);

 AtomicInteger total = new AtomicInteger();
 gen.combine(arr -> {
     System.out.println(Arrays.toString(arr));
     total.incrementAndGet();
 });
 System.out.println(total);

获得预期的结果:

[0, 1]
[0, 2]
[0, 3]
[0, 4]
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
10

最后，将索引映射到您可能拥有的任何数据集。

简短javascript版本(es5)

令combine = (list, n) => N == 0 ? [[]]: 列表。flatMap((e, i) => 结合( 列表。切片(i + 1) N - 1 ）.Map (c => [e].concat(c)) ）; Let res = combine([1,2,3,4]， 3); res.forEach(e => console.log(e.join()));

另一个具有组合索引惰性生成的c#版本。这个版本维护了一个索引数组来定义所有值列表和当前组合值之间的映射，即在整个运行时不断使用O(k)额外的空间。该代码在O(k)时间内生成单个组合，包括第一个组合。

public static IEnumerable<T[]> Combinations<T>(this T[] values, int k)
{
    if (k < 0 || values.Length < k)
        yield break; // invalid parameters, no combinations possible

    // generate the initial combination indices
    var combIndices = new int[k];
    for (var i = 0; i < k; i++)
    {
        combIndices[i] = i;
    }

    while (true)
    {
        // return next combination
        var combination = new T[k];
        for (var i = 0; i < k; i++)
        {
            combination[i] = values[combIndices[i]];
        }
        yield return combination;

        // find first index to update
        var indexToUpdate = k - 1;
        while (indexToUpdate >= 0 && combIndices[indexToUpdate] >= values.Length - k + indexToUpdate)
        {
            indexToUpdate--;
        }

        if (indexToUpdate < 0)
            yield break; // done

        // update combination indices
        for (var combIndex = combIndices[indexToUpdate] + 1; indexToUpdate < k; indexToUpdate++, combIndex++)
        {
            combIndices[indexToUpdate] = combIndex;
        }
    }
}

测试代码:

foreach (var combination in new[] {'a', 'b', 'c', 'd', 'e'}.Combinations(3))
{
    System.Console.WriteLine(String.Join(" ", combination));
}

输出:

a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e

这是我想出的解决这个问题的算法。它是用c++编写的，但是可以适应几乎任何支持位操作的语言。

void r_nCr(const unsigned int &startNum, const unsigned int &bitVal, const 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);
}

你可以在这里看到它如何工作的解释。

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

源

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

你可以使用Asif算法来生成所有可能的组合。这可能是最简单和最有效的方法。你可以在这里查看媒体文章。

让我们看看JavaScript中的实现。

function Combinations( arr, r ) {
    // To avoid object referencing, cloning the array.
    arr = arr && arr.slice() || [];

    var len = arr.length;

    if( !len || r > len || !r )
        return [ [] ];
    else if( r === len ) 
        return [ arr ];

    if( r === len ) return arr.reduce( ( x, v ) => {
        x.push( [ v ] );

        return x;
    }, [] );

    var head = arr.shift();

    return Combinations( arr, r - 1 ).map( x => {
        x.unshift( head );

        return x;
    } ).concat( Combinations( arr, r ) );
}

// Now do your stuff.

console.log( Combinations( [ 'a', 'b', 'c', 'd', 'e' ], 3 ) );