Algorythmus für arraykombinationen

truespin

Professional

Posts: 378

Tuesday, March 23rd 2010, 7:34am

Algorythmus für arraykombinationen

guten morgen zusammen,

ich weiß, der titel ist nicht ganz so vielsagen wie er eigentlich sein sollte

könnte hilfe bei einem algorythmus brauchen...
in einme array habe ich acht einträge. jeweils einen buchstaben.
ich benötige alle möglichen kombinationen dieser buchstaben aber jeweils nur in dreier grüppchen.

beispiel:

im array: g, b, r, c, n, o, p, l

alle dreiergrüppchen:
gbr
gbc
gbn
gbo
gbp
bgl
grc
...

dabei ist auch die reihenfolge wichtig. heißt gbr != brg

das ganze dürften dann 8^3 * 6 möglichkeiten sein oder?

kann mir jemand weiter helfen?

thx, truespin

Rondrer

Professional

Posts: 306

Tuesday, March 23rd 2010, 8:25am

Also ich würde das einfach über 3 ineinander verschachtelte for-Schleifen machen, die jeweils durchs komplette Array laufen. Damit bekommst du dann zwar auch doppelte Buchsaben (also ggg,ggb etc) aber die Fälle lassen sich leicht durch Vergleich der Laufvariablen überspringen.
Ich denke es müssten 8 * 7 * 6 Kombinationen sein.

truespin

Professional

Posts: 378

Tuesday, March 23rd 2010, 9:41am

hallo,

danke für die antwort, so habe ich mir das auch gedacht. nur mit der abbruch bedingung hab ich noch meine probleme.
hier mal ein kleiner pseudocode wie ich mir das vorstelle:

für a = 0, solange a < array.length
für i = 1, solange i < array.length
für x = 2, solange x < array.length
für y = 0, solange y < testArray.length
testArray[y] = array[a] + array + array[x]
wenn y == testArray.length - 1
return testArray
ende wenn
wenn x == array.length - 1
x = 0
ende wenn
wenn i == array.length - 1
i = 0
ende wenn
wenn a == array.length - 1
a = 0
ende wenn
ende für y
ende für x
ende für i
ende für a

kann das so sein?
was mich noch intressieren würde, wie kommst du auf 8 * 7 * 6?

thx, truespin

Rondrer

Professional

Posts: 306

Tuesday, March 23rd 2010, 11:11am

das müsste Auswählen mit Beachtung der Reihenfolge (Variationen) sein (http://de.wikipedia.org/wiki/Kombinatori…8Variationen.29)
Und da lautet die Formel für deinen Fall n = 8, k = 3:
n! / (n-k)! = 8! / 5! = 8 * 7 * 6
(lustigerweise genau ein Beispiel in der Wikipedia ;) )

und ich hatte eher an sowas gedacht: (mehr oder weniger pseudocode)

Java Quellcode

int y = 0;
for a = 0 to array.length-1 {
  for i = 0 to array.length-1 {
    if (i == a) continue;
    for x = 0 to array.length-1 {
      if (x == a || x == i) continue;
      testArray[y] = array[a] + array[i] + array[x]; // wenn + konkatenation bedeutet
      y++;
 
    }
  }	
}