Algorithmus zur Kombinatorik

Barbarossa

Hallo

Nachdem man mir in diesem Forum schon vor kurzem tolle Buchtipps geben konnte (ich habe "Algorithmen mit C" bestellt, ist für ein Einsteiger sicher besser) erlaube ich mir nochmal eine Frage zu stellen

Well my question: Ich habe x char-Arrays mit jeweils n Felder. (z. B. drei Arrays mit je 2 Elementen, die könnten z.B. folgende Zeichen beinahlten:

F K
O E
N S

)

Nun möchte ich alle möglichen Strings kombinieren, wobei aus jedem Array genau ein Zeichen kommt. Für den obigen Fall also:

1 FON
2 FOS
3 FEN
4 FES
5 KON
6 KOS
7 KEN
8 KES

Ich kriege aber den nötigen Algo nicht hin Mein Bauchgefühl sagt mir, dass ich zwei Schleifen ineinander Verschachteln muss, ich habe schon herumexperimentiert aber es nicht hingekriegt.

Hat jemand ein Tipp oder gar die Lösung?

Danke schon im Voraus

SeppJ

Barbarossa schrieb:

Ich kriege aber den nötigen Algo nicht hin Mein Bauchgefühl sagt mir, dass ich zwei Schleifen ineinander Verschachteln muss, ich habe schon herumexperimentiert aber es nicht hingekriegt.

Genau das ist der Ansatz. Was genau geht denn bei dir nicht?

Barbarossa

Ehrlich gesagt funktioniert "das Ganze" nicht. Ich krieg ned auf die Reihe

Th69

Bei drei Arrays brauchst du aber drei(!) ineinander verschachtelte Schleifen...

// Pseudocode
for(a in "FK")
  for(b in "OE")
    for(c in "NS")
      print a b c

Barbarossa

Th69 schrieb:

Bei drei Arrays brauchst du aber drei(!) ineinander verschachtelte Schleifen...
// Pseudocode
for(a in "FK")
  for(b in "OE")
    for(c in "NS")
      print a b c

Mhh ja aber gibt es nicht eine allgemeingültige Lösung? Wenn z.B. erst während er Laufzeit bekannt ist wieviele Arrays es sind? Oder wenn es 50 Arrays sind (50 Verschachtelungen...)

lg BArbarossa

knivil

Warum willst du es unbedingt in C oder C++ machen? Hier eine simple Loesung in Haskell, wobei man sich auch die erste Zeile sparen kann:

combine :: [String] -> [String]
combine [] = [[]]
combine (x:xs) = [ a:as | a <- x,  as <- combine xs ]

*Main> combine ["FK","OE","NS"]
["FON","FOS","FEN","FES","KON","KOS","KEN","KES"]

Th69

Eine allgemeingültige Lösung gibt es mittels dynamischer Programmierung (s. z.B. Rucksackproblem) bzw. Rekursion mit eigenen Stack für die Indizes.
(Am Wochenende kann ich dir mal den Code in C posten, wenn Interesse besteht...)

oder probier mal so:

#include <stdio.h>
#include <string.h>
#include <math.h>

void combi (char *a[], int strings, int size)  // 3, 2
{
  int loops = (int)pow(size, strings);
  int s, t;
  for (s=0; s<loops; s++)
  {
    int n = loops/size;
    for (t=0; t<strings; t++)
    {
      putchar (a[t][s/n % size]);
      n = n/size;
    }
    puts ("");
  }
}

int main (void)
{
  char *a[] = {"FK","OE","NS", "12"};  // <-- alle strings gleich lang!
  combi (a, sizeof(a)/sizeof(*a), (int)strlen(a[0]));
}

^^oberflächlich ausprobiert, scheint zu klappen. aber vielleicht gehts ja noch einfacher (rekursiv z.b.)

Bashar

Naja, "einfacher" ist da relativ. Ist auch nicht ganz so hübsch wie die Haskell-Variante.

#include <stdio.h>
#include <string.h>

void combi(char **array, int n, int pos, int l, char string[]) {
  if (pos == n)
    puts(string);
  else {
    int i;
    for (i = 0; i < l; ++i) {
      string[pos] = array[pos][i];
      combi(array, n, pos+1, l, string);
    }      
  }
}

int main() {
  char *array[] = { "FK", "OE", "NS", "12" };
  char storage[sizeof(array)/sizeof(*array)+1] = { 0 };
  combi(array, sizeof(array)/sizeof(*array), 0, strlen(*array), storage);
  return 0;
}

Bashar schrieb:

Naja, "einfacher" ist da relativ. Ist auch nicht ganz so hübsch wie die Haskell-Variante.

trotzdem sehr schön *daumen_hoch*

Barbarossa

Danke genau das hab ich gesucht