kombinatorik

[Lutz]

Hallo Zusammen,

ich habe folgende Problemstellung:

Ich habe eine bestimmte Menge von Werten. Diese Werte muss wiederholt ich in einem zweidimensionalen Array ablegen und zwar so, dass alle möglichen Kombinationen der Werte in der zweiten Dimension einmalig auf eine fest vorgebene erste Dimension verteilt werden. Vielleicht ein Beispiel:

Ich gebe die erste Arraydimension mit 3 vor.

Ich habe die Werte 1, 2, 3, 4

die Ergebnisarrays könnten z.B. wie folgt aussehen:

1 - -
2 - -
3 - -
4 - -

1 4 -
2 - -
3 - -

1 3 -
2 4 -

1 2 -

• 3 -
• 4 -

// Nächstes Ergebnis entfällt, da die Kombination aus
// 1-2-3-4 innerhalb von einem Index der ersten Dim
// schon in Ergebnis 1 enthalten waren.

1 2 4

• 3 -

• 1 4

• 2 -

• 3 -

usw usf.

Bei diesem Beispiel könnte die Aufgabe also mit "Alle Möglichen Kombination der Zahlen verteilt auf 3 Indizies, wobei jede Kombination nur ein mal vorkommen darf, unabhängig davon in welchem Indizie.

Ich komme bei der Lösung dieses Problems nicht weiter. Eine einfache Permutation kann ja mit Hilfe einer rekursiven Funktion relativ einfach gelöst werden. Ich komme aber nicht darauf, wie ich die Permutation auf die mehreren Indizies verteile und so sämtliche einfache Kombinationen erreiche.

Viele Dank für Eure Hilfe,

Lutz

[frankx]

Hellihello lutz,

sorry, ich kapiers nicht, was sollen die striche da?

Gruß,

frankx

[Lutz]

Hallo fankx,

sorry, ich kapiers nicht, was sollen die striche da?

Die Striche heißen soviel wie das ist nichts drin. Ziel ist es eine Möglichkeit zu entwickeln welche es ermöglicht sämtliche Kombinationen der Werte in Bezug zu n (in diesem Fall 3) Einheiten zu betrachten. Und zu diesen Kombinationen gehört es halt auch das in Einheit 1 alle Werte sind und in Einheit 2 u. 3 kein Wert. Sorry wenn ich das missverständlich formuliert habe.

Gruß,

Lutz

[frankx]

Hellihello lutz,

wäre dann vielleicht die Verwendung der Zahl 0 hilfeich?

ist aus deiner sicht dann

1 0 0 0

ident mit

0 0 0 1 ?

Gruß,

frankx

[Lutz]

Hallo,

wäre dann vielleicht die Verwendung der Zahl 0 hilfeich?

Ich wollte vermeiden das "0" als ein Wert aus der Menge interpretiert wird. "null" trifft es vielleicht besser. Ich fand den Strich auch ganz ok, hätte vielleicht was dazu sagen sollen.

ist aus deiner sicht dann

1 0 0 0

ident mit

0 0 0 1 ?

Ja. Wenn wir von vier Einheiten ausgehen und einem Element was in allen unterschiedlichen Komibnationen auf die Einheiten verteilt wird gibt es genau eine Möglichkeit, da es unrelevant ist in welcher Einheit die Kombination (hier 1) Vorkommt.

Gruß,

Lutz

[frankx]

Hellihello,

also irgendwas wie bernoulli-ketten. warum du dich vor der null so scheust, weiß ich nicht. die null im mathematischen sinn ist doch dafür da, das nichtvorhandensein darzustellen. in einem array macht es doch vielleicht auch mehr sinn, die plätze zu füllen.

naja, weiß jetzt auch nicht, ob die NULL hier besser angebracht wäre.

bei zahlen von 1-4 und 3 stellen wären als deine ergebnisse:

NULL
1
2
3
4
12
13
14
22
23
24
33
34
44
111
112
113
114
122
123
124
133
134
144
222
223
224
233
234
244
333
334
344
444

???

Gruß,

frankx

[Lutz]

Hallo,

???

Nein, Irgendwie nicht. Es geht nicht um zu errechnende Wahrscheinlichkeit.

