Как создать массив подмножеств

Я думаю, что это отличный вопрос — поиск подмножеств множества имеет несколько подходов
Я предпочитаю использовать бинарный подход:

Есть n^2 наборы для данного набора n, Вы можете считать в двоичном коде от 0 до 2 ^ n и интерпретировать двоичное число как соответствующее подмножество. Обратите внимание, что этот подход требует двоичного числа с достаточным количеством цифр для представления всего набора, поэтому нам нужно дополнить двоичное представление.

Больше чтения: Бинарное-подмножество

Моя реализация:

$arr = array(1,2,3);
$res = subsets($arr);

function subsets($arr,$sort = true,$include_empty = false,$include_full = false) {
$length = count($arr);
$res = array();
if (!$length && $include_full) return $res;
for ($i = 0; $i<pow(2, $length); $i++) {
$set = array();
$bin = str_split(str_pad(decbin($i), $length, "0", STR_PAD_LEFT));
$binLen = count($bin);
for ($j = 0; $j < $binLen; $j++)
if ($bin[$j] === "1") $set[] = $arr[$j];
$res[] = $set;
}
foreach($res as $k => $val)
if (!count($val) && !$include_empty) unset($res[$k]);
elseif (count($val) === $length && !$include_full) unset($res[$k]);
function cmp($a, $b){ return (count($a) - count($b)); }
if ($sort) usort($res, 'cmp');
return $res;
}

//Output Results:
foreach ($res as $key => $data) {
echo $key." -> [".(implode(',',$data))."]\r";
}
/*
0 -> [1]
1 -> [3]
2 -> [2]
3 -> [1,2]
4 -> [2,3]
5 -> [1,3]
*/

Как видите, функция обрабатывает входной массив, и вы можете выбрать, включать в результат пустой набор и полный набор или нет.

Вы должны знать, что количество итераций резко увеличивается:

Без удаления пустого набора или полного набора:

n*(2^n)

с удалением:

(2^n) + n*(2^n)

с удалением & сортировка (наихудший случай):

(2^n) + n*(2^n) + n^2

Допустим, у нас есть входной массив с 9 значениями:

(2^9)*9 = 4608;

(2^9) + 9*(2^9) = 5120;

(2^9) + 9*(2^9) + 9^2 = 5201;

Это самый быстрый способ, который я знаю.

Заметка:
Функция ожидает уникальный массив — вы можете убедиться, что ваш массив уникален:

$arr = array_unique ($arr);