2

I have an array:

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

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

Let's assume 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),
);

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.

Eg. 

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?

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

marka.thore
  • 2,795
  • 2
  • 20
  • 35
  • You should use recursion. Also be aware that the result set can be very large - that might be a good opportunity to learn about iterators. (Yes, PHP supports that.) – btilly Sep 01 '14 at 18:52
  • possible duplicate of [PHP array combinations](http://stackoverflow.com/questions/3742506/php-array-combinations) – David Eisenstat Sep 01 '14 at 19:08
  • (use an outer loop from X to Y, or slightly more cleverly, adjust the recursion to yield partial results as long as X) – David Eisenstat Sep 01 '14 at 19:09

1 Answers1

8

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

and then

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

foreach(range(3, 5) as $n)
    foreach(comb($n, $a) as $c)
        echo join(' ', $c), "\n";
georg
  • 211,518
  • 52
  • 313
  • 390
  • it's the first time that I see generators in php. Good to know! Thank you – marka.thore Sep 02 '14 at 08:19
  • @marka.thore: you're welcome. Bear in mind though, this code is not particularly efficient. – georg Sep 02 '14 at 10:35
  • you mean that generators are not efficient? How could be a more efficient way to do this (not the code, just the idea)? – marka.thore Sep 02 '14 at 11:12
  • @marka.thore: no idea about generators... but if performance matters, an iterative algorithm will be better than a recursive one. Search around for "generate combinations lexicographically". – georg Sep 02 '14 at 11:32