所有组合都没有重复，且具有特定基数 [英] All combinations without repetitions with specific cardinality

问题描述

我有一个数组：

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

，我将生成所有可能的子数组的集合，没有重复，其基数在X与是。

and I would generate the set of all possible subarrays, withuout repetition, whose cardinality is between X and Y.

让我们假设php：

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

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

我的函数应返回以下内容：

My function should returns something like:

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

我的尝试是对二进制数进行计数，从0到2 ^ n（其中n是集合），如果 1s 的数目在X和Y之间，则将由 1s 元素组成的数组添加到结果集。

My attempt was to count in binary, from 0 to 2^n (where n is the cardinality of the set) and if the number of 1s is between X and Y, add the array made of 1s element to the result set.

例如。

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

但这很丑陋！
还有更好的算法吗？

but it's very ugly! Any better algorithm?

我正在使用php，但是可以随意使用任何喜欢的语言。

I'm using php, but feel free to use whatever language you like.

推荐答案

一个非常简单的解决方案（需要生成器，我认为是PHP 5.5 +）

A pretty straightforward solution (requires generators, I think, it's 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";

这篇关于所有组合都没有重复，且具有特定基数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！