php从多维数组中获取所有有效组合

Question

I have a array which represent allowed value in a key. The length of this array is dynamic

array(
 10=>array(100,101,102),
 11=>array(100,104),
 12=>array(100,102,103)
)

in this exemple, key 10 can have 100, 101 and 102.

I want to get all valid combination where each value appear only one time

array(
   array(10=>array(100,101,102),11=>array(104),12=>array(103)),
   array(10=>array(100,101),10=>array(104),12=>array(102,103)),
   array(10=>array(101),10=>array(100,104),12=>array(102,103)),
   array(10=>array(101),10=>array(104),12=>array(100,102,103)),
   AND SO ON
)

Answer 1

They want you to find the power sets for each index and then calculate the power set of the sets.

This code will allows you to calculate the power set for each index. It should get you started and give you an idea of how to complete the rest of the problem.

function power_set($arr)
{
    $sets = [];

    for ($i = 0; $i < pow(2, count($arr)); $i++) {
        $set = [];
        for ($j = 0; $j < count($arr); $j++) {
            if ($i & (1 << $j)) {
                $set[] = $arr[$j];
            }
        }
        if (count($set) > 0) {
            $sets[] = $set;
        }
        $set = [];
    }
    return $sets;
}

Output

array(7) {
  [0] =>
  array(1) {
    [0] =>
    int(100)
  }
  [1] =>
  array(1) {
    [0] =>
    int(101)
  }
  [2] =>
  array(2) {
    [0] =>
    int(100)
    [1] =>
    int(101)
  }
  [3] =>
  array(1) {
    [0] =>
    int(102)
  }
  [4] =>
  array(2) {
    [0] =>
    int(100)
    [1] =>
    int(102)
  }
  [5] =>
  array(2) {
    [0] =>
    int(101)
    [1] =>
    int(102)
  }
  [6] =>
  array(3) {
    [0] =>
    int(100)
    [1] =>
    int(101)
    [2] =>
    int(102)
  }
}

One thing that I did notice, is that you aren't including the case where the set has no elements. Technically that should be included, so I would check to ensure that your sample output is right. I modified the algorithm to exclude this case, but I would assume that it should be included.

If you want to include it remove the if statement that checks for the number of elements in the $set.