Kobinationsalgorithmus

hallo,
ich möchte beliebig viele strings in einer beliebigen reihenfolge beliebig oft miteinander kombinieren. kann mir irgendjemand ein tipp geben wie man so etwas macht? habe schon irgendwas mit rekursiv gelesen… die zeit spielt keine rolle!

danke
rokdd

Hallo rokdd,

würde dir gerne helfen, mir ist leider anhand deiner Mail nicht klar geworden, was du eigentlich machen willst. Kannst du mal was mehr an Information 'rübergeben? :wink:

Chris

Morgen,
also habe viele verschiedene strings in einem array. und ich will jede kombinationsmöglichkeit nach diesen kriterien: Der String…
… darf mehrmals vorkommen
… kann an jeder Stelle (oder gar nicht) stehen
… die anzahl der Strings, die benutzt werden sollen, ist nicht definiert!

Hoffe das hilft dir jetzt mehr!

rokdd

Hallo rokdd,
die Frage verstehe ich nicht ganz. Möchtest Du einen Quellcode in einer beliebigen Programmiersprache?
Ein Beispiel für ein Ergebnis einer solchen Operation hätte ich für Dich. Eine beliebige Zahl in einem beliebigen Zahlensystem. Die Anzahl der Strings definiert dabei Dein Zahlensystem.
Daran siehst Du, daß die Zahl der Kombinationen zwangsläufig unendlich ist. Um ein Ende der Operation zu erzwingen mußt Du die Anzahl der Glieder begrenzen.
cu Rainer

Hallo,
programmieren will ich das ganze Delphi. Mir geht es wirklich nur um den Algo. Wir können ruhig die anzahl der strings auf 50 setzen(ich weiß dass es trotzdem sehr viele lösungen gibt)!

rokdd

Hallo,
bei n Strings gibt es nm Möglichkeiten, die m mal hinterander zu hängen. Gelinde gesagt ist das Erzeugen aller Lsg. selbst bei kleinen Werten schon kaum mehr praktikabel. Wenn das eine Übungsaufgabe mit „Eigensinn“ ist ok, wenn Du aber z.B. Lsg. für das PCP (PKP) oder eingeschränkte Fassungen davon suchst solltest Du die zusätzlichen Einschränkungen bereits bei der Generierung der Wörter berücksichtigen. Ansonsten sieht es „düster“ aus.

Gruss
Enno

Hallo rokdd,

Deine Aufgabe ist nicht Lösbar !!

also habe viele verschiedene strings in einem array. und ich
will jede kombinationsmöglichkeit nach diesen kriterien: Der
String…

  1. darf mehrmals vorkommen
  2. kann an jeder Stelle (oder gar nicht) stehen
  3. die anzahl der Strings, die benutzt werden sollen, ist nicht
    definiert!

Aus 1. ergiebt sich schon eine unendliche Anzahl von Lösungen, 3. spielt da schon gar keine Rolle mehr, daurch benötigt die Lösung mit dem Computer auch unendlich viel Zeit.

Nehmen wir mal nur einen String „a“.
Lösungen:
1.
2. a
3. aa
4. aaa

Das kannst du weiterführen bis hier der Server explodiert, allerdings ist das noch nicht die letzte gültige Lösung.

Du musst also schon deine Aufgabe so einschränken, dass sich eine endliche Menge an Lösungen ergibt, dann kann man es möglicherweise mit einem Computer berechnen.
Deine Aufgabenstellung lässt sich ganz einfach nicht Lösen !!!

MfG Peter(TOO)

Hallo rokdd,
delphi habe ich nicht und Pascal kann ich auch nicht.
Eine Lösung für VB ist aber kein Problem und sicher leicht für Delpi umzuschreiben. Wo die Schwierigkeit sein soll, zwei-drei Schleifen ineinander zu schreiben kann ich nicht sehen. … Ich ‚bastel‘ Dir mal ne fertige Lösung und mail Dir die.
cu Rainer

Hallo,
ich weiß ja dass jeder eine andere programmierprache nutzt, genau deswegen wollte ich nur den strategischen teil von euch wissen. das problem ist dass ich mir sicher bin, ob ich alle Varianten durchprobiert habe!
Trotzddem schon mal danke!

rokdd

Hallo rokdd,
zu prüfen, ob Dein Algorithmus richtig ist, ist einfach.
Fülle Deine Datenbank mit den Ziffern 0 bis 9 und lasse das Programm dann laufen. Der Rechner sollte dann ‚zählen‘ wenn alles richtig ist. :wink:
cu Rainer

