Aus Buchstaben-Array einzigartige Strings generieren

[Quests Sohn]

Hallo,

ich möchte aus einem Array von vordefinierten Buchstaben sämtliche möglichen Kombinationen
eines sechs- oder achtstelligen Strings generieren. Ich benötige keine Zufalls-Strings.

array('A', 'B', 'C', ... , 'N', 'P', ... , 'X', 'Y', 'Z');

Das Array enthält bei mir insgesamt 20 Buchstaben, weil ich z. B. das O weglasse.
Jetzt möchte ich sechsstellige Buchstabenketten erstellen, wie "AAAAAA", "AAAAAB", ...
Dabei sollen die Buchstabenketten immer von Klein zu Groß erstellt werden, also von "AAAAAA" (als kleinste mögliche Kombination) über "AAAAAB" bis zu "ZZZZZZ" (als größte mögliche Kombination).
Es darf keine Kombination doppelt vorkommen, also "AAAAAA" soll es z. B. nur exakt einmal geben.

Das Ganze soll anschließend in eine MySQL-Datenbank geschrieben werden, wobei ich das wohl
noch selbst hinbekomme.

Wer kann mir einen Tipp geben, wie das lösbar ist?

 

[Technipion]

Suchst du eine Lösung in PHP, oder bloß nach einem Algorithmus?

Das Array enthält bei mir insgesamt 20 Buchstaben, weil ich z. B. das O weglasse.

Das Ganze soll anschließend in eine MySQL-Datenbank geschrieben werden, wobei ich das wohl
noch selbst hinbekomme.

Öhm, dann willst du also eine Datenbank mit 384 MB dafür anlegen, obwohl man das relativ einfach on-the-fly berechnen könnte?

• Sind die Zeichenketten immer 6-stellig?
• Stehen die weggelassenen Buchstaben von vornherein fest oder ist die Menge an erlaubten Buchstaben variabel?

Gruß Technipion

 

[Quests Sohn]

Hallo Technipion,

es soll eine Datenbank mit einmaligen Losnummern entstehen, die dann Personen zugeordnet werden können. Das Buchstaben-Array steht fest: A, B, C, D, E, G, H, K, M, N, P, Q, R, S, T, U, V, X, Y, Z
Die Zeichenkette soll immer exakt sechsstellig sein, also niemals mehr oder weniger Zeichen enthalten.

Eigentlich will ich natürlich keine so gewaltige Datenbank anlegen und auch die Reihenfolge wäre zufällig besser, aber es dürfte kompliziert sein und lange Abfragen erzeugen, wenn ich zu Beginn erstmal nur 100.000 Losnummern erzeuge und dann später über eine Abfrage für jeweils weitere 100Tsd Lose klären muss, ob der jeweilige String schon vorhanden ist, bevor sie hinzugefügt werden.

Oder irre ich mich da?

 

[Zvoni]

Hä????
Wenn es um eine Lotterie geht, benutz doch einfach einen der unzähligen Lotto-Algorithmen.
Ich hatte sogar hier irgendwo einen für VB6 geschrieben, welcher dem Durstenfeld-Algoritmus entspricht (was ich damals nicht wusste).
Dein Verfahren nennt sich übrigens: Mit Zurücklegen und beachten der Reihenfolge (AABAAA<>AAAABA)

Zur grundlegenden Problemstellung (Deine originale Frage, wie man alle möglichen Kombinationen erzeugt):
6-fach verschachtelte For-Schleife
Viel Spass damit....

Nachtrag: An deiner Stelle würde ich nicht alle möglichen Kombinationen speichern (siehe die 384MB die Technipion erwähnt hat), sondern genau anderst herum: Die bereits gezogenen Losnummern abspeichern.
Dann ist es einfach per SQL abzufragen, ob das Los bereits gezogen worden ist. Falls ja, ziehe erneut (per Algoritmus siehe oben), falls nein, wir haben einen Sieger, und speichern es in der DB ab.

Dürfte mMn performance-mässig deutlich schneller sein.
Andererseits muss der "Grundpool" aber auch nur einmal aufgebaut werden.....

Nachtrag 2: Habs gefunden
[Visual Basic] x Zahlen aus n Zahlen ziehen: Das Lotto-Problem | Tutorial
Es wäre also ein Aufruf Lottery 6,20,False, True
und die Zufallszahl ist der Index deines Buchstaben Arrays
Falls du Hilfe brauchst, das nach PHP umzubauen gib Bescheid, wobei ich kein PHP-ler bin

