查找分区集的每个可能组合的更好方法

我需要找到 N 个 X 长度的集合的每个可能组合，没有重复项，并且按特定顺序，例如

input:  [["A"], ["B"], ["C"]]
output: [["A","B","C"],["A","B"],["A","C"],["B","C"],["A"],["B"],["C"]]

规则：

分区的数量或大小不是固定的。
组合中每个分区只有一个成员。
具有更多成员的组合优先级更高。
输入中较早的成员比稍后的成员具有更高的优先级。

另一个具有较大集合的示例：

input:  [["A","B"],["C","D","E"],["F"]]
output: [["A","C","F"],["A","D","F"],["A","E","F"],["B","C","F"],["B","D","F"],["B","E","F"],["A","C"],["A","D"],["A","E"],["B","C"],["B","D"],["B","E"],["A","F"],["B","F"],["C","F"],["D","F"],["E","F"],["A"],["B"],["C"],["D"],["E"],["F"]]

通过将幂集函数的输出与笛卡尔乘积函数相结合，我设法获得了我想要的输出，但生成的代码不是很简洁或漂亮。我想知道这是否可以通过递归更好地完成？

这是我已经拥有的：

$test = json_decode('[["A"]]');
$test1 = json_decode('[["A"], ["B"], ["C"]]');
$test2 = json_decode('[["A", "B"], ["C", "D", "E"], ["F"]]');
/**
 * Returns a power set of the input array.
 */                   
function power_set($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;
}
/**
 * Returns the cartesian product of the input arrays.
 */
function array_cartesian() {
  $_ = func_get_args();
  if(count($_) == 0) {
    return array(array());
  }
  $a = array_shift($_);
  $c = call_user_func_array(__FUNCTION__, $_);
  $r = array();
  foreach($a as $v) {
    foreach($c as $p) {
      $r[] = array_merge(array($v), $p);
    }
  }
  return $r;
}
/**
 * Used with usort() to sort arrays by length, desc.
 * If two arrays are the same length, then a sum of 
 * their keys is taken, with lower values coming first.
 */
function arraySizeDesc($a, $b) {
  if(count($a) === count($b)) {
    if(array_sum($a) === array_sum($b)) {
      return 0;
    }
    return (array_sum($a) > array_sum($b)) ? 1 : -1;
  }
  return (count($a) < count($b)) ? 1 : -1;
}
/**
 * Calculates a powerset of the input array and then uses
 * this to generate cartesian products of each combination
 * until all possible combinations are aquired.
 */
function combinations($in) {
 $out = array();
 $powerSet = power_set(array_keys($in));
 usort($powerSet, 'arraySizeDesc');
 foreach($powerSet as $combination) {
   if(count($combination) < 2) {
     foreach($in[$combination[0]] as $value) {
       $out[] = array($value);
     }
   } else {
     $sets = array();
     foreach($combination as $setId) {
       $sets[] = $in[$setId];
     }
     $out = array_merge($out, call_user_func_array('array_cartesian', $sets));
   }
 }
 return $out;
}
echo "input: ".json_encode($test2);
echo "<br />output: ".json_encode(combinations($test2));

我意识到输出的大小可能会非常迅速地增长，但输入通常应该只包含 1-5 组 1-50 个成员，因此它不需要处理大量集合。

从本质上讲，您的方法是生成输入的功率集，然后对其进行后处理以达到所需的输出。

人们可以通过尝试直接解决它来以不同的方式处理它。我想到的一个解决方案如下。

给定输入 A = [ A 1， ...]，假设 A \ A₁ 的问题已经解决。将此解决方案称为 S'。我们如何将整个 A 的 S' 转换为解 S？这本质上是通过制作两个 S' 副本来实现的。我们将 A₁ 的元素分发到第一个副本中。我们将新序列称为 S''。因此，A 的解变成了 S'' 和 S' 的简单连接。

在算法上，

Input: A = [ A₁, A₂, ..., A_n]


combine(A, i, n):


if n < i
return []
if n == i 
return singletons(A_i)
S' = combine(A, i + 1, n)
S'' = [a, S'], for each a in A_i

return [S'', S']

该函数singletons返回输入集的单元素子集系列。因此，如果它接受输入 [1
， 2， 3]，它将返回 [[1]、[2]、[3]]。
如果您忽略此处和那里序列串联的一些松散用法，该方法应该很清楚......
祝你好运！

尝试

$test = array ();
$test [0] = json_decode ( '[["A"]]', true );
$test [1] = json_decode ( '[["A"], ["B"], ["C"]]', true );
$test [2] = json_decode ( '[["A", "B"], ["C", "D", "E"], ["F"]]', true );

echo "<pre>" ;
$set = array ();
getSet ( $test, $set );
$set = array_values(array_unique($set));
$return = powerSet($set,1,3);
print_r ($return);

输出

使用的函数

function powerSet($in, $minLength = 1, $max = 10) {
    $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 && count ( $out ) <= $max) {
            $return [] = $out;
        }
    }
    return $return;
}
function getSet($array, &$vals) {
    foreach ( $array as $key => $value ) {
        if (is_array ( $value )) {
            getSet ( $value, $vals );
        } else {
            $vals [] = $value;
        }
    }
    return $vals;
}

尝试

输出

使用的函数

相关内容

最新更新

热门标签：