長さ X の N 個のセットのすべての可能な組み合わせを重複なしで特定の順序で見つける必要があります。
input: [["A"], ["B"], ["C"]]
output: [["A","B","C"],["A","B"],["A","C"],["B","C"],["A"],["B"],["C"]]
ルール:
- パーティションの数またはサイズは固定されていません。
- 各組み合わせの各パーティションから 1 つのメンバーのみ。
- より多くのメンバーとの組み合わせが優先されます。
- 入力の前のメンバーは、後のメンバーよりも優先順位が高くなります。
より大きなセットの別の例:
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 ～ 50 のメンバーの 1 ～ 5 セットのみを含める必要があるため、大量のセットを処理する必要はありません。