…derzeit läuft da gar nichts :frowning:((

rokdd

Hi rokdd,
wenn n die Anzahl der Worte ist und m eine maximale Anzahl von Worten per fertigem String:
nimm ein integer-Array mit m Eintraegen und initialisiere es zu [0,0,0,0,0…]
Dann zaehle in einer Schleife das Array modulo n+1 hoch, d.h fasse es auf als Zahldarstellung
z_m z_(m-1) … z_1
wobei die z_i N+1 verschiedenen Werte annehmen koennen (im "normalen Dezimalsystem waer m z.B. 10, im binaeren waere es 2). In jeder Schleife addiere 1 zu der Zahl modulo n+1.
Dann erzeuge Ausgabestrings als:
word[z_m] | word[z_(m-1) … | word[z_1]
wobei word[0] = „“ (der leere String ist) und „|“ die Konkatenation (Aneinanderhaengen).
Das sollte es tun. Den Algorithmus kann man noch optimieren. Wie jemand anderes in der Diskussion schon bemerkt hast, wirst Du damit schon fuer moderate n und m keine Freude mehr haben …
Viel Erfolg,
-thowe-

PS: statt eines index-arrays kannst Du auch einfach eine integer-Variable nehmen, die Du in der Schleife hochzaehlst und aus der dann mittels Division durch n+1 und Modulo-Operation nach n+1 die Indexe deiner Worte bestimmen…

PPS: Es gibt ca (n+1)^m Moeglichkeiten; nur „ca“, weil doppelte Ausgabestrings vorkommen

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

hmm, danke!
ein was verstehe ich aber nicht:
>>Dann zaehle in einer Schleife das Array modulo n+1 hoch, d.h fasse es >>auf als Zahldarstellung
>>z_m z_(m-1) … z_1

Rokdd

Hallo

also habe viele verschiedene strings in einem array. und ich will
jede kombinationsmöglichkeit nach diesen kriterien: Der String…
… darf mehrmals vorkommen
… kann an jeder Stelle (oder gar nicht) stehen
… die anzahl der Strings, die benutzt werden sollen, ist nicht
definiert!

Durch die Bedingung „darf mehrmals vorkommen“, also zwischen 0 und Unendlich mal, ist die Aufgabe nicht lösbar bzw. es kommt der Therm „Unendlich Fakultät“ in der Berechnung vor.

MfG Peter(TOO)

Lieber Peter,
selbstverstaendlich gibt es einen Algorithmus, der die Aufgabe loest.
Er terminiert nur nicht in endlicher Zeit. Jedenfalls nicht auf einer herkoemmlichen Turingmaschine.
Im uebrigen habe ich in dem von mir vorgeschlagenen Algorithmus das Problem auf Strings aus hoechstens m Teilstrings beschraenkt, wie Du vermutlich bemerkt hat. Dann terminiert der Algorithmus stets in endlicher, aber fuer praktische Zwecke wahrscheinlich ungemuetlicher Zeit.
Gruesse,

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

Hi Rokdd
Unser alltaegliches Dezimalsystem basiert auf zehn Ziffern (0…9)
Jede Zahl setzt sich daraus zusammen;

452 = z_3 z_2 z_1

wobei z_3=4, z_2=5 und z_1=2 ist.

„Zaehlen“ meint in jedem Schritt 1 dazu addieren; dabei kommt es zu Ueberlaufen, wenn man 9 + 1 addiert und man muss dann eine 1 nach links zur naechst hoeheren Dezimalstelle uebertragen. OK?

Es gibt Ausserirdische, die haben nur 4 Finger an jeder Hand. Die zaehlen im Oktalsystem und Zahlen enthalten deshalb nur die Ziffern 0 bis 7; Uebertraege erfolgen bei 7+1, weil 7+1 im Oktalsystem gleich 10 ist. Z.B.
257 + 1 = 260 (ein Uebertrag)
oder 277 + 1 = 300 (2 mal Uebertrag nach links wie bei 299+1 = 300
im Dezimalsysytem)

Du hast n Woerter und den leeren String. Dein Problem loest Du durch Aufzaehlen aller moeglichen Wortkombinationen. Die sind darstellbar durch alle Zahlen im n+1 System. Wenn Du das Aufzaehlen nicht im Dezimalsystem machst, sondern im n+1 - System, dann geben Dir die Ziffern in den Zahlen genau die Nummern der Woerter in Deiner Liste an, die Du verketten musst. Deshalb bastelst Du Dir einen Zaehler im Programm, der modulo n+1 zaehlt und haengst dann, die von der Zahl im n+1 System angegebenen Strings einfach hintereinander.

Wie schon in einer frueheren Notiz ist es vermutlich leichter, statt eines Arrays fuer die Positionen der Ziffern in dem Zahler, einfach einen Integer zu verwenden, den hoch zu zaehlen, und mittels Division und Modulo-operation die (n+1) - Darstellung auszurechnen. Etwa so:

long counter=0; // das ist der Zaehler
long cdiv, cmod; // zur Hilfe
string ouput;
while( counter [Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

okay danke, er rechnet jetzt erstmal. wenn ich mir aber deinen quelltext mal anschaue ist dieses label teil doch eine endlosschleife! ist das wirklich so gewollt?

rokdd

Hallo,
die Frage ist, was er mit „beliebig viele Strings“ meint. Beliebig aber fix - kein Problem. Ansonsten wäre eine aufzählbare Menge von String ausreichend, um ein Aufzählungsverfahren sämtlicher Kombinationen zu erlangen.

Gruss
Enno

Hallo,
hilft es schon wenn jeder string nur maximal 3 mal vorkommen darf oder? Das würde vielleicht auch reichen…

Rokdd

Hallo,
mit beliebigen Strings meinte ich den Inhalt. Die Länge des Arrays könnte man vielleicht ja auch begrenzen…

rokdd