Ricerca di tutti i non-conflitto combinazioni di valori di più elenchi di valori
https://stackoverflow.com/questions/1378098
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho il seguente array che contiene un array di valori:
$array = array(
array('1', '2'),
array('a', 'b', 'c'),
array('x', 'y'),
);
Ci può essere un qualsiasi numero di matrici e di un array può contenere qualsiasi numero di valori.Attualmente ho un pezzo di codice che genera tutte le combinazioni in cui un valore è assunto da ciascuna matrice.ad esempio:
1ax, 1ay, 1bx, 1by, 1cx, 1cy, 2ax, 2ay, 2bx, 2by, 2cx, 2cy
Però quello che voglio è solo le combinazioni in cui un solo valore si trova in ogni colonna, vale a dire.1ax non va bene perché tutti e tre i valori 1, a e x sedersi nella prima colonna, 1by non va bene perché b e y sedersi nella seconda colonna.Così dall'esempio sopra solo queste combinazioni sarebbero validi:
1cy, 2cx
Inizialmente avevo pensato solo di generare tutte le combinazioni e poi filtrare quelli con i conflitti, ma che non scala come questo è un esempio molto semplificato, nell'applicazione reale ci saranno situazioni in cui ci sono potenzialmente milioni di combinazioni (compresi quelli in conflitto).
Qualcuno può aiutarmi con un modo migliore per risolvere questo problema?Sto lavorando in PHP, ma qualsiasi codice di esempio che dimostra chiaramente la logica sarebbe utile.
Grazie in anticipo.
Aggiornamento:
Ho provato le soluzioni che funzionano contro un grande set di dati, per ottenere alcuni parametri di riferimento, questi sono i risultati:
$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'),
);
Josh Davis 2 ° Soluzione:
Combinations: 249480
Time: 0.3180251121521 secs
Memory Usage: 22.012168884277 mb
Peak Memory Usage: 22.03059387207 mb
Josh Davis:
Combinations: 249480
Time: 1.1172790527344 secs
Memory Usage: 22.004837036133 mb
Peak Memory Usage: 22.017387390137 mb
Tom Haigh:
Combinations: 249480
Time: 5.7098741531372 secs
Memory Usage: 39.145843505859 mb
Peak Memory Usage: 39.145843505859 mb
Soluzione
Questo è uno di quei casi in cui l'auto-generato il codice e la forza bruta di battere la maggior parte degli algoritmi sulla semplicità e prestazioni.Nella risposta precedente ho visto un sacco di ricorsione, la manipolazione degli array e calcoli, quando in realtà ciò che si vuole fare è:
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;
}
}
}
Naturalmente, non si può scrivere se non si conosce il numero di matrici sono in $array.Questo è dove il codice generato viene a portata di mano:
$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);
Si noti che questa procedura presuppone che $array è una base zero numericamente array, come nel tuo esempio.Verrà generato il codice sopra citato, rettificato per un numero arbitrario di matrici.
Aggiornamento
Ecco un algoritmo alternativo.E ' ancora auto-generato, ma meno di bruteforce.Abbiamo ancora nested loops, tranne che per ogni ciclo di opere su una copia della matrice in cui le chiavi sono attualmente utilizzati da esterno con passanti sono stati rimossi da questo ciclo l'array.Per esempio, se i valori dovrebbero essere (a,b,c) ma l'anello esterno sono utilizzando gli indici 0 e 2, è possibile rimuovere "a" (indice 0) e "c" (indice 2) e tutti ci hanno lasciato è "b".Significa che il loop funziona solo su combinazioni possibili e non abbiamo bisogno di un if condizione più.
Inoltre, questa parte può essere applicato l'algoritmo precedente, è il processo di array di valori in ordine dal più piccolo al più grande, in modo che possiamo garantire che utilizzati indici di esistere in matrice corrente.L'aspetto negativo è che non genera le combinazioni nello stesso ordine.Esso genera le stesse combinazioni, anche non nello stesso ordine.Il codice simile a questo:
$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";
}
}
}
Sopra routine imposta una copia dei valori all'inizio di ogni ciclo, quindi rimuove i valori che sono utilizzati da outer loop.È possibile migliorare questo processo di impostazione di una copia dei valori solo una volta all'inizio, rimuovere le chiavi in quanto sono utilizzati (all'inizio di ogni ciclo) e come essi vengono liberati (alla fine di ogni ciclo).La routine poi assomiglia a questo:
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];
}
Il codice che genera la fonte di cui sopra è:
$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);
Altri suggerimenti
problema interessante! Questa si è rivelata più complessa di quanto pensassi, ma sembra funzionare.
La strategia di base è quella di primo ordine gli array più piccolo al più grande (tenere traccia di quale ordine erano in, in modo da può produrre le risposte nell'ordine corretto).
Continuo risposte, sotto forma di una serie di indici in questo array ordinato di liste di ingresso.
Ora che le liste sono ordinati, posso archiviare la prima risposta corretta come array (0,1,2, ..., n);
Poi ricorsivamente una funzione per cercare tutti i valori nel primo slot lì (la 0 sopra) scambiando con altri valori in tale matrice risposta (tutti quelli che non sono troppo grandi per quello slot). Dal momento che li ho ordinati per dimensione, posso spostare qualsiasi valore a destra quando sto scambiando, senza preoccuparsi che sia troppo grande per quello slot a destra.
emissione di ogni slot valido ha qualche riferimento indiretto pazzo per annullare tutto l'ordinamento.
Scusate se questo sembra confuso. Non ho passato molto tempo a pulirlo.
<?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();
Credo che questo funziona. Sta usando la ricorsione per andare oltre la struttura come un albero. Per ogni ramo tiene traccia delle quali è già presi colonne. Probabilmente è lento perché è un approccio forza bruta.
<?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);
Probabilmente non è il modo più elegante, ma fa il trucco (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]);
}
}
}
}
}
Questo può essere riscritta utilizzando la ricorsione farlo funzionare con qualsiasi quantità arbitraria di array. Se trovo il tempo, darò una prova me stesso.
ps. Non so php, l'esempio è scritto in Delphi.
Modifica soluzione ricorsiva con # array arbitrarie
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.
vedere le cose da una prospettiva diversa: per comporre una riga del risultato, è necessario scegliere un valore per ogni colonna. Ogni valore deve essere raccolto da una riga di origine diversa. Il problema è sapere come "scegliere N di M", o più matematicamente, un Combinazione .
Ciò significa che una riga risultato corrisponde a una serie di indici sorgente-fila.
È possibile creare tutte le possibili guadagni per iniziare a costruire un indice-array come questo (pseudo-codice)
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 );
}
Un'altra opzione:
$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);
Il tuo problema è simile a quello di trovare un determinante di una matrice . Il modo migliore imho sarebbe quello di riempire gli array più piccoli con un po 'il simbolo, dire '0', in modo che tutti hanno uguale numero di valori, nel tuo esempio
$array = array(
array('1', '2', '0'),
array('a', 'b', 'c'),
array('x', 'y', '0'),
);
quindi scorrere ciascuno dei primi valori della matrice e per ogni incremento dell'indice di array 1 e controllare la seguente matrice e la colonna successiva (il primo ciclo sarà '1' e indice sarà 0 incrementato - 1 , quindi ottenere $ array 1 - 'b' e così via) se si raggiungere '0', rompere, se si raggiunge bordo destro, reimpostare primo indice a 0. Poi fare lo stesso con decremento e avrete tutte le combinazioni. Probabilmente è chiaro, controllare l'immagine ho collegato a
provare questo:
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);
