У меня есть массив:
[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, но не стесняюсь использовать любой язык, который вам нравится.
Довольно простое решение (требуется генераторы, я думаю, это 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";