Die Suche nach all nicht in Konflikt Kombinationen von Werten aus mehreren Wertelisten

StackOverflow https://stackoverflow.com/questions/1378098

  •  21-09-2019
  •  | 
  •  

Frage

I weisen die folgende Anordnung, die Arrays von Werten enthält: 

$array = array(
    array('1', '2'),
    array('a', 'b', 'c'),
    array('x', 'y'),
);

Es kann eine beliebige Anzahl von Arrays und ein Array eine beliebige Anzahl von Werten enthalten kann. Ich habe noch ein Stück Code, das alle Kombinationen erzeugen, wo ein Wert von jedem Array genommen wird. zB: 

1ax, 1ay, 1bx, 1by, 1cx, 1cy, 2ax, 2ay, 2bx, 2by, 2cx, 2cy

Doch was ich will eigentlich nur die Kombinationen, in denen nur ein Wert in jeder Spalte sitzt, dh. 1ax ist nicht gut, weil alle drei Werte 1, a und x in der ersten Spalte sitzen, 1BY ist nicht gut, weil B und y in der zweiten Spalte sitzen. So aus dem obigen Beispiel nur diese Kombinationen wären gültig: 

1cy, 2cx

Ich habe ursprünglich geplant, nur alle Kombinationen erzeugen und dann die, die mit Konflikten herausfiltern, aber das nicht Maßstab, da dies ein stark vereinfachte Beispiel ist, in der realen Anwendung, es geht um Situationen, in denen es möglicherweise Millionen von Kombinationen ( einschließlich kollidiere).

Kann mir jemand helfen mit einem besseren Weg, dies zu lösen? Ich bin in PHP arbeiten, aber jedes Codebeispiel, das eindeutig die Logik zeigt, wäre hilfreich.

Vielen Dank im Voraus.

Update:

ich die Lösungen getestet haben, dass die Arbeit gegen einen größeren Datensatz einige Benchmarks zu bekommen, das sind die bisherigen Ergebnisse: 

$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. Lösung: 

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
War es hilfreich?

Lösung

Dies ist einer jener Fälle, in denen selbst generierten Code und Brute-Force meisten Algorithmen, die auf Einfachheit und Leistung schlagen. In früheren Antworten habe ich viele Rekursion, Array Manipulation und Berechnungen zu sehen, wenn in Wirklichkeit, was Sie tun wollen würde, ist: 

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;
        }
    }
}

Natürlich können Sie nicht schreiben, wenn Sie wissen, wie viele Arrays in $array sind. Das ist, wo generierte Code kommt praktisch: 

$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);

Beachten Sie, dass diese Routine, dass $array annimmt, ist ein Null-basiertes numerisch indiziertes Array, wie in Ihrem Beispiel. Es wird den Code generiert oben zitierte, für eine beliebige Anzahl von Feldern eingestellt.

Update

Hier ist ein alternativer Algorithmus. Es ist immer noch selbst erzeugt, aber weniger Brute-Force. Wir haben noch verschachtelte Schleifen, mit der Ausnahme, dass jede Schleife arbeitet auf einer Kopie des Arrays in dem Schlüssel, die zur Zeit von äußeren Schleifen verwendet werden, wird aus dieser Schleife des Arrays entfernt. Wenn die Werte sollte beispielsweise (a, b, c) sein, aber die äußeren Schleifen werden mit den Indizes 0 und 2, entfernen wir „a“ (Index 0) und „c“ (Index 2), und alles, was wir gelassen wird haben "b". Es bedeutet, dass Schleifen arbeiten nur auf mögliche Kombinationen und wir keine if Zustand mehr benötigen.

Darüber hinaus, und dieser Teil kann auch auf den vorherigen Algorithmus angewandt werden, verarbeiten wir die Arrays von Werten in der Reihenfolge von den kleinsten bis zum größten, so dass wir garantieren, dass verwendeter Indizes in aktuellen Array vorhanden ist. Der Nachteil ist es nicht die Kombinationen in der gleichen Reihenfolge zu erzeugen. Es erzeugt die gleichen Kombinationen, nur nicht in der gleichen Reihenfolge. Der Code sieht wie folgt aus: 

$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";
        }
    }
}

