Auswahl von k aus n möglichen Elementen

Java-Forum Java-Grundlagen
1

hi liebe leser,

ich habe ein kleines großes problem. es geht um etwas sehr simples, aber google konnte mir in den letzten TAGEN dazu nichts finden. thema stochastik --> kombinatorik.

Auswahl von k aus n möglichen Elementen
genauer gesagt variationen MIT wiederholungen.

kleines beispiel mit 1,2,3
111, 112, 113, 121, 122, 123, 131, 132, 133, 211, 212, 213, 221, 222, 223, 231, 232, 233, 311, 312, 313, 321, 322, 323, 331, 332, 333,

permutationen sind ähnlich, aber mir geht es um variationen.

die beste seite dazu die mir die ergebnisse auch ausspuckt, ist diese:
http://www.zum.de/Faecher/Materialien/gebhardt/stochastik/Kombin.html
(siehe zweite tabelle)

leider funktioniert diese nur bis zu 1000 möglichkeiten. ich bräuchte alle ergebnisse zu der aufgabe 20 hoch 3. das macht 8000 möglichkeiten. die werte liegen zwischen 0,1 - 2,0 (genau 20 schritte)

3 beispiele aus den 8000 werten:
0,1 1,4 2,0
0,3 0,8 0,8
1,5 1,1 0,7

die 8000 ergebnisse muss ich danach bei excel einfügen. leider fehlt dem office für macs 2008 die makro funktion (VBA), deswen würden mir hilfen in diesem wege nichts nützen. ich wäre euch sehr sehr dankbar, wenn vllt jemand mir soetwas schreiben könnte. irgendwann würde ich vielleicht sogar 30 hoch 3 ausprobieren für meine kleine tabelle. das wären dann 27000 möglichkeiten.

vielen dank für eure hilfe

2

du willst also eine methode haben die dir die Anzahl der Moeglichkeiten gibt ?

weiss nicht ob ichs richtig verstanden habe…

wenn ja - nutz groovy :smiley:

def l = [1,2,3,4,5,6,7]
def com = l.inject([]) { list, element -> list << l}
println com.combinations().size()

gibt aber bestimmt auch ne lib fuer java die dir das berechnet… (bis 7 elemente gehts ohne heap space erhoehung… das sind schonmal 823543 moeglichkeiten)

lol - wenns nur um die anzahl geht ists ja einfach - egal welche sprache
totalNr = Math.power(laenge,laenge)
(generell gesprochen)

oder geht es dann doch explizit um alle Moeglichkeiten ?

3

Ich hatte in einem “Konkurrenzforum” mal so eine Utility-Klasse für solche Aufgaben gepostet… Aber… Stell’ dir vor, du solltest alle Möglichketen auflisten, 3 Elemente aus den Ziffern 0…9 auszuwählen. Das wäre dann
000
001
002
…
009
010
011
012
…
020
021
…
…
100
101

… Ja: Es wird nur gezählt!

Wenn es um Ziffern von 0 bis n-1 gehen würde, gäbe es da sogar einen SEHR einfachen Trick:

int max = Math.pow(n, k);
for (int i=0; i<max; i++)
{
    System.out.println(Integer.toString(i, n)); // Ggf. noch mit 0en auffüllen
}

Ansonsten (für Ziffern von 1 bis n) muss man das “händisch” machen - aber das ist auch nur Zählen. Im Pseudocode

void create()
{
    int selection[] = new int[k]; // Mit 1en füllen...
    int max = Math.pow(n, k);
    for (int i=0; i<max; i++) increase(selection, k-1);
}

void increase(int selection[], int position)
{
    if (position<0) return; // "Überlauf" -> Fertig
    selection[position]++;
    if (selection[position]>n)
    {
        selection[position] = 1;
        increase(selection, position-1);
    }
}

Die increase-Methode erhöht eine bestimmte Stelle um 1, und überträgt einen “Überlauf” auf die weiter vorne stehenden Stellen:
111
112
…
119 -> Erhöhe letzte Stelle um 1 -> Überlauf! Letzte stelle auf 1 setzen und vorletzte erhöhen ->
121
122
…

4

@Marco13
wie handelst du dann eine beliebige Zahlenfolge bzw allg Zeichenfolge, die man eben nicht ueber +1 errechnen kann.

Z.b.

  • 4, 9, 23
  • a, g, h
  • 0.01, 0.45, 2

?

5

Das sind “Dinge”. Es gibt ein erstes, ein zweites, … und ein n-tes (letztes). Und man zählt an einer Stelle von 1 bis n, springt dann zurück auf 1 und erhöht die nächste Stelle um 1. Bei Zahlen:

00
01
02
…
09
10
11
…

Bei Buchstaben:
AA
AB
AC
…
AJ
BA
BB
…

Es werden praktisch immer die Zahlen von 0 bis n-1 auf die n “Objekte” abgebildet - stellenweise.

6

ohja… mea culpa…

dennoch finde ich die Java loesung mehr als schwierig zu lesen… nun ja - es klappt :smiley: