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

Учитывая массив элементов в 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'
    }
}

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


php set powerset
person stevendesu    schedule 06.09.2011    source источник

Ответы (2)


arrow_upward
4
arrow_downward

Используйте простой рекурсивный алгоритм: для набора всех подмножеств размера 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;
}
person Kerrek SB    schedule 06.09.2011
comment
Увлекся несколькими другими проектами, и у меня никогда не было времени попробовать это. Однако это сработало как шарм. - person stevendesu; 17.10.2011

arrow_upward
0
arrow_downward

Я не эксперт по 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)
    }
}
person Daniel Wagner    schedule 06.09.2011