 |
Das deutsche QBasic- und FreeBASIC-Forum
Für euch erreichbar unter qb-forum.de, fb-forum.de und freebasic-forum.de!
|
| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
momohk
Anmeldungsdatum: 21.01.2014
Beiträge: 9
Wohnort: Deutschland
|
 Verfasst am: 06.02.2014, 12:15 Titel: Kombination von allem mit allem |
 |
|
Hola.
ich habe gerade wieder angefangen zu programmieren und stoße leider schon recht schnell an meine Grenzen 
Folgende Aufgabe:
Ich frage ein paar Dinge ab und möchte nun eine Datei erstellen in dem jegliche Kombination der Eingaben gespeichert wird.
Also z.B.
Abfrage 1: Schaufel
Abfrage 2: Hammer
Abfrage 3: Stiefel
usw.
In der Datei sollte nun die Kombination alles mit allem stehen, also
Schaufel, Hammer, Stiefel, Schaufelhammer, Schaufelstiefel, Hammerschaufel, Hammerstiefel, Stiefelschaufel, Stiefelhammer.
Also die Abfragen usw. sind nicht das Problem, aber wie bekomme ich es hin, dass diese Kombinationen entstehen ??
Danke im Voraus
Oli |
|
| Nach oben |
|
 |
TimesChange
Anmeldungsdatum: 20.11.2013
Beiträge: 85
|
| Verfasst am: 06.02.2014, 12:32 Titel: |
|
|
Du könntest sowas in der Art machen:
| Code: | Neu = n+1
For i=1 to n
For k=1 to n
if i<>k then
Dat(Neu)=Dat(i) & Dat(k)
Neu = Neu + 1
end if
next k
next i |
Das Feld Dat() enthält deine abgefragten Begriffe, n ist die Anzahl der Begriffe. Anschlie0end werden deine neuen Kombinationen in Dat() gespeichert (oder du schreibst in dieser Zeile direkt in die Datei).
Dat() muss natürlich ausreichend groß dimensioniert werden.
Grüße
Rainer |
|
| Nach oben |
|
|
momohk
Anmeldungsdatum: 21.01.2014
Beiträge: 9
Wohnort: Deutschland
|
| Verfasst am: 06.02.2014, 16:51 Titel: |
|
|
Hallo Rainer.
Danke für deine Antwort.
Funktioniert soweit, aber was müsste ich tun, damit es auch die Kombination SchaufelHammerStiefel usw. gibt.
Bis jetzt bekommt ja jedes Wort nur einen Zusatz, aber sollen ja wenn möglich alle Kombinationsarten erstellt werden.
Gruessle
Oli |
|
| Nach oben |
|
|
TimesChange
Anmeldungsdatum: 20.11.2013
Beiträge: 85
|
| Verfasst am: 06.02.2014, 18:16 Titel: |
|
|
Davon hast du oben aber nichts geschrieben 
Du könntest eine weitere Schleife (for L = 1 to n...) einfügen, für dein Beispiel (3 Begriffe) würde das reichen.
Das ist aber nicht sinnvoll, wenn du viele Begriffe hast, und alle denkbaren Doppel- und Mehrfachkombinationen erzeugen willst.
Dann bräuchte man wohl eher eine rekursiv aufgerufene Prozedur, oder so 
Das können aber andere besser, ich kann nur Pimperles-Programme...
Grüße
Rainer |
|
| Nach oben |
|
|
ThePuppetMaster
Anmeldungsdatum: 18.02.2007
Beiträge: 1839
Wohnort: [JN58JR]
|
| Verfasst am: 06.02.2014, 18:50 Titel: |
|
|
| Code: | dim td() as string 'elementespeicher
dim tc as integer 'anzahl elemente
dim t as string 'eingabevariable
dim tx as UInteger 'zählervariable
'!ACHTUNG! bereits 8 eingaben erzeugen 16 millionen kombinationen!!!
Print "Bitte geben sie daten ein! (fertig mit leerer zeile)"
do
Input t
if t = "" then exit do
tc += 1
redim preserve td(tc) as string
td(tc) = t
Print Str(tc) & " Elemente im speicher! Das ergibt " & str(tc ^ tc) & " kombinationen!"
tx += 1
loop
If tc = 0 Then print "keine eingabe! bye!": End -1 'wenn nix drin, auch keien kombi!
dim tmax as UInteger = tc ^ tc 'maximale anzahl an kombinationen
dim trest as UInteger 'rest-variable für berechnung
dim tval as UInteger 'aktueller wert-variable für berechnung
Dim ttot as double 'timeout für sleep udn cpu schonung
Do
trest = tx
t = ""
Do 'das folgende prinzip bassiert auf dem binärem rechnen, nut wird hier stat 0 und 1 alle varianten bis tc verwendet.
if ttot < timer() Then 'dient dem schutz vor extremer cpu auslastung bei zu vieler kombinationen
Sleep 1, 1
ttot = timer() + 1
End If
tval = trest mod tc
trest = fix(trest / tc)
t += td(tc - tval) '"bit" bzw "tc wert" der position aus dem array holen und an string anhängen
If trest = 0 then exit Do 'wenn nix mehr vorhanden, schleife verlassen.
Loop
Print t 'kombination ausgeben
tx += 1 'nächste kombi
If tx >= tmax then exit Do 'wenn max erreicht, exit (sonst krachts)
Loop
Print "gesammt:" & tx
end 0
|
EDIT:
Als kurze erklärung zum hintergrund des verfahrens.
Man nehme das Binärprinzip zur hand:
0, 1, 10, 11, 100, 101, 110, 111, 1000, ... usw.
Beim binärem gibt es nur 0 und 1 ... wir ändern das jetzt einfach und führen werte von 0 bis <anzahl elemente> ein.
angenommen, wir haben 3 elemente:
0, 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102, 110, 111, 112, 120, ... usw.
jeder wert wird als indexnummer des array verwendet .. damit das ganze klapt wird eine variable erzeugt, die einfach +1 rechnet .. das läuft quasi die gesammten kombinationen ab welche maximal <anzahl> hoch <anzahl> sind ...
um den ersten wert in unserem zähler zu erhalten rechnen wir den "rest" heraus, mit mod
wert = zählerkopie mod anzahl
anschliessend wird der zähler (welcher in eine temp variable kopiert wurde) um eine entsprechende stelle reduziert:
zählerkopie = fix(zählerkopie / anzahl)
das wird solange widerholt, bis der wert 0 erreicht hat (zählerkopie = 0)
jeder wert entspricht damit einem wert zwischen 0 und anzahl -1 ... da das array mit 1 beginnt entsprechend den wert + 1 rechnen.
das ganze dann noch aus dem array in einem temp-string zusammenkombinieren, und ausgeben.
MfG
TPM
_________________
[ WebFBC ][ OPS ][ ToOFlo ][ Wiemann.TV ] |
|
| Nach oben |
|
|
momohk
Anmeldungsdatum: 21.01.2014
Beiträge: 9
Wohnort: Deutschland
|
| Verfasst am: 09.02.2014, 16:51 Titel: |
|
|
Hallo TPM.
Sorry für die späte Rückmeldung und danke für deine Antwort.
1. Es funktioniert
2. Ich verstehe es nicht wirklich
3. Du hast recht, die das Ganze wir ziemlich groß, darum mein Frage.
Gäbe es die Möglichkeit die Länge zu begrenzen, also, obwohl ich 20 Werte habe und alle mit allen kombinieren möchte, sollen max. 3 drei Werte gemeinsam ausgegeben werden.
Gruessle
Oli |
|
| Nach oben |
|
|
dreael
Administrator
Anmeldungsdatum: 10.09.2004
Beiträge: 2531
Wohnort: Hofen SH (Schweiz)
|
| Verfasst am: 09.02.2014, 17:43 Titel: |
|
|
Vielleicht solltest Du den Permutationengenerator (so etwas willst Du ja übrigens!) etwas präziser definieren, denn ich bin mir nicht sicher, ob Du
| Code: | Schaufelschaufelschaufel
Hammerhammerhammer
Stiefelstiefelstiefel |
auch haben willst.
Wenn jedes Wort immer nur maximal 1x vorkommen darf und "Schaufelhammer" und "Hammerschaufel" gleichwertig sind, reduzieren sich die Möglichkeiten bereits beträchtlich: Dann hast Du es mit einer Art Set-Datentyp zu tun, d.h. jedes Wort erscheint oder erscheint nicht.
Zur Illustration
| Code: | xx1 = Schaufel
x1x = Hammer
1xx = Stiefel
1 001 = Schaufel
2 010 = Hammer
3 011 = Schaufelhammer
4 100 = Stiefel
5 101 = Schaufelstiefel
6 110 = Hammerstiefel
7 111 = Schaufelhammerstiefel |
d.h. bei n Begriffe also immer 2^n-1 Kombinationen.
Am besten also mit dem 3-Wort-Beispiel einmal vollständig von Hand alle gewünschten Kombinationen bilden, danach kann das Bildungsmuster herausgelesen werden. Gleichzeitig stellt diese von Hand erstellte Tabelle den Testfall für den Permutationengenerator dar.
Übrigens der Mastermindknacker aus meiner Sammlung verwendet auch so einen Permutationengenerator.
_________________
Teste die PC-Sicherheit mit www.sec-check.net |
|
| Nach oben |
|
|
ThePuppetMaster
Anmeldungsdatum: 18.02.2007
Beiträge: 1839
Wohnort: [JN58JR]
|
|
| Nach oben |
|
|
dreael
Administrator
Anmeldungsdatum: 10.09.2004
Beiträge: 2531
Wohnort: Hofen SH (Schweiz)
|
| Verfasst am: 10.02.2014, 14:18 Titel: |
|
|
| momohk hat Folgendes geschrieben: | | Gäbe es die Möglichkeit die Länge zu begrenzen, also, obwohl ich 20 Werte habe und alle mit allen kombinieren möchte, sollen max. 3 drei Werte gemeinsam ausgegeben werden. |
Inzwischen selber den FbEdit angeworfen und ein kleines Beispiel zusammengestellt:
http://beilagen.dreael.ch/QB/PermuationsGenerator.bas
Genaue Definition der Permutationen im Beispiel:
- jeder Begriff nur maximal 1x vorkommend
- Reihenfolge irrelevant, d.h. HammerSchaufel und SchaufelHammer sind gleichwertig => nur eines davon wird benötigt
- dafür auch weniger als die maximalen k Begriffe (im Minimum 1 Begriff)
Rechnerisch entstehen so bei max. k Begriffe aus n:
totalKombinationen = Summe(i=1..k, n!/(i!*(n-i)!))
z.B. wie im Beispiel n=9, k=3:
| Code: | 9*8*7 9*8 9
----- + --- + - = 84 + 36 + 9 = 129
3*2*1 2*1 1 |
In Deinem Fall mit n=20, k=3:
| Code: | 20*19*18 20*19 20
-------- + ----- + -- = 1140 + 190 + 20 = 1350
3* 2* 1 2* 1 1 |
Von der Programmierung her ist für so etwas Rekursion nötig.
_________________
Teste die PC-Sicherheit mit www.sec-check.net |
|
| Nach oben |
|
|
momohk
Anmeldungsdatum: 21.01.2014
Beiträge: 9
Wohnort: Deutschland
|
| Verfasst am: 14.02.2014, 09:11 Titel: |
|
|
Hallo Dreael, Hallo PuppetMaster,
Vielen Dank für eure Mühen. Ich muss jetzt erst mal versuchen das alles zu verstehen, denn ich möchte ja nicht einfach kopieren.
@Dreael, Hammerstiefel und Stiefelhammer wären in meiner Anwendung nicht gleichwertig, müssten also beide vor kommen, HammerHammer Hammer, jedoch nicht.
Gruessle
Oli |
|
| Nach oben |
|
|
|
|
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
|
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
