所有组合都没有重复,具有特定的基数

Question

我有一个数组:

[a, b, c, d, e, f, ... , z]

并且我将生成所有可能的子阵列的集合,不重复,其基数在X和Y之间.

我们假设php:

$array = array(1, 2, 3, 4, 5, 6, 7, 8);

$results = myFunction($array, 3, 5);

我的函数应该返回如下内容:

array( 
    array(1, 2, 3),
    array(1, 2, 4),
    ...
    array(4, 5, 6, 7, 8),
);

我的尝试是以二进制计数,从0到2 ^ n(其中n是集合的基数),如果数字1s在X和Y之间,则将由1s元素组成的数组添加到结果集中.

例如.

8  = 0000 0111 => add (6,7,8) to result
9  = 0000 1000 => no 
10 = 0000 1001 => no
...

但它非常难看!有更好的算法吗？

我正在使用PHP,但随意使用你喜欢的任何语言.

Answer 1

一个非常简单的解决方案(需要生成器,我认为,这是PHP 5.5+)

// generate combinations of size $m
function comb($m, $a) {
    if (!$m) {
        yield [];
        return;
    }
    if (!$a) {
        return;
    }
    $h = $a[0];
    $t = array_slice($a, 1);
    foreach(comb($m - 1, $t) as $c)
        yield array_merge([$h], $c);
    foreach(comb($m, $t) as $c)
        yield $c;
}

然后

$a = ['a','b','c','d','e','f', 'g'];

foreach(range(3, 5) as $n)
    foreach(comb($n, $a) as $c)
        echo join(' ', $c), "\n";