我有以下数组，它包含值的数组：
$array = array(
array('1', '2'),
array('a', 'b', 'c'),
array('x', 'y'),
);
可以有任意数量的阵列和阵列可以包含任意数目的值。 我现在有一段代码，这将产生其中一个值是从每个阵列采取的所有组合。 例如：
1ax, 1ay, 1bx, 1by, 1cx, 1cy, 2ax, 2ay, 2bx, 2by, 2cx, 2cy
但是我真正想要的只是组合只有一个值，坐在每一列，即。 1AX没有好的，因为所有三个值1，并且x在第一列坐，因为B和Y坐在第二列1BY是没有好处的。 因此，从上面的例子只有这些组合是有效的：
1cy, 2cx
我原本打算只生成所有组合，然后筛选出与冲突的，但这并不能扩展，因为这是一个过于简单的例子，在实际应用中也将是那里有潜在的数以百万计的组合（包括冲突的那些情况）。
任何人都可以有一个更好的办法来解决这方面的帮助？ 我在PHP中的工作，但清楚地表明了逻辑的任何代码示例将是有益的。
提前致谢。
更新：
我测试过，对一个更大的数据集的工作方案，得到一些基准测试，这些都是迄今为止的结果：
$array = array(
array('1', '2', '3', '1', '2', '3', '1', '2', '3', '1', '2', '3', '1', '2', '3'),
array('a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd'),
array('x', 'y', 'z', 'x', 'y', 'z', 'x', 'y', 'z'),
array('1', '2', '3', '1', '2', '3', '1', '2', '3'),
array('a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd'),
array('x', 'y', 'z'),
);
乔希·戴维斯第2个解决方案：
Combinations: 249480
Time: 0.3180251121521 secs
Memory Usage: 22.012168884277 mb
Peak Memory Usage: 22.03059387207 mb
乔希·戴维斯：
Combinations: 249480
Time: 1.1172790527344 secs
Memory Usage: 22.004837036133 mb
Peak Memory Usage: 22.017387390137 mb
汤姆·黑格：
Combinations: 249480
Time: 5.7098741531372 secs
Memory Usage: 39.145843505859 mb
Peak Memory Usage: 39.145843505859 mb
Answer 1:
这是那些情况下自我生成的代码和蛮力将击败简单性和性能最算法之一。 在以前的答案我见过很多递归，数组处理和计算，实际上，当你想要做的是什么样的：
foreach ($array[0] as $k0 => $v0)
{
foreach ($array[1] as $k1 => $v1)
{
if ($k1 == $k0)
{
continue;
}
foreach ($array[2] as $k2 => $v2)
{
if ($k2 == $k1 || $k2 == $k0)
{
continue;
}
$result[] = $v0.$v1.$v2;
}
}
}
当然，除非你知道有多少数组是你不能写这个$array 。 这就是生成的代码来得心应手：
$array = array(
array('1', '2'),
array('a', 'b', 'c'),
array('x', 'y')
);
$result = array();
$php = '';
foreach ($array as $i => $arr)
{
$php .= 'foreach ($array[' . $i . '] as $k' . $i . ' => $v' . $i . '){';
if ($i > 0)
{
$sep = 'if (';
$j = $i - 1;
do
{
$php .= $sep . '$k' . $i . ' == $k' . $j;
$sep = ' || ';
}
while (--$j >= 0);
$php .= ') { continue; } ';
}
}
$php .= '$result[] = $v' . implode('.$v', array_keys($array)) . ';' . str_repeat('}', count($array));
eval($php);
print_r($result);
请注意，这个程序假定$array是一个从零开始的数字索引数组，在你的榜样。 它将产生上面引述的代码，调整后的阵列的任意数量。
更新
下面是一个替代算法。 它仍然是自身产生的，但不暴力破解。 我们仍然有嵌套循环，除了每个回路的工作在哪里当前使用的外环路键已经从这个循环的数组中删除数组的一个副本。 例如，如果值应为（A，B，C），但外环使用索引0和2，我们删除“一”（索引0）和“c”（索引2）和所有我们已经离开是“b”。 这意味着环上可能的组合只是工作，我们不需要if条件了。
此外，并且这部分可以应用于先前算法为好，我们处理的值的阵列，以便从最小到最大的，这样就保证当前的数组中存在，则使用索引。 不足之处是它不会产生相同的顺序组合。 它产生相同的组合，只是没有以相同的顺序。 代码如下所示：
$a0 = $array[0];
foreach ($a0 as $k0 => $v0)
{
$a2 = $array[2];
unset($a2[$k0]);
foreach ($a2 as $k2 => $v2)
{
$a1 = $array[1];
unset($a1[$k0], $a1[$k2]);
foreach ($a1 as $k1 => $v1)
{
$result[] = "$v0$v1$v2";
}
}
}
上述例程设置在每一个循环开始时的值的副本，然后删除由外环使用的值。 您可以改善在一开始建立的值的副本只有一次这个过程，删除键，因为它们使用（在每个循环的开始），并把它们放回去，因为他们被释放（在每个循环结束） 。 然后该程序是这样的：
list($a0,$a1,$a2) = $array;
foreach ($a0 as $k0 => $v0)
{
unset($a1[$k0], $a2[$k0]);
foreach ($a2 as $k2 => $v2)
{
unset($a1[$k2]);
foreach ($a1 as $k1 => $v1)
{
$result[] = "$v0$v1$v2";
}
$a1[$k2] = $array[1][$k2];
}
$a1[$k0] = $array[1][$k0];
$a2[$k0] = $array[2][$k0];
}
生成上述源的实际代码是：
$keys = array_map('count', $array);
arsort($keys);
$inner_keys = array();
foreach ($keys as $k => $cnt)
{
$keys[$k] = $inner_keys;
$inner_keys[] = $k;
}
$result = array();
$php = 'list($a' . implode(',$a', array_keys($array)) . ')=$array;';
foreach (array_reverse($keys, true) as $i => $inner_keys)
{
$php .= 'foreach ($a' . $i . ' as $k' . $i . ' => $v' . $i . '){';
if ($inner_keys)
{
$php .= 'unset($a' . implode('[$k' . $i . '],$a', $inner_keys) . '[$k' . $i . ']);';
}
}
$php .= '$result[] = "$v' . implode('$v', array_keys($array)) . '";';
foreach ($keys as $i => $inner_keys)
{
foreach ($inner_keys as $j)
{
$php .= '$a' . $j . '[$k' . $i . ']=$array[' . $j . '][$k' . $i . "];\n";
}
$php .= '}';
}
eval($php);
Answer 2:
有趣的问题！ 事实证明，这比我想象的更复杂，但它似乎工作。
基本策略是首先为了从最小到最大的阵列（跟踪什么顺序的，他们在，这样我就可以输出正确的顺序的答案）。
我保持指标阵列的形式将答案输入列表此有序阵列。
现在，列表进行排序，我可以存储第一个正确答案阵列（0,1,2，...，N）;
然后，我递归到一个功能通过在这个问题的答案阵列其他值（所有不属于该插槽太大了的）交换它在第一个插槽有尝试所有的值（高于0）。 自从我知道了按大小排序，我可以在任何价值转移到时候我交换的权利，而不必担心它是到大对于右侧的插槽。
输出每个有效插槽有一些疯狂的间接取消所有排序。
很抱歉，如果这看起来混乱。 我没有花太多的时间清除它。
<?php
# $lists is an array of arrays
function noconfcombos($lists) {
$lengths = array();
foreach($lists as $list) {
$lengths[] = count($list);
}
# find one solution (and make sure there is one)
$answer = array();
$sorted_lengths = $lengths;
asort($sorted_lengths);
$answer_order_lists = array();
$answer_order_lengths = array();
$output_order = array();
$min = 1;
$max_list_length = 0;
foreach($sorted_lengths as $lists_key => $list_max) {
if($list_max < $min) {
# no possible combos
return array();
}
$answer[] = $min - 1; # min-1 is lowest possible value (handing out colums starting with smallest rows)
$output_order[$lists_key] = $min - 1; # min-1 is which slot in $answers corresponds to this list
$answer_order_lists[] = $lists[$lists_key];
$answer_order_lengths[] = $lengths[$lists_key];
++$min;
}
ksort($output_order);
$number_of_lists = count($lists);
$max_list_length = end($sorted_lengths);
if($max_list_length > $number_of_lists) {
for($i = $number_of_lists; $i < $max_list_length; ++$i) {
$answer[] = $i;
}
$stop_at = $number_of_lists;
} else {
$stop_at = $number_of_lists - 1;
}
# now $answer is valid (it has the keys into the arrays in $list for the
# answer), and we can find the others by swapping around the values in
# $answer.
$ret = array();
$ret[] = noconfcombos_convert($answer, $answer_order_lists, $output_order);
noconfcombos_recurse($ret, $max_list_length, $stop_at, $answer_order_lengths, $answer_order_lists, $output_order, $answer, 0);
return $ret;
}
# try swapping in different indexes into position $index, from the positions
# higher, then recurse
function noconfcombos_recurse(&$ret, $max_list_length, $stop_at, &$lengths, &$lists, &$output_order, $answer, $index) {
if($index < $stop_at) {
noconfcombos_recurse($ret, $max_list_length, $stop_at, $lengths, $lists, $output_order, $answer, $index + 1);
}
for($other = $index + 1; $other < $max_list_length; ++$other) {
if($answer[$other] < $lengths[$index]) { # && $answer[$index] < $lengths[$other]) {
$tmp = $answer[$index];
$answer[$index] = $answer[$other];
$answer[$other] = $tmp;
$ret[] = noconfcombos_convert($answer, $lists, $output_order);
if($index < $stop_at) {
noconfcombos_recurse($ret, $max_list_length, $stop_at, $lengths, $lists, $output_order, $answer, $index + 1);
}
}
}
}
function noconfcombos_convert(&$indexes, &$lists, &$order) {
$ret = '';
foreach($order as $i) {
$ret .= $lists[$i][$indexes[$i]];
}
return $ret;
}
function noconfcombos_test() {
$a = array('1', '2', '3', '4');
$b = array('a', 'b', 'c', 'd', 'e');
$c = array('x', 'y', 'z');
$all = array($a, $b, $c);
print_r(noconfcombos($all));
}
noconfcombos_test();
Answer 3:
我想这样的作品。 它使用递归走过去就像一棵树的结构。 对于每一个分支它跟踪哪些列已被使用。 这可能是缓慢的，因为它是一种强制方法。
<?php
$array = array(
array('1', '2'),
array('a', 'b', 'c'),
array('x', 'y'),
);
function f($array, & $result, $colsToIgnore = array(), $currentPath = array()) {
$row = array_shift($array);
$length = count($row);
$isMoreRows = !! count($array);
for ($col = 0; $col < $length; $col++) {
//check whether column has already been used
if (in_array($col, $colsToIgnore)) {
continue;
}
$item = $row[$col];
$tmpPath = $currentPath;
$tmpPath[] = $item;
if ($isMoreRows) {
$tmpIgnoreCols = $colsToIgnore;
$tmpIgnoreCols[] = $col;
f($array, $result, $tmpIgnoreCols, $tmpPath);
} else {
$result[] = implode('', $tmpPath);
}
}
}
$result = array();
f($array, $result);
print_r($result);
Answer 4:
可能不是最优雅的方式，但不会把戏（JavaScript的）
var result = [];
for(i=0;i<arr1.length;i++)
{
for(j=0;j<arr2.length;j++)
{
if(j==i)
continue;
else
{
for(k=0;k<arr3.length;k++)
{
if(k==i||k==j)
continue;
else
{
result.push(arr1[i]+arr2[j]+arr3[k]);
}
}
}
}
}
Answer 5:
这可以通过使用递归使其与阵列中任意数量的工作进行重构。 如果我发现的时候，我给它一个尝试自己。
PS。 我不知道PHP的例子是在Delphi编写。
编辑：任意＃数组递归解决方案
type
TSingleArray = array of string;
TMasterArray = array of TSingleArray;
var
solutions: array of integer; // Q&D container to hold currently used indexes of SingleArrays
procedure WriteSolution(const masterArray: TMasterArray);
var
I: Integer;
indexes: string;
solution: string;
begin
for I := 0 to High(solutions) do
begin
indexes := indexes + IntToStr(solutions[I]) + ' ';
solution := solution + masterArray[I][solutions[I]];
end;
Writeln('Solution: ' + solution + ' Using indexes: ' + indexes);
end;
procedure FindSolution(const masterArray: TMasterArray; const singleArrayIndex: Integer; var bits: Integer);
var
I: Integer;
begin
for I := 0 to High(masterArray[singleArrayIndex]) do
begin
//***** Use bit manipulation to check if current index is already in use
if bits and (1 shl I) = (1 shl I ) then continue;
solutions[singleArrayIndex] := I;
Inc(bits, 1 shl I);
//***** If it is not the last array in our masterArray, continue by calling RecursArrays recursivly.
if singleArrayIndex <> High(masterArray) then FindSolution(masterArray, Succ(singleArrayIndex), bits)
else WriteSolution(masterArray);
Dec(bits, 1 shl I);
end;
end;
//***************
// Initialization
//***************
var
I, J: Integer;
bits: Integer;
singleArrayString: string;
masterArray: TMasterArray;
begin
I := 10;
SetLength(masterArray, I);
for I := 0 to High(masterArray) do
begin
SetLength(masterArray[I], High(masterArray) + Succ(I));
singleArrayString := EmptyStr;
for J := 0 to High(masterArray[I]) do
begin
masterArray[I][J] := IntToStr(J);
singleArrayString := singleArrayString + masterArray[I][J];
end;
WriteLn(singleArrayString)
end;
ReadLn;
//****** Start solving the problem using recursion
bits := 0;
SetLength(solutions, Succ(High(masterArray)));
FindSolution(masterArray, 0, bits);
end.
Answer 6:
看它从一个不同的角度：为了组成一个结果行，你需要选择每个列的值。 每个值应该从不同的源行被拾起。 问题是知道的“挑N OUT M的”，或更多数学上，一个组合 。
这意味着，其结果行对应于源极 - 行索引的阵列。
你可以开始建立索引阵列像这样的（伪代码）建立所有可能的采摘
function combinations( $source ) {
if( count( $source ) == 0 ) return $source;
$result=array();
// build one row
foreach( $source as $index=>$value ) {
$newsource = array_splice( $source, $index, 1 );
$reduced_combinations=combinations( $newsource );
foreach( $reduced_combinations as $reduced_combi ) {
$newrow=array_unshift( $reduced_combi, $value );
$result[]=$newrow;
}
}
return $result;
}
function retrieve_indices( $indices, $arrays ) {
$result=array();
foreach( $indices as $column=>$index ) {
$result[]=$arrays[$index][$column];
}
return $result;
}
$source_arrays = array(
array( "1", "2", "3" ),
array( "a", "b", "c" ),
array( "x", "y", "z" )
);
$index_combinations = combinations( range(0,2) );
$result=array();
foreach( $index_combinations as $combination ) {
$result[]=retrieve_indices( $combination, $source_arrays );
}
Answer 7:
另外一个选项：
$arr = array(
array('1', '2'),
array('a', 'b', 'c'),
array('x', 'y'),
);
//-----
//assuming $arr consists of non empty sub-arrays
function array_combinations($arr){
$max = 1;
for ($i = 0; $i < count($arr); $i ++){
$max *= count($arr[$i]);
}
$matrix = array();
for ($i = 0; $i < $max; $i ++){
$matrix = array();
}
$c_rep = 1;
for ($i = count($arr) - 1; $i >= 0; $i --){
$c_rep *= ($i < count($arr) - 1)//last sub-array
? count($arr[$i + 1])
: 1;
$k = 0;
while ($k < $max){
for ($t = 0; $t < count($arr[$i]); $t ++){
for ($j = 0; $j < $c_rep; $j ++){
$matrix[$i][$k ++] = $arr[$i][$t];
}
}
}
}
return $matrix;
}
//-----
$matrix = array_combinations($arr);
Answer 8:
你的问题是类似的寻找矩阵的行列式 。 最好的方式恕我直言，将填补较小的阵列，一些符号，说“0”，所以它们都具有值的相等数量，在你的榜样
$array = array(
array('1', '2', '0'),
array('a', 'b', 'c'),
array('x', 'y', '0'),
);
然后循环通过每个第一阵列值，并且对于每个递增1数组的索引，并检查下一个阵列和所述下一列（在第一循环将是“1”和索引将是0递增 - 1，则得到$阵列1 - “b”等），如果达到“0”，休息，如果达到右边界，第一个索引重置为0，然后做同样的递减，你将拥有所有的组合。 这可能是目前还不清楚，我检查链接到图像
Answer 9:
试试这个 ：
function algorithmToCalculateCombinations($n, $elems) {
if ($n > 0) {
$tmp_set = array();
$res = algorithmToCalculateCombinations($n - 1, $elems);
foreach ($res as $ce) {
foreach ($elems as $e) {
array_push($tmp_set, $ce . $e);
}
}
return $tmp_set;
} else {
return array('');
}
}
$Elemen = array(range(0,9),range('a','z'));
$Length = 3;
$combinations = algorithmToCalculateCombinations($Length, $Elemen);
文章来源: Finding all non-conflicting combinations of values from multiple lists of values
