Algorithmus ähnlich einem Brutforce

[_nicer_]

Hallo Zusammen,

ich stehe gerade etwas extrem auf dem Schlauch. Ich habe das Alphabet (26 Buchstaben) und möchte alle Möglichkeiten ausschöpfen die Buchstaben in 8 Felder zu verteilen. Dabei soll die Reihenfolge im Alphabet allerding erhalten bleiben.

Also das ist so gemeint. Ich mach mal ein Bsp nur mit A,B und C und 3 möglichen "Feldern":

_ = Feld ist leer.

Möglichkeit 1:
ABC | _ | _
AB | C | _
A | BC | _
A | B | C

Vielleicht hat ja jemand schonmal sowas gemacht und kann mir den Code zur Verfügung stellen. Oder mir einen Lösungsansatz liefern, wie ich da ran gehn kann.

Danke Gruß Pascal

 

[kabel2]

Das schreit förmlich nach einer Rekursion wie bei den Hanoischen Türmen.
Die rekursive Funktion hat bei mir drei Parameter: Den Zeichenvorrat als Liste, eine Liste mit den einzelnen Zeichenketten, und die Position, ab der Zeichen aus dem Zeichenvorrat eingefügt werden sollen.

Interessanter dürfte allerdings die Funktion abhängig von der Anzahl Zeichen im Vorrat und den zu besetzenden Stellen sein, die direkt die Anzahl liefert.
Hat da jemand eine offene oder geschlossene? Bin ordentlich aus der Übung... Gebe auch zu, dass ich nach ner halben Stunde abgebrochen habe

 

[Thomas Darimont]

Hallo,

gib doch bitte mal noch ein weiteres Beispiel an:
4 Buchstaben auf 3 Felder.

Wenn ich dich richtig verstanden habe, lässt sich dein Problem auch folgendermaßen darstellen:

Aus:

ABC | _ | _
AB | C | _
A | BC | _
A | B | C

wird:

        3 0 0
        2 1 0
        1 2 0
        1 1 1

Die Zahlen geben die jeweiligen Feldkapazitäten an. In jeder Zeile ist die Kapazität k gleich (in diesem Fall also 3).

Wenn du nun im ersten Schritt diese Kapazitätspläne generieren würdest,
könntest du in einem zweiten Schritt mit einem kleinen "Fenster" (sliding window) der Länge k über das Alphabet laufen und die darin enthaltenen Buchstaben je nach Kapazitäten auf die Felder verteilen.

Gruß Tom

 

[kabel2]

Der Lösungsansatz ist gut.
Ich nehme allerdings an, dass vorne auch Leerstellen sein dürfen, so dass _ AB C z.B. auch eine gültige Lösung darstellen.
Es reicht übrigens aus, alle Feldkapazitäten herzuleiten, denn zwischen der Feldkapazität und den Zeichen, die dann darin liegen, besteht eine 1:1 Beziehung. (Mathesprech: Isomorphie).
Dazu einfach von links nach rechts einen Kapazitätsplan durchgehen und die (geordneten) Zeichen dann reinschieben. Das geht auf genau einem Weg.

Für die Funktion ergibt sich dann folgendes:
(mit n Anzahl der Stellen, auf die verteilt werden kann und k Anzahl der Zeichen im Vorrat)
1) Zuerst kann man sich entscheiden, auf wieviele Stellen man die k Zeichen legen kann. Das rangiert von i=1 bis n.
2) Diese i Stellen können nun irgendwie auf den n möglichen Stellen liegen. Das ist dann ein Faktor innerhalb der Funktion.
3) Die k Zeichen können nun auf den i Stellen verteilt werden. Einzige Einschränkung ist, dass die Summe auf den Stellen jeweils k ergibt.

So und das Ganze jetzt bitte schön in Mathesprech einpacken ;-)
Dürfte für die Fein-Kombinatoriker ein Klacks sein, ich hab das damals gehasst wie die Pest.

 

[Vereth]

Du solltest am besten nicht in Feldern und Zeichen denken, sondern in Alphabet und Separatoren (Feldtrennern).

Beispiel:
Du hast ein Alphabet 'ABCDEFGHI'
und mußt 4 Felder füllen, was gleichbedeutend ist mit der Aufgabe, innerhalb des Alphabets 3 Feldtrenner zu platzieren. Da du 9 Buchstaben hast, hast du 8 mögliche Positionen zwischen den Buchstaben, eine vor allen Buchstaben und eine hinter allen Buchstaben, also insgesamt 10; diese kannst du von 0 bis 9 durchnummerieren.
Nun brauchst du nur noch durchzuzählen:

0 0 0
0 0 1
0 0 2
...
0 0 9
0 1 1 (nur wenn auch zwischendrin leere Felder erlaubt sind!)
0 1 2
0 1 3
etc.

du musst nur darauf achten, dass eine Positionsnummer nicht kleiner sein darf als eine vorhergehende.

Viel Erfolg