Комбинации элементов X в 1, 2, 3, 4, … X суб-под-массивы
У меня есть массив, который выглядит следующим образом: [0, 1, 2, 3, 4, 5, …]
Мне нужна функция, которая даст мне такой массив:
[
[[0, 1, 2, 3, 4, 5]],
[[0, 1, 2, 3, 4], [ 5 ]],
[[0, 1, 2, 3], [ 4, 5 ]],
[[0, 1, 2], [ 3, 4, 5 ]],
...
[[0, 1, 2], [ 3, 4 ], [ 5 ]],
...
[[ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ]]
]
Конечно, этот вывод только для 6 элементов.
Если вы посмотрите на 2-ю, 3-ю и 4-ю строку выходного массива, это своего рода комбинация в 2 подмассива.
Если вы посмотрите на 6-ю строку выходного массива, он превратится в 3 подмассива.
В последней строке каждый элемент должен быть один в своем подмассиве.
Я видел примеры на эта страница и я попробовал функции, но моя немного отличается, потому что порядок элементов должен соблюдаться. Это означает, что независимо от того, где скобки,
Вы должны увидеть 1 2 3 4 5 6 в каждой строке.
Кроме того, функции на ранее упомянутой странице предоставят мне массив, включающий все вложенные массивы:
[[x, x], [x], [x], [xxx]] Я не могу использовать это.
Мне нужен этот формат:
[
[ [ 1 , 2 , 3 ] ] ,
[ [ 1 , 2 ] , [ 3 ] ] ,
[ [ 1 ] , [ 2 , 3 ] ] ,
[ [ 1 ] , [ 2 ] , [ 3 ] ]
]
Я новичок, пожалуйста, кто-нибудь подскажет, как это сделать!
Решение
Я только что разработал особый способ достижения того, что вы ищете (обход двоичного дерева с использованием двоичных меток! Я не знаю, существует ли он уже !!) Это очень быстро и не использует рекурсию 🙂
<?php
function getSpecialSubsets($in) {
$in = array_reverse($in);
$n = count($in);
$out = array();
// for every possible route
for($i = 0; $i<pow(2, $n-1); $i++) {
$out[$i] = array(array());
// for every value in the input array
for($j=$n-1; $j>=0; $j--) {
$val = $in[$j];
if(($i >> $j) & 1)
$out[$i][] = array($val);
else $out[$i][count($out[$i])-1][] = $val;
}
}
return $out;
}
$subsets = getSpecialSubsets([1, 2, 3, 4]);
// for demonstration purposes only!!
echo "<pre>";
echo preg_replace('~\]\],~', "]],\n", json_encode($subsets));
echo "</pre>";
?>
Другие решения
Это заняло у меня несколько часов!
Ты прав, ваш вопрос ошибочно указан как дубликат Тем не менее, в этом вопросе участвует то, что вы хотели получить все Перегородки из набора вместо того, что вы хотели Вот (здесь вы хотели подмножество этого набора.) В любом случае вы можете использовать следующее для получения желаемого результата, просто замените имя нужной функции в отмеченной строке на любое, что вы хотите (я имею в виду, вы также можете изменить его на getSpecialSubsets() представленный выше.
Как вы говорите, скажите, желаемая главная функция getVerySpecialSubsets() также имеет благоприятные аргументы $level_min а также $level_max 🙂
<?php
function allPermutations($InArray, $InProcessedArray = array())
{
$ReturnArray = array();
foreach($InArray as $Key=>$value)
{
$CopyArray = $InProcessedArray;
$CopyArray[$Key] = $value;
$TempArray = array_diff_key($InArray, $CopyArray);
if (count($TempArray) == 0)
$ReturnArray[] = array_values($CopyArray);
else
$ReturnArray = array_merge($ReturnArray, allPermutations($TempArray, $CopyArray));
}
return $ReturnArray;
}
function powerSet($in,$minLength = 1) {
$count = count($in);
$members = pow(2,$count);
$return = array();
for ($i = 0; $i < $members; $i++) {
$b = sprintf("%0".$count."b",$i);
$out = array();
for ($j = 0; $j < $count; $j++) {
if ($b{$j} == '1') $out[] = $in[$j];
}
if (count($out) >= $minLength) {
$return[] = $out;
}
}
return $return;
}
function getAllPartitionsOfSet($in) {
$arr = powerSet(powerSet($in));
$out = array();
foreach($arr as $combination) {
$a = array();
foreach($combination as $_arr)
foreach($_arr as $v)
$a[] = $v;
// check if $a has duplicates
// (i.e: the intersection of subsets in $combination is void)
if(count($a) !== count(array_unique($a)))
continue;
// check if there's no difference between $a and $in.
// (i.e: the union of subsets in $combination is equal to $a)
if(!empty(array_diff($a, $in)) || !empty(array_diff($in, $a)))
continue;
$out[] = $combination;
}
return $out;
}
function getVerySpecialSubsets($_in, $level_min = 1, $level_max = 0) {
$in = array_reverse($_in);
$n = count($in);
$level_min = $level_min>0 ? $level_min : 1;
$level_max = $level_max>0 ? $level_max : $n;
$allPartitions = getAllPartitionsOfSet($_in); //* marked!
$out = array();
foreach($allPartitions as $partition) {
$levels_count = count($partition);
if($levels_count>$level_max || $levels_count<$level_min)
continue;
// add the permutations of the arrays
for($i=0; $i<count($partition); $i++) {
$per = allPermutations($partition[$i]);
if(count($per)==1)
continue;
// combine the permutation with the rest of array
$first_item = true;
foreach($per as $_per) {
$arr = array();
for($j=0; $j<count($partition); $j++)
$arr[] = ($j==$i) ? $_per : $partition[$j];
$out[] = $arr;
}
}
}
// last singles
if($n<=$level_max && $n>=$level_min) {
$arr_last = array();
for($k=count($in)-1; $k>=0; $k--)
$arr_last[] = array($in[$k]);
$out[] = $arr_last;
}
return array_values(array_unique($out, SORT_REGULAR));
}
$subsets = getVerySpecialSubsets([0, 1, 2]);
// for demonstration purposes only!!
echo '<pre>';
echo preg_replace('~\]\],~', "]],\n", json_encode($subsets));
echo '</pre>';
?>