Силовой набор элементов определенной длины

Question

Учитывая массив элементов в PHP, я хочу создать новый двумерный массив, содержащий только те элементы набора мощности, которые имеют определенную длину. Например, для следующего массива:

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

Если бы я запустил функцию fixed_length_power_set( $arr, 2 ), я бы хотел, чтобы она вернулась:

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

Хотя я могу придумать несколько правил для обобщения процесса, почему-то не могу превратить его в код. У кого-нибудь есть предложения?

Answer 1

Используйте простой рекурсивный алгоритм: для набора всех подмножеств размера k из набора размера n,

• , если n == k, вернуть набор, содержащийвесь набор;

• , если k == 1 возвращает набор всех синглетонов;

• , в противном случае удалить элемент x из набора:теперь вам нужны все подмножества размера k-1 оставшегося набора (т.е. те подмножества, которые включают x), а также все подмножества размера k оставшегося набора (те, которые не включают x).

В PHP псевдокод:

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

Здесь merge_into_each() добавляет x к каждому массиву в коллекции:

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

Answer 2

Я не эксперт по PHP, поэтому я отвечу псевдокодом. Поскольку вы, похоже, спрашиваете о массивах и подпоследовательностях (даже если вы используете английские слова «наборы» и «подмножества»), я сделаю это. Я буду использовать обозначение arr[m:n] для обозначения построения нового массива длиной n - m + 1, который копирует элементы m, m+1, ..., n из 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)
    }
}