Ich probiere das Problem allgemeiner zu beschreiben: Man hat eine Menge von Objekten. Diese Objekte gilt es in eine bestimmte Anzahl von Bereichen abzulegen (Dazu sollten meine Indizies erster Dimension in dem Array dienen) und zwar für jede Mögliche Kombination ein mal.

Ein Beispiel: Man hat die Kinder Kasper, Basti und Danni. Diese Kinder sollen sich, nacheinander auf zwei Flächen ("ob Ihr richtig steht oder nicht...") in allen unterschiedlichen Kombinationen verteilen. Hier gebe es folgende Kombinationen:

K1: Alle stehen auf Fläche 1, auf Fläche 2 steht kein Kind:

K2: K, B auf Fl. 1, D auf Fläche 2.

K3: K auf 1, B und D auf Fläche 2;

K4: K und D auf 1, B auf 1

Wobei es egal ist auf welcher Fläche die Kinder zusammen stehen, wichtig sind nur die Kombinationen. (Also Basti ein mal alleine während Kasper und Danni zusammen stehen, Ein mal Basti mit Kasper wobei danni alleine steht, ein mal kasper danni und basit zusammen wobei auf der anderen Fläche keiner steht usw.)

Anzahl der Kinder und der Fläche muss variable handhabbar sein. Und hier habe ich keinen Ansatz wie ich das als Algorithmus formulieren könnte...

Viele Grüße und Danke fürs Interesse,

Lutz

[Gunnar Bittersmann]

Hello out there!

Hab ich das richtig verstanden? Du willst n Werte (in deinem Beispiel vier: 1, 2, 3, 4) unabhängig voneinander auf k Töpfe (in deinem Beispiel drei; nennen wir sie A, B, C) aufteilen, wobei die Reihenfolge der Werte in den Töpfen keine Rolle spielt?

Erzeuge dir also alle n^k Kombinationen mit Wiederholungen

AAAA
AAAB
AAAC
AABA
.
.
.
CCCC

BCAB bedeutet bswp. 1 in Topf B, 2 in C, 3 in A, 4 in B, in deiner Schreibweise

3 1 2

• 4 -

---

---

See ya up the road,
Gunnar

[Lutz]

Hallo Gunnar,

vielen Dank für Dein Post. Das ist auf jeden Fall ein Ansatz. Also ist es doch mit Permutation lösbar. Ich habe das Problem bloß von der falschen Richtung betrachtet, von den "Töpfen" anstatt von den Werten aus. Du gibst dem Wert quasi eine "TopfID" und kommst so zu den Kombinationen.

Allerdings habe ich viele Kombinationen doppelt. Beispielsweise sind bei AAAA, BBBB und CCCC so ja alle Elemente in einem Topf, die beiden anderen sind leer, die Kombination ist also die gleiche, siehst du eine Möglichkeit dies bei der Erzeugung der Permutation abzufangen?

@frankx: Ich denke das ist auch das, was du mir in deinem letzten Post mitteilen wolltest.

Gruß u. Dank,

Lutz

[Sven Rautenberg]

Moin!

vielen Dank für Dein Post. Das ist auf jeden Fall ein Ansatz. Also ist es doch mit Permutation lösbar. Ich habe das Problem bloß von der falschen Richtung betrachtet, von den "Töpfen" anstatt von den Werten aus. Du gibst dem Wert quasi eine "TopfID" und kommst so zu den Kombinationen.

Allerdings habe ich viele Kombinationen doppelt. Beispielsweise sind bei AAAA, BBBB und CCCC so ja alle Elemente in einem Topf, die beiden anderen sind leer, die Kombination ist also die gleiche, siehst du eine Möglichkeit dies bei der Erzeugung der Permutation abzufangen?

Klingt irgendwie wie "Türme von Hanoi", zumindest optisch. :)

Diese Einschränkung der Duplikate bedeutet jedenfalls, dass man das Resultat (mit Dopplungen) noch "normalisieren" soll. Also: Töpfe nach "links" schieben. Im Endeffekt also den Topf mit den meisten Elementen als "A" bezeichnen, den mit den zweitmeisten als "B", und den mit den wenigsten als "C" (bei drei Töpfen).

