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

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

Решение
Используйте функцию pc_array_power_set()

Пример 4.5. 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 вызывает удвоение количества элементов.

Оцените статью: (0 голосов)
0 5 0

Статьи из раздела PHP на эту тему:
Добавление одного массива к другому
Изменение длины массива
Инициализация массива диапазоном
Инициализация массива диапазоном целых чисел
Нахождение всех перестановок массива

Вернуться в раздел: PHP / 4. Массивы