Recherche de toutes les combinaisons de valeurs non conflictuelles à partir de plusieurs listes de valeurs
https://stackoverflow.com/questions/1378098
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai le tableau suivant qui contient des tableaux de valeurs :
$array = array(
array('1', '2'),
array('a', 'b', 'c'),
array('x', 'y'),
);
Il peut y avoir n'importe quel nombre de tableaux et un tableau peut contenir n'importe quel nombre de valeurs.J'ai actuellement un morceau de code qui générera toutes les combinaisons où une valeur est extraite de chaque tableau.par exemple:
1ax, 1ay, 1bx, 1by, 1cx, 1cy, 2ax, 2ay, 2bx, 2by, 2cx, 2cy
Cependant, ce que je veux réellement, ce sont uniquement les combinaisons où une seule valeur se trouve dans chaque colonne, c'est-à-dire.1ax n'est pas bon car les trois valeurs 1, a et x se trouvent dans la première colonne, 1by n'est pas bon car b et y se trouvent dans la deuxième colonne.Ainsi, d'après l'exemple ci-dessus, seules ces combinaisons seraient valides :
1cy, 2cx
J'avais initialement prévu de simplement générer toutes les combinaisons, puis de filtrer celles avec des conflits, mais cela ne s'applique pas car il s'agit d'un exemple trop simpliste. Dans l'application réelle, il y aura des situations où il y aura potentiellement des millions de combinaisons (y compris celles en conflit). ).
Quelqu'un peut-il nous aider avec une meilleure façon de résoudre ce problème ?Je travaille en PHP, mais tout exemple de code démontrant clairement la logique serait utile.
Merci d'avance.
Mise à jour:
J'ai testé les solutions qui fonctionnent sur un ensemble de données plus important, pour obtenir quelques points de référence, voici les résultats jusqu'à présent :
$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ème solution :
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
La solution
Ceci est l'un de ces cas où le code autogénérés et la force brute battra la plupart des algorithmes sur la simplicité et la performance. Dans les réponses précédentes, j'ai vu beaucoup de récursivité, la manipulation des tableaux et des calculs, alors qu'en réalité ce que vous voulez faire est la suivante:
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;
}
}
}
Bien sûr, vous ne pouvez pas écrire si vous ne savez combien de tableaux sont en $array. C'est là le code généré est à portée de main:
$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);
Notez que cette routine suppose que $array est un tableau indexé numériquement base zéro, comme dans votre exemple. Il va générer le code cité ci-dessus, ajusté pour tenir compte d'un nombre arbitraire de tableaux.
Mise à jour
Voici un autre algorithme. Il est encore autogénérés, mais moins bruteforce. Nous avons encore des boucles imbriquées, sauf que chaque boucle fonctionne sur une copie du tableau où les clés qui sont actuellement utilisées par des boucles extérieures ont été retirées du tableau de cette boucle. Par exemple, si les valeurs doivent être (a, b, c), mais les boucles externes utilisent les indices 0 et 2, nous enlever « a » (indice 0) et « c » (indice 2) et tout ce qu'il nous reste est "b". Cela signifie que les boucles ne fonctionnent que sur les combinaisons possibles et on n'a pas besoin d'une condition de if plus.
En outre, et cette partie peut être appliqué à l'algorithme précédent ainsi, nous traitons les tableaux de valeurs dans l'ordre du plus petit au plus grand afin que nous garantissons que les indices utilisés existent dans le tableau en cours. L'inconvénient est qu'il ne génère pas les combinaisons dans le même ordre. Il génère les mêmes combinaisons, mais pas dans le même ordre. Le code ressemble à ceci:
$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";
}
}
}
La routine ci-dessus met en place une copie des valeurs au début de chaque boucle, puis supprime les valeurs utilisées par des boucles extérieures. Vous pouvez améliorer ce processus en mettant en place une copie des valeurs une seule fois au début, supprimez les clés comme ils sont utilisés (au début de chaque boucle) et les remettre comme ils sont libérés ( à la fin de chaque boucle). La routine ressemble alors à ceci:
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];
}
Le code réel qui génère la source ci-dessus est la suivante:
$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);
Autres conseils
Problème intéressant! Cela est avéré être plus complexe que ce que je pensais, mais il semble fonctionner.
La stratégie de base est de premier ordre les tableaux le plus petit au plus grand (garder une trace de quel ordre ils étaient, donc je peux sortir les réponses dans l'ordre correct).
Je garde des réponses sous la forme d'un tableau d'index dans ce tableau des listes triées de saisie.
Maintenant que les listes sont triées, je peux stocker la première réponse sous forme de tableau (0,1,2, ..., n);
Alors je RECURSE en fonction pour essayer toutes les valeurs dans la première fente il (le 0 ci-dessus) en échangeant avec d'autres valeurs dans ce tableau de réponse (tous ceux qui ne sont pas trop grand pour cet emplacement). Depuis que je l'ai trié par taille, je peux passer toute valeur à droite quand j'échange, sans se soucier qu'il soit grand pour ce créneau droit.
délivrer en sortie chaque fente valide a une certaine indirection fou pour défaire tout le tri.
Désolé si cela semble confus. Je ne l'ai pas passé beaucoup de temps le nettoyer.
<?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();
Je pense que cela fonctionne. Il utilise la récursivité pour aller au-dessus de la structure comme un arbre. Pour chaque branche, il garde la trace des colonnes sont déjà prises. Il est probablement lente, car elle est une approche de la force brute.
<?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);
probablement pas la façon la plus élégante, mais le tour est joué (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]);
}
}
}
}
}
Cela peut être à l'aide récursion refactorisé le faire fonctionner avec une quantité arbitraire de tableaux. Si je trouve le temps, je vais le donner moi-même essayer.
ps. Je ne sais pas php, l'exemple est écrit en Delphi.
Edit: solution récursive avec des tableaux arbitraires #
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.
Regardez-le sous un autre angle :afin de composer une ligne de résultats, vous devez choisir une valeur pour chaque colonne.Chaque valeur doit être sélectionnée dans une ligne source différente.Le problème est connu sous le nom de « choisir N parmi M », ou plus mathématiquement, un Combinaison.
Cela signifie qu'une ligne de résultat correspond à un tableau d'indices de ligne source.
Vous pouvez créer tous les choix possibles en commençant à créer un tableau d'index comme celui-ci (pseudo-code)
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 );
}
Une autre option:
$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);
Votre problème est similaire à celui de trouver un déterminant d'une matrice . La meilleure façon serait IMHO de combler les petits tableaux avec un symbole, dire « 0 », ils ont tous le même nombre de valeurs, dans votre exemple
$array = array(
array('1', '2', '0'),
array('a', 'b', 'c'),
array('x', 'y', '0'),
);
puis une boucle à travers chacune des premières valeurs de tableau et pour chaque incrément de l'indice de matrice de 1 et vérifier la prochaine rangée et la colonne suivante (sur la première boucle, il sera « 1 » et l'index sera de 0 incrémentée - 1 , puis obtenir $ array 1 - 'b' et ainsi de suite) si vous atteindre « 0 », casser, si vous atteignez la bordure droite, réinitialiser premier index à 0. Ensuite, faites la même chose avec décrémentation et vous aurez toutes les combinaisons. Il est sans doute pas clair, vérifier l'image que je lié à
essayez ceci:
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);
