X 元素组合成 1, 2, 3, 4, ... X 子子数组

Question

我有一个如下所示的数组：[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 个子数组。
在最后一行中，每个元素都应该单独存在于它自己的子数组中。

我在 this page 上看到了示例并尝试了这些函数，但我的有点不同，因为需要遵守元素的顺序。这意味着无论括号在哪里，你应该在每一行看到 1 2 3 4 5 6。

此外，前面提到的页面中的函数将给我一个包含所有子数组的数组：
[[x,x],[x],[x],[xxx]] 我不能用这个。

我需要的是这种格式：

[  
[ [ 1 , 2 , 3 ] ] ,  
[ [ 1 , 2 ] , [ 3 ] ] ,  
[ [ 1 ] , [ 2 , 3 ] ] ,  
[ [ 1 ] , [ 2 ] , [ 3 ] ]  
]

我是初学者，请高人指点一下如何操作！

Answer 1

我刚刚开发了一种非常特殊的方法来实现你正在寻找的东西（使用二进制标签遍历二叉树！我不知道它是否已经存在！！）它非常快而且不会使用递归:)

<?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>";
?>

Answer 2

这花了我几个小时才完成！！

你是对的，your question is wrongly set as duplicate. However, In that question what you wanted is involved to get all the Partitions of the set instead of what you wanted (here you wanted a subset of that set.) In either of cases, you can use the following to get the desired output, just replace the name of the desired function in the marked line to whatever you want (I mean you may also change it to getSpecialSubsets() presented 。

当你调用 tell 时，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>';
?>

X 元素组合成 1, 2, 3, 4, ... X 子子数组

Combinations of X elements into 1, 2, 3, 4, ... X sub-sub-arrays

php

powerset