Matrixelemente Kombination

Question

Es gibt ein m x n Array, ich muss jede mögliche Kombination von jedem Element der Zeile ausgeben. Zum Beispiel für das Array {{1,2,3},{4,5,6}} muss ich {{1,4},{1,5},{1,6},{2,4},{2,5},{2,6},{3,4},{3,5},{3,6}} ausgeben.

---

Ich denke, es sollte eine m-Schleife sein, um dies zu lösen. Für das obige Beispiel, schrieb ich den Code:

 int[,] array = new int[,] {{1, 2, 3}, {4, 5, 6}}; 

     for (var i = 0; i < 3; i++) 
     { 
      for (var j = 0; j < 3; j++) 
      { 
       Console.WriteLine($"{{{array[0, i]},{array[1, j]}}}"); 
      } 
     } 

Mit m ändert, wird die Anzahl der for Schleife ändert sich auch. Aber m ist unbekannt, wenn ich den Code schreibe. Wie kann ich es lösen?

Answer 1

Pflegen Sie eine Liste der aktiven Kombinationen c. Initialisieren Sie c, um die erste Zeile des Arrays zu sein. Wiederholen Sie dann jede weitere Zeile und aktualisieren Sie c. Grundsätzlich erweitern Sie jede der aktuellen Kombinationen mit jedem Element der Zeile. Hier sind einige Pseudo-Code:

c = array[0]; //read: the first row of the array 
for(var i = 1; i < m; ++i) { //iterate all rows 
    var c_modified = []; 
    for(var j = 0; j < n; ++j) { //iterate all row entries 
     for(var k = 0; k < c.length; ++k) { //iterate all entries of c 
      add c[k].array[i, j] to c_modified; // . represents concatenation 
     } 
    } 
    c = c_modified; 
} 

Answer 2

Diese Kombination von Elementen (n^m Sätze) wird kartesisches Produkt bezeichnet. Es gibt gebrauchsfertige Funktionen für seine Erzeugung in einigen Sprachbibliotheken

Ich glaube, dass der einfachste Code rekursiv ist.

type 
    TArr2D = TArray<TArray<Integer>>; 

procedure CartesianProduct(const A: TArr2D; Line: Integer; Reslt: TArray<Integer>); 
var 
    i: integer; 
begin 
    if Line > High(A) then 
    Memo1.Lines.Add(ArrayToString(Reslt)) // output m-element set 
    else 
    for i in A[Line] do 
     CartesianProduct(A, Line + 1, Reslt + [i]); // include element in set 
end; 

var 
    A: TArr2D; 
    n, m, i, j: Integer; 
begin 
    m := 3; 
    n := 3; 
    SetLength(A, m, n); 
    for j := 0 to m - 1 do 
    for i := 0 to n - 1 do 
     A[j, i] := j * n + i; 
    //0 1 2 
    //3 4 5 
    //6 7 8 

    CartesianProduct(A, 0, []); 

gibt

0 3 6 
0 3 7 
0 3 8 
0 4 6 
0 4 7 
0 4 8 
0 5 6 
0 5 7 
0 5 8 
1 3 6 
1 3 7 
1 3 8 
1 4 6 
1 4 7 
1 4 8 
1 5 6 
1 5 7 
1 5 8 
2 3 6 
2 3 7 
2 3 8 
2 4 6 
2 4 7 
2 4 8 
2 5 6 
2 5 7 
2 5 8