[recursie] Alle combinaties vinden in 2d array

[Robert]

hoi, ik zit al vrij lang te turen op een ogenschijnlijk goed op te lossen probleem. Ik heb een 2 dimensionaal array met plaatsen, en wil alle mogelijke combinaties (tussen de rijen) van die plaatsen vinden, dus op deze manier:

Array:
A1 A2 A3
B1 B2 B3
C1 C2 C3

Resultaat:
A1->B1->C1
A1->B2->C1
A1->B3->C1
A1->B1->C2
A1->B2->C2
A1->B3->C2
A1->B1->C3
A1->B2->C3
A1->B3->C3
A2->B1->C1
[....]
A3->B3->C3


Ik had even snel de code getypt voor als ik weet dat ik 3 rijen heb, maar kan even de stap niet maken naar een recursieve functie voor X aantal rows.

Perl:

for (my $i=0; $i<scalar(@{$hashArray[0]}) ;$i++){
        for (my $j=0; $j<scalar(@{$hashArray[1]}) ;$j++){
                for (my $k=0; $k<scalar(@{$hashArray[2]}) ;$k++){
                        print "$hashArray[0]->[$i]->{name} - ";
                        print "$hashArray[1]->[$j]->{name} - ";
                        print "$hashArray[2]->[$k]->{name}";
                        print "\n";
                }
        }
}

Zou super zijn als iemand me hiermee kon helpen

[Twazerty]

Met een tweedimensionaal array heb je maar 2 foreach loops nodig. Even uit de losse hand:

Java:

int[][] array2d = new int[30][30]; //30 rijen, iedere rij bevat 30 elementen, 900 elementen

for(int x = 0; x < array2d.length; x++){ //Loop door iedere rij heen
  for(int y = 0; y < array2d[x].length; y++){ //Loop door de elementen in een rij heen
    int element = array2d[x][y]; //Element
    System.out.println(element);
  }
}

Met de juiste aanpassing kun je de output krijgen die je nodig hebt. Een derde foreach loop zoals onder mij ook te zien is is overbodig. In het geval van een driedimensionaal array (int[][][]) heb je een derde foreach nodig.

[ Voor 101% gewijzigd door Twazerty op 31-07-2011 17:52 ]

[Verwijderd]

code:

foreach (array(A1, A2, A3) as A)
{
   foreach (array(B1, B2, B3) as B)
   {
      foreach (array(C1, C2, C3) as C)
      {
         print A.B.C;
      }
   }
}

[Robert]

Twazerty schreef op zondag 31 juli 2011 @ 17:29:
Met een tweedimensionaal array heb je maar 2 foreach loops nodig. Even uit de losse hand:

Java:

int[][] array2d = new int[30][30](); //30 rijen, iedere rij bevat 30 elementen, 900 elementen

for(int x = 0; x < array2d.length; x++){ //Loop door iedere rij heen
  for(int y = 0; y < array2d[x].length; y++){ //Loop door de elementen in een rij heen
    int element = array2d[x][y]; //Element
    System.out.println(element);
  }
}

Met de juiste aanpassing kun je de output krijgen die je nodig hebt. Een derde foreach loop zoals onder mij ook te zien is is overbodig.

Met die code loop je wel door het array, maar het gaat er hier om dat ik routes vindt zoals in topicstart. Met een array van 30*30 ints zou ik b.v. zo'n resultaat willen krijgen:

0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,1
0,0,0,0,0,0,0,0,0,2
etc..t/m:
30,30,30,30,30,30,30,30,30,30

die 3 foreach loops gaan dus over het aantal rijen in dit geval, niet om de dimensies van het array.

Verwijderd schreef op zondag 31 juli 2011 @ 17:34:

code:

foreach (array(A1, A2, A3) as A)
{
   foreach (array(B1, B2, B3) as B)
   {
      foreach (array(C1, C2, C3) as C)
      {
         print A.B.C;
      }
   }
}

thanks, maar dan moet je wel al weten dat er 3 rijen zijn met 3 elementen toch. Het is een variabel array, dus zowel het aantal rijen als het aantal columns per rij kan verschillen, dit moet b.v. ook kunnen:

A1, A2, A3, A4
B1, B2,
C1, C2, C3

[ Voor 23% gewijzigd door Robert op 31-07-2011 17:59 ]

[Twazerty]

Dan moet je de resultaten tussentijds even opslaan in een variable:

Java:

