Необходимо определить совокупность всех комбинаций множеств, содержащих все или некоторые элементы массива, известную также как показательное множество.
Используем функцию 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 вызывает удвоение количества элементов.