Was wiederum für die Permutationen und die Verteilung auf die Töpfe bedeutet: Topf A hat mindestens soviele Elemente, wie Topf B. Topf B hat mindestens soviele Elemente wie Topf C. |A| >= |B| >= |C|

Das wiederum bedeutet, dass man eigentlich doch eher von den Elementen ausgehen muß. Am Anfang sind alle Elemente in Topf A. Dann wird eines der Elemente von A nach B getan, und ergibt eine neue Kombination. Für alle Elemente durchführen.

Das Element jetzt von B nach C tun ist verboten, weil |B|=0 >= |C|=1 nicht erfüllt wäre, also muß ein weiteres Element von A nach B getan werden. Das wieder für alle Kombinationen machen.

Jetzt darf ein Element von B nach C getan werden, weil danach |B|=1 >= |C|=1.

Und so weiter... :)

- Sven Rautenberg

[Lutz]

Hallo Gunnar,

Das wiederum bedeutet, dass man eigentlich doch eher von den Elementen ausgehen muß.

Das bringt mich dan wieder zu den gleichen Problemen die ich vor dem ersten Post hatte.

Deine Einschränkung:

»»Am Anfang sind alle Elemente in Topf A. Dann wird eines der Elemente von A nach B getan, und ergibt eine neue Kombination. Für alle Elemente durchführen.

Das Element jetzt von B nach C tun ist verboten, weil |B|=0 >= |C|=1 nicht erfüllt wäre, also muß ein weiteres Element von A nach B getan werden. Das wieder für alle Kombinationen machen.

Jetzt darf ein Element von B nach C getan werden, weil danach |B|=1 >= |C|=1.

Bringt mich zu so was grafisch dargestellt. (Wenn ich dich nicht falsch verstanden habe:
1|-|-
2|-|-
3|-|-
4|-|-

1|4|-
2|-|-
3|-|-

1|3|-
2|-|-
4|-|-

1|2|-
3|-|-
4|-|-

2|1|-
3|-|-
4|-|-

2|1|-
3|4|-

2|1|4
3|-|-

Aber wenn Sie platt liegen komm ich nicht weiter.

Diese Einschränkung der Duplikate bedeutet jedenfalls, dass man das Resultat (mit Dopplungen) noch "normalisieren" soll.

Es wäre natürlich schön wenn man solche Doppelungen gleich vermeiden könnte. Die Ausführung des Programms welches das Problem nach dem ersten Ansatz löst (mit Doppelungen) dauert hier schon 5 Minuten bei 20 Elemente.

Viele Grüße,

Lutz

[Gunnar Bittersmann]

Hello out there!

Allerdings habe ich viele Kombinationen doppelt. Beispielsweise sind bei AAAA, BBBB und CCCC so ja alle Elemente in einem Topf, die beiden anderen sind leer, die Kombination ist also die gleiche

Du hattest in deinem OP angedeutet, dass dies nicht das Gleiche ist:

1 4 -
2 - -
3 - -

[schnipp]

• 1 4
• 2 -
• 3 -

Wie denn nun, kommt es darauf an, welches Element in welchem Topf ist? Hat also jeder Topf eine ihm eigene Identität/Bedeutung?

Oder willst du die Werte einfach nur in k Gruppen aufteilen, wobei die Anordnung der Gruppen egal ist?

See ya up the road,
Gunnar

[Lutz]

Hallo,

Du hattest in deinem OP angedeutet, dass dies nicht das Gleiche ist:

1 4 -
2 - -
3 - -

...

Oh ja, da ist mir ein Fehler unterlaufen. Das sollte nicht so sein.

Wie denn nun, kommt es darauf an, welches Element in welchem Topf ist? Hat also jeder Topf eine ihm eigene Identität/Bedeutung?

Nein, es kommt einzig und allein auf die Unterschiedlichen Kombinationen an. In welchem Topf diese liegt ist unrelevant. Die Kombination zieht natürlich alle drei Töpfe mit ein. Damit könnte das Zitat aus meinem OP mit "In einem Topf sind 1,2,3, in einem anderen ist die 4 und in dem der übrig bleibt nix" beschrieben werden. Die zweite von dir gequotete Kombination aus dem OP ist also absolut redundant.

Gruß und Dank für Deine Mühe,

btw: Ich bin noch kein Stückchen weiter...

Lutz