Nachtrag 3: Es gibt 64.000.000 (64 Millionen) mögliche Kombinationen.
Mit 1 Byte / Buchstabe landet man tatsächlich bei den 384 MB, lass die Tabelle jetzt aber Multi-Byte-encoding haben....

 

[Quests Sohn]

Hallo Zvoni,

da habe ich mich vielleicht ungenau ausgedrückt: Ich möchte keine Lotterie veranstalten, sondern Objekte - oder genauer gesagt Tiere - identifizieren. Ein "Los" ist also keine Gewinnmöglichkeit, sondern z. B. eine Fußklammer. Es soll eine Datenbank entstehen, in die Rancher Tiere eintragen. Wenn Tier AAAAAA dann entlaufen oder noch nicht untersucht ist, wird es anhand des einmaligen Codes erkannt.

Wenn also Rancher X seine 200 Tiere registriert, dann soll er schnell 200 Codes erhalten, die einmalig existieren und eindeutig seiner Ranch zugeordnet werden können. Ich dachte, das geht ggf. am besten, wenn alle möglichen Codes vorhanden sind und sofort beliebig große Listen an Codes ausgegeben werden können.

 

[Zvoni]

ACH SOOOOO.

Sag das doch gleich…. LOL
muss bis morgen warten. Bin jetzt schon auf dem Sprung
Muss ich nachdenken wie ich das lösen würde

 

[Sempervivum]

Im wesentlichen kann man das genau so wie einen Zähler aufziehen, nur nicht mit Ziffern sondern mit Buchstaben: Eine Stelle von Anfang bis Ende durcharbeiten und dann kommt die nächste Stelle dran. Man könnte daran denken, 6 for-Schleifen zu verschachteln aber etwas kompakter geht es, wenn man es rekursiv aufzieht:

    $letters=['a','b','c','d'];
    $places=6;
    function addLetters($letters, $result, $idx)
    {
        // Decrement index on places:
        $idx--;
        // Loop through all letters:
        for ($j = 0; $j < count($letters); $j++) {
            // Add current letter to string:
            $newResult= $result . $letters[$j];
            // Last place not yet reached?
            if ($idx>0) {
                // Places left, add letters for next place:
                addLetters($letters, $newResult, $idx);
            } else {
                // Resulting string ready, enter into DB:
                echo $newResult.'<br>';
            }
        }
    }
    addLetters($letters, '', $places);

 

[Zvoni]

Ok, an Rekursion hab ich jetzt nicht gedacht, da ich schon voraus gedacht habe wegen dem Hinweis „100.000“ Lose.
da ist es einfacher, 6 schleifen zu schachteln und einen Zähler mitlaufen zu lassen.
Zähler erreicht, speichere den Zustand der Schleifenvariablen usw.

 

[Quests Sohn]

Oh Gott, klingt beides extrem kompliziert.

In der Version von Sempervivum bin ich offenbar nicht in der Lage den Duplikatschutz zu erkennen. Es wirkt für mich wie eine sinnvolle Reihung, aber ohne dass dabei verhindert wird, dass ein vorhandener String wiederholt ausgegeben wird. Kann das sein?

 

[Sempervivum]

Einen Duplikatschutz würdest Du nur brauchen, wenn Du Zufallszahlen verwenden würdest, weil es dabei passieren kann, dass sich mehrmals die selbe Zahl ergibt. Mein Verfahren mit der Rekursion macht jedoch genau das, was Du in deinem Eingangsposting beschrieben hast:

Dabei sollen die Buchstabenketten immer von Klein zu Groß erstellt werden, also von "AAAAAA" (als kleinste mögliche Kombination) über "AAAAAB" bis zu "ZZZZZZ" (als größte mögliche Kombination).

Der letzte bzw. rechte Buchstabe wird vom ersten bis zum letzten durchlaufen. Ist man damit am Ende, wird beim nächsten Buchstaben, dem zweiten von rechts, der nächste genommen und der letzte wiederum vom ersten bis zum letzten durchlaufen. Und immer so weiter. Wenn man das so macht, können keine Dupletten entstehen. Wenn Du dir die Ausgabe von meinem Skript ansiehst, erkennst Du, dass die entstehenden Strings genau so aussehen.
Wie schon geschrieben, funktioniert das genau so wie bei einem Zähler mit Dezimalziffern. Wenn man eine Stelle immer um eins erhöht und beim Überlauf die nächste, können sich auch keine doppelten Zahlen ergeben.