Power set elements of a certain length

Question

Given an array of elements in PHP, I wish to create a new two-dimensional array containing only those elements of the power set that are a specific length. As an example, for the following array:

array(4) {
    0 => 'A',
    1 => 'B',
    2 => 'C',
    3 => 'D'
}

If I were to run the function fixed_length_power_set( $arr, 2 ) then I want it to return:

array(6) {
    0 => array(2) {
        0 => 'A',
        1 => 'B'
    }
    1 => array(2) {
        0 => 'A',
        1 => 'C'
    }

    2 => array(2) {
        0 => 'A',
        1 => 'D'
    }
    3 => array(2) {
        0 => 'B',
        1 => 'C'
    }
    4 => array(2) {
        0 => 'B',
        1 => 'D'
    }
    5 => array(2) {
        0 => 'C',
        1 => 'D'
    }
}

Although I can think of a few rules to generalize the process, for some reason I can not seem to turn it into code. Does anyone have suggestions?

Answer 1

Use a simple recursive algorithm: For the set of all subsets of size k from a set of size n,

• if n == k, return a set containing the entire set;

• if k == 1 return the set of all singletons;

• otherwise remove an element x from the set: now you need all the subsets of size k-1 of the remaining set (i.e. those subsets which include x), as well as all the subsets of size k of the remaining set (those which don't include x).

In PHP pseudo-code:

function subsets_n($arr, $k)
{
  if (count($arr) < $k) return array();
  if (count($arr) == $k) return array(0 => $arr);

  $x = array_pop($arr);
  if (is_null($x)) return array();

  return array_merge(subsets_n($arr, $k),
                     merge_into_each($x, subsets_n($arr, $k-1)) );
}

Here merge_into_each() adds x to each array in the collection:

function merge_into_each($x, $arr)
{
  foreach ($arr as &$a) array_push($a, $x);
  return $arr;
}

Answer 2

I am not a PHP expert, so I will answer with pseudocode instead. Since you seem to be asking about arrays and subsequences (even though you use the English words "sets" and "subsets"), I'll do that. I'll use the notation arr[m:n] to mean the construction of a brand new array of length n - m + 1 that copies the elements m, m+1, ..., n from arr.

fun subsequences(arr, len) {
    answer = new empty array

    // base case 1: we haven't got a enough members in the
    // array to make a subsequence that long, so there are
    // no subsequences of that length
    if(arr.length < len) return answer

    // base case 2: we're only looking for trivial subsequences
    if(len <= 0) {
        trivial = new empty array
        prepend trivial to answer
        return answer
    }

    // choose the first element in the subsequence nondeterministically
    for each i from 0 to arr.length - 1 {
        // since we know the sequence starts with arr[i], the
        // remainder of the sequence must come from the elements
        // after index i
        subanswer = subsequences(arr[i+1:arr.length], len-1)
        for each subsequence in subanswer, prepend arr[i] to subsequence
        answer = concat(subanswer, answer)
    }
}