int[][] array2d = new int[30][30]; //30 rijen, iedere rij bevat 30 elementen, 900 elementen

for(int x = 0; x < array2d.length; x++){ //Loop door iedere rij heen
  String row = "";
  for(int y = 0; y < array2d[x].length; y++){ //Loop door de elementen in een rij heen
    row += array2d[x][y] + ", "; //Element toevoegen aan de string
  }
  System.out.println(row);
}

Edit: In jouw voorbeeld heb je juist een driedimensionaal array getoond als voorbeeld ipv een tweedimensionaal array, toch?

In een tweedimensionaal array van int[3][3] zijn er 9 combinaties/paden mogelijk (3 * 3). In een driedimensionaal array van int[3][3][3] zijn er 27 combinaties/paden mogelijk (3 * 3 * 3) zoals in je voorbeeld te zien is.

[ Voor 35% gewijzigd door Twazerty op 31-07-2011 18:12 ]

[Nactive]

Java:

    public static void printAlleMogelijkHeden(String[][]arr, int j, String[] opl) {
        if (j < arr.length) {
            for (int i = 0; i < arr[j].length; i++) {
                opl[j] = arr[j][i];
                printAlleMogelijkHeden(arr, j + 1, opl);
            }            
        } else {
            for (String s : opl)
                System.out.print(s);
            System.out.println("");
        }
    }

oproepen doe je dan op volgende methode

Java:

            arr[0][0] = "a1";
            arr[0][1] = "a2";
            arr[0][2] = "a3";

            arr[1][0] = "b1";
            arr[1][1] = "b2";
            arr[1][2] = "b3";

            arr[2][0] = "c1";
            arr[2][1] = "c2";
            arr[2][2] = "c3";

            String[] opl = new String[3];
            printAlleMogelijkHeden(arr, 0, opl);

[ Voor 21% gewijzigd door Nactive op 31-07-2011 18:26 ]

[RayNbow]

Monads to the rescue!

ghci> let rows = map words . lines $ "A1 A2 A3\nB1 B2 B3\nC1 C2 C3"

ghci> rows
[["A1","A2","A3"],["B1","B2","B3"],["C1","C2","C3"]]

ghci> sequence rows
[["A1","B1","C1"],["A1","B1","C2"]
...
["A3","B3","C1"],["A3","B3","C2"],["A3","B3","C3"]]

Definitie van sequence:

Haskell:

sequence :: (Monad m) => [m a] -> m [a]
sequence []     = return []
sequence (x:xs) = do v <- x; vs <- sequence xs; return (v:vs)

Gespecialiseerd naar lijsten:

Haskell:

sequenceList :: [[a]] -> [[a]]
sequenceList []     = [[]]
sequenceList (x:xs) = [(v:vs) | v <- x, vs <- sequenceList xs]

Equivalente Python versie:

Python:

def sequenceList(L):
    if not L:
        return [[]]
    else:
        results = []
        
        x, xs = L[0], L[1:]
        for v in x:
            for vs in sequenceList(xs):
                results.append([v] + vs)
        
        return results
        
        # of:
        # return [ [v]+vs for v in x for vs in sequenceList(xs) ]

[Robert]

thanks iedereen voor het meedenken, die recursieve java functie was precies wat ik ook wilde maken maar waar mijn denkproces even faalde

Die monads moet ik ook eens even bekijken, nog nooit van gehoord

[RayNbow]

Monads zijn wezens uit de wiskundige wereld van Category Theory. Vele mensen vinden deze schepsels eng.

Maar goed, een monad in de programmeervoorbeeld is een typeconstructor met bepaalde eigenschappen. Als we C++/Java/C# notatie gebruiken, dan is een monad M iets dat de vorm M<A> heeft. Als we bijvoorbeeld List<String> hebben, dan zou M=List de monad in kwestie zijn.

M is een monad als je de volgende functies kunt schrijven:

Java:

M<A> unit(A x) {/* ... */}
M<B> map(Function<A,B> f, M<A> mx) {/* ... */}
M<A> join(M<M<A>> x) {/* ... */}

(Deze functies moeten ook nog aan bepaalde eigenschappen voldoen, maar die laat ik buiten beschouwing)

Probeer deze functies eens te implementeren voor List:

Java:

List<A> unit(A x) {/* ... */}
List<B> map(Function<A,B> f, List<A> mx) {/* ... */}
List<A> join(List<List<A>> x) {/* ... */}