Разработчику. Сборник рецептов PHP
Задавайте вопросы

Определение всех комбинаций элементов массива

Вернуться назад

Задача

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

Решение

Используем функцию pc_array_power_set():

function pc_array_power_set($array) {
       // инициализируем пустым множеством
       $results = array(array());

       foreach ($array as $element)
              foreach ($results as $combination)
                     array_push($results, array_merge(array($element), $combination));

       return $results;
}

Она возвращает массив массивов, содержащий все комбинации элементов, включая пустое множество. Например:

$set = array('A' , 'B' , 'C');
$power_set = pc_array_power_set($set);

Массив $power_set состоит из восьми массивов:

array();
array('A');
array('B');
array('C');
array('A' , 'B');
array('A' , 'C');
array('B' , 'C');
array('A' , 'B' , 'C');

Обсуждение

Сначала включаем в результат пустое множество {}. Все-таки должна быть одна комбинация множеств, которая не содержит ни одного элемента из них.

Остальная часть этой функции основана на природе комбинаций и реализации оператора foreach в PHP. Каждый новый элемент, добавленный в массив, увеличивает число комбинаций. Новые комбинации представляют собой старые комбинации с новым элементом; двухэлементный массив, состоящий из A и B, генерирует четыре возможных комбинации: {}, {A}, {B} и {A, B}. Добавление C к этому множеству сохраняет четыре предыдущих комбинации, а также добавляет четыре новых комбинации: {C}, {A, C}, {B, C} и {A, B, C}.

Таким образом, внешний цикл foreach проходит по всем элементам списка; внутренний цикл foreach проходит по всем предыдущим комбинациям, созданным более ранними элементами. Это немного сложно, но необходимо точно знать, как ведет себя PHP в процессе выполнения цикла foreach.

Функция array_merge() объединяет элемент с предыдущими комбинациями. Заметим, однако, что массив $results, добавленный к новому массиву функцией array_push(), – это тот самый массив, который обрабатывался в цикле foreach. Обычно добавление элемента к массиву $results приводит к бесконечному циклу, но не в PHP, поскольку PHP работает с копией исходного списка. И когда вы возвращаетесь на уровень внешнего цикла и снова выполняете цикл foreach со следующим элементом, эта копия сбрасывается. Поэтому можно работать непосредственно с массивом $results и использовать его в качестве стека для хранения комбинаций. Хранение всей информации в массиве даст большую гибкость, когда в дальнейшем придется выводить на печать и дополнительно подразделять на комбинации.

Чтобы исключить пустое множество, замените начальную строку:

// инициализируем, добавляя пустое множество
$results = array(array());

на:

// инициализируем, добавляя первый элемент
$results = array(array(array_pop($array)));

Поскольку одноэлементный массив имеет только одну комбинацию – самого себя, то удаление элемента равносильно выполнению первого прохода цикла. Двойные циклы foreach не знают, что в действительности они начинают свою работу со второго элемента массива.

Чтобы напечатать результат с табуляциями между элементами внутри комбинации и возвратом каретки в конце каждой комбинации, используйте следующий код:

$array = array('Adam' , 'Bret' , 'Ceff' , 'Dave');

foreach (pc_array_power_set($array) as $combination) {
     print join("\t", $combination) . "\n";
}

Ниже показано, как напечатать только трехэлементные комбинации:

foreach (pc_array_power_set($set) as $combination) {
     if (3 == count($combination)) {
          print join("\t", $combination) . "\n";
     }
}

Итерация с большими множествами занимает значительное время. Множество из n элементов приводит к образованию 2n+1 множеств. Другими словами, увеличение n на 1 вызывает удвоение количества элементов.

Вернуться назад

Рейтинг@Mail.ru

Яндекс.Метрика

Индекс цитирования

Рейтинг Сайтов ДОСКИ.РУ