Die obige Routine richtet eine Kopie der Werte zu Beginn jeder Schleife, entfernt dann Werte, die von äußeren Schleifen verwendet werden. Sie können diesen Prozess verbessern, indem eine Kopie der Werte einrichten nur einmal am Anfang, entfernen Sie die Tasten, wie sie (am Anfang jeder Schleife) verwendet werden, und legt sie zurück, als sie befreit werden ( am Ende jeder Schleife). Die Routine geht dann wie folgt aussieht: 

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];
}

Der tatsächliche Code, der die Quelle oben erzeugt ist: 

$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);

Andere Tipps

Interessantes Problem! Dies erwies sich als komplexer zu sein, als ich dachte, aber es scheint zu funktionieren.

Basis-Strategie ist in erster Ordnung die Arrays der kleinsten zur größten (die Verfolgung von welcher Reihenfolge sie waren in, so kann ich geben die Antworten in der richtigen Reihenfolge).

Ich halte Antworten in Form einer Anordnung von Indizes in diese sortierten Array von Eingabelisten.

Nun, da die Listen sortiert werden, kann ich die erste richtige Antwort als Array speichern (0,1,2, ..., n);

Dann Rekursion ich in eine Funktion für den Versuch, alle Werte in dem ersten Schlitz dort (die 0 oben), indem sie es mit anderen Werten in dieser Antwort Array Swapping (alle diejenigen, die für diesen Schlitz nicht zu groß sind). Seit ich habe es nach Größe sortiert, kann ich jeden Wert nach rechts bewegen, wenn ich tauschen, ohne sich Gedanken über sie für das richtige Schlitz zu groß zu sein.

jeden gültigen Slot Ausgeben hat einige verrückte indirection alle die Sortierung rückgängig zu machen.

Sorry, wenn das sieht verwirrend. Ich habe nicht viel Zeit es aufzuräumen. 

<?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();

ich denke, das funktioniert. Es wird unter Verwendung von Rekursion wie ein Baum über die Struktur zu gehen. Für jeden Zweig hält sie verfolgen, welche Spalten bereits getroffen werden. Es ist wahrscheinlich langsam, weil es sich um eine Brute-Force-Ansatz ist. 

<?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);

wahrscheinlich nicht der eleganteste Weg, macht aber den Trick (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]);
        }
      }
    }
  }
}

Dies kann Refactoring mit Rekursion so dass es mit jeder beliebigen Menge von Arrays arbeiten. Wenn ich die Zeit finde, werde ich es versuchen mich.

ps. Ich weiß php nicht, wird das Beispiel in Delphi geschrieben.

Edit: rekursive Lösung mit beliebigen # Arrays 

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.

Sehen Sie es aus einem anderen Blickwinkel: um eine Ergebniszeile zu schreiben, müssen Sie für jede Spalte einen Wert auszuwählen. Jeder Wert sollte von einer anderen Quelle Reihe aufgenommen werden. Das Problem ist bekannt als „N auszusuchen von M“ oder mathematisch, eine Kombination .

Das bedeutet, dass ein Ergebnis Zeile entspricht einem Array von source-Zeilenindizes.

Sie können alle möglichen pickings bauen durch das Starten eines Index-Array wie diese (Pseudocode)

bauen 
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 );
}

Eine weitere 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);

Ihr Problem ist ähnlich der eine Determinante einer Matrix finden . Der beste Weg, imho wäre zu kleineren Arrays füllen mit einigen Symbol, sagen ‚0‘, so dass sie alle die gleiche Anzahl von Werten haben, in Ihrem Beispiel 

$array = array(
    array('1', '2', '0'),
    array('a', 'b', 'c'),
    array('x', 'y', '0'),
);

dann die Schleife durch jede der ersten Datenfeldwerte und für jedes Inkrement des Index des Arrays von 1 und prüfen Sie den nächsten Array und die nächste Spalte (auf der ersten Schleife wird es ‚1‘ und der Index wird 0 inkrementiert - 1 , dann $ array erhalten 1 - 'b' und so weiter), wenn Sie erreichen ‚0‘, Pause, wenn Sie mit der rechten Grenze erreichen, setzen erste Index auf 0. Dann das gleiche tun mit Erniedrigen und Sie werden alle Kombinationen haben. Es ist wahrscheinlich unklar, überprüfen Sie das Bild, das ich auf

verknüpft

versuchen, diese: 

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);
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top