Kombinatorikaufgabe

[FenixAoW]

Bin heute in der Arbeit auf ein Problem gestoßen, dass gelöst werden muss. Habe selber nicht viel Plan auf diesem Gebiet daher dachte ich, bevor ich sonderlich viel umhergoogle, frage ich gleich mal beim Zenith des Wissens nach.

Aufgabe ist diese, dass ich sämtliche Möglichkeiten für die Zuhaltungstiefen eines Sicherheitszylinders ausgeben muss.

Sprich: Ich habe 12 Zuhaltungsnuten und 5 verschiedene Tiefen. D.h. also bei jeder Nut ist Tiefe 1-5 möglich. Die möglichen Kombinationen sind dann in etwa 3 Mio.. Diese muss ich jetzt (am besten in ner Excelliste) ausgeben.

Format z.B.: 154-502-345-112

Danke für hilfreiche Antworten

 

[Stupid]

Das sind 5^12 Möglichkeiten. Oder was willst du wissen?

 

[narc]

Und 5^12 sind übrigens 244mio, wie kommst du also auf 3mio. Du meinst wohl was anderes, also was brauchst du genau? Und dein Beispiel verstehe ich gar nicht, was soll das darstellen?

 

[FenixAoW]

Ok vergesset mal die 3 Mio. Ich versuchs nochmal zu erklären:

Es geht darum, dass ich alle möglichen Kombinationen (am besten in ner EXCEL Datei) benötige. Und zwar alle ohne das diese sich wiederholen.

Ich habe 12 Positionen. Jede Position muss mit einer Tiefe 1-5 gefüllt werden. Das sieht dann von den Positionen so aus:

X-X-X
X-X-X
X-X-X
X-X-X

eine mögliche Kombination sieht dann so aus:

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

Ich brauche aber alle Kombinationen. Am besten in folgender Form:

221-411-521-323

 

[Stupid]

Du hast 12 Positionen, machst aber ein Beispiel mit 15. Wtf?
Und du willst, dass dir jemand ein >100MB großes Excel-File mit allen Kombinationen erstellt?

 

[FenixAoW]

Jo kommt davon wenn man nebenbei zockt.

Nein? Das mache ich schon selber. Nen Lösungsansatz wäre nicht schlecht.

 

[Hakuba]

Grob überschlagen wären das 3.6GB in einer unformatierten CSV-Datei. Keine Ahnung was du damit vorhast, aber besonders gut arbeiten kannst du damit nicht. Bei mir laggt Excel schon mit ein paar Zehntausend Datensätzen und einem Diagramm und allzu schlecht ist mein PC jetzt auch nicht gerade, deshalb bezweifel ich, dass das irgendwie laufen wird.

Ansonsten wäre das ein 20-Zeilen Skript, die Sprache ist egal, nur überlass ich das jemandem der eine bessere Idee hat als 12 verschachtelte for-Schleifen, auf Anhieb fällt mir da nix ein.

Es wäre relativ praktisch zu wissen was genau du damit vorhast, damit man vielleicht eine bessere Alternative vorschlagen könnte.

 

[narc]

Also eine excel-Tabelle mit 244mio Einträgen wird doch eher nutzlos sein (wenns denn überhaupt funktioniert). Was genau willst du damit machen?
Willst du dann nachschauen, welche Kombinationen alle auftreten können? Dann wäre das ja sinnlos, weil ja vornherein klar ist, wie diese Kombinationen aussehen.
Willst du dann zu jeder Kombination irgendwas dazuschreiben? Das wird zu nichts führen, weil du eben 244mio Einträge abarbeiten musst.
Lösungsansatz wäre wie eben Hakuba vorgeschlagen hat, was zu programmieren. Nur wirst du, so denke ich, mit der erstellten Datei nicht viel anfangen können.

 

[FenixAoW]

Jungs das ist ein Sicherheitszylinder. Ein Sicherheitszylinder sieht so aus:

Die orangenen Dinger heißen Zuhaltungen. Diese haben verschiedene Tiefen die in den, nur für diesen Sicherheitszylinder, angefertigten Schlüssel eingreifen.

Wir arbeiten gerade an einem Modularzylinder mit eben 12 Zuhaltungen. Damit jeder Schlüssel nur einen Zylinder schließt brauche ich Kombinationen um Mehrfachschließungen auszuschließen. Ich muss keine 244 Mio. ausspielen lassen. 2 Mio. wären mehr als ausreichend für das was geplant ist.

In der Praxis sieht das dann so aus dass die Zuhaltungen nach dieser Codeliste in den Zylinderkörper (samt Stiften und Federn) gefüllt werden. Dafür brauche ich diese Kombinationen.

 

[narc]

Ich verstehe nur Bahnhof, aber mich interessiert, wie du auf diese 2mio kommst. Vielleicht sehe ich dann, was du machen willst.

Aber ne excel-Tabelle selbst mit nur 2mio sollte schwer werden...

 

[FenixAoW]

Wenn ihr es bis jetzt nicht verstanden habt dann konzentriert euch bitte nur auf die Fakten:

12 Positionen füllen mit den Werten 1-5 -> alle Kombinationen ohne Wiederholung

 

[FORYOUITERRA]

wie nun alle kombinationen ohne wiederholung?
111-222-333-444 darf also z.B. nicht vorkommen?

 

[narc]

12 Positionen füllen mit den Werten 1-5 -> alle Kombinationen ohne Wiederholung

Was sind für dich Wiederholungen?
Sind 111-111-111-112 und 111-111-112-111 für dich eine Wiederholung oder nicht? Falls letzteres sind es ohne Wiederholungen eben über 244mio Möglichkeiten.

edit: Oder meinst du, dass in einer Kombination sich die 3er nicht wiederholen dürfen? Also 111-111-123-134 ist verboten, weil zweimal "111" vorkommt?

 

[FenixAoW]

Ich meinte mit "ohne Wiederholung", dass sich die gleiche Kombination nicht wiederholen darf.

 

[Stupid]

Lässt sich wie gesagt in jeder Programmiersprache in wenigen Zeilen schreiben. Wenn dus direkt in Excel machen willst, musst du wohl in nem spezifischeren Forum nachfragen.

 

[narc]

Ich meinte mit "ohne Wiederholung", dass sich die gleiche Kombination nicht wiederholen darf.

Das sind dann aber 5^12 > 244mio Möglichkeiten.

 

[FenixAoW]

Ich muss keine 244 Mio. ausspielen lassen. 2 Mio. wären mehr als ausreichend für das was geplant ist.

Liest du auch das was ich poste? Von den 244 Mio. reichen mir 2 Mio..

 

[narc]

Warum nehmt ihr dann 12-stellige Kombinationen? Wenn ihr eh nur 2mio verschiedene wollt, reichen auch 9 aus, denn 5^9 ist fast 2mio. Alternativ könnte ihr natürlich alle 12-stelligen nehmen, die mit 111 beginnen.

 

[North]

Ich glaube ich verstehe, was ihr da vor habt. Aber wieso willst du dafür ne Excel Tabelle? Schreib doch "einfach" ein kleines Programm, welches dir entsprechenden Code XXX-XXX-XXX-XXX generiert; da kannst du auch einbauen, dass derselbe Code nicht 2 mal vorkommt. Den ausgegeben Code müsste man doch rel. einfach in eine Excel Tabelle exportieren können?
...
(Ich gehe mal davon aus dass ihr sowas vor habt wie "Kunde X bekommt einen individuellen Schlüssel mit Code XXX-XXX-XXX-XXX den nur er hat; dann kannst du eben diesen Code direkt erstellen lassen und ausgeben?).
...
Wenn es Excel oder eine Tabelle mit 2Mio+ aufgeführten Codes sein MUSS, dann bist du hier glaube ich falsch; denke da müsste man andere Wege finden

 

[FenixAoW]

Warum nehmt ihr dann 12-stellige Kombinationen? Wenn ihr eh nur 2mio verschiedene wollt, reichen auch 9 aus, denn 5^9 ist fast 2mio. Alternativ könnte ihr natürlich alle 12-stelligen nehmen, die mit 111 beginnen.

Sorry man aber mir fehlen nun echt so langsam die Worte...
So wenig Verständniß für Praxis kann ein Mensch doch gar nicht haben.
Sicherheitsfaktor bei 12 Zuhalten > Sicherheitsfaktor bei 9 Zuhaltungen.
Dazu gibts noch zahlreiche andere Gründe warum 12 und nicht 9.

@ North:
Das Programm was du da erwähnst hört sich schon sehr gut an. Ich habe allerdings keinerlei Plan von Programmieren.

Mir wäre eine Liste auch lieber. Andere große Sicherheitsfirmen wie zB Keso oder Evva arbeiten auch mit diesen Listen. Liegt an verschiedenem aber ich glaube es ist am einfachsten zu katalogisieren für den Fall, dass der Kunde einen Schlüssel nachmachen will.

Hat Excel denn da Probleme ne Liste mit 2 Mio. einträgen zu erstellen?

Aber Danke für die Antwort. Kommt am ehesten etwas hilfreichen soweit nahe.

 

[narc]

Sorry man aber mir fehlen nun echt so langsam die Worte...
So wenig Verständniß für Praxis kann ein Mensch doch gar nicht haben.
Sicherheitsfaktor bei 12 Zuhalten > Sicherheitsfaktor bei 9 Zuhaltungen.
Dazu gibts noch zahlreiche andere Gründe warum 12 und nicht 9.

Ob man nun in der Praxis 2mio oder 244mio Schlüssel ausprobieren musst, spielt doch auch keine Rolle. Aber wie gesagt, überlege dir in diesem Fall eine Kombination XYZ und lass dir alle Kombinationen, die mit XYZ beginnen (oder an beliebiger anderer fester Stelle stehen), von einem Programm ausspucken. Und wenn du dann irgendwann mal neue Kombinationen brauchen solltest, kannst du, einfach die Anfangskombination ändern und das Spielchen wiederholen.

 

[FenixAoW]

Ob ich 2 Mio. Schlüssel ausprobiere oder 244 Mio.? Der Satz alleine ergibt für mich keinen Sinn, sorry.

Das mit der fixen ersten Kombination wäre an sich keine schlechte Idee kann ich aber vom sicherheitstechnischen Aspekt aus einfach nicht unterstützen weil sonst die Kombination der ersten Reihe bei jedem Zylinder gleich wäre. Selbst wenn es nur für die erste Serie wäre...

 

[FORYOUITERRA]

Sorry man aber mir fehlen nun echt so langsam die Worte...
So wenig Verständniß für Praxis kann ein Mensch doch gar nicht haben.
Sicherheitsfaktor bei 12 Zuhalten > Sicherheitsfaktor bei 9 Zuhaltungen.
Dazu gibts noch zahlreiche andere Gründe warum 12 und nicht 9.

@ North:
Das Programm was du da erwähnst hört sich schon sehr gut an. Ich habe allerdings keinerlei Plan von Programmieren.

Mir wäre eine Liste auch lieber. Andere große Sicherheitsfirmen wie zB Keso oder Evva arbeiten auch mit diesen Listen. Liegt an verschiedenem aber ich glaube es ist am einfachsten zu katalogisieren für den Fall, dass der Kunde einen Schlüssel nachmachen will.

Hat Excel denn da Probleme ne Liste mit 2 Mio. einträgen zu erstellen?

Aber Danke für die Antwort. Kommt am ehesten etwas hilfreichen soweit nahe.

warum macht ihr nicht 13 mögliche kombinationen?

 

[mfb]

Die Liste ist ganz einfach zu erstellen - alle Zahlen von 0 bis (5^12-1) im 5er-System (wobei das Ziffern von 0 bis 4 gibt, also immer 1 addieren oder 0 als 5 betrachten). Das kann jede vernünftige Programmiersprache, und Excel mit ein paar Formeln auch.
Wenn man nur jede ~100. davon will, einfach in Schritten von 93 hochzählen. Die Schrittweite ist so gewählt, dass die Stifte sich mehr unterscheiden als bei Schritten von 100.

Interessanter wäre es, wenn sich keine zwei Kombinationen nur um eine benachbarte Stellung unterscheiden sollten (also 123-123-123-123 => keine 223-123-123-123 mehr). Das würde immer noch grob 10 Millionen mögliche Kombinationen geben.

 

[FenixAoW]

Wenn es so einfach ist dann mach es doch vor.

 

[Benrath]

guck halt mal hier, auch wenn du so unfreundlich fragst

http://starcraft2.ingame.de/forum/showthread.php?t=225755

Ein Programm wie R oder Matlab oder k.a. wirst du dann noch wählen müssen. Wenn die Permutationen können wirst du dann über die Hilfe auch Kombinationen ohne Wiederholungen eines n langen vektors finden wo die Elemente von 1 bis 5 gehen.

Sonst schreib halt ne schleife über 12 vars von 1 bis 5 und mach nen vektor mit den Variationen draus und wählste dir irgendwelche aus.

Ich mein in dem THema von mir erklärten thema hab ich auch bisschen hinterm Berg gehalten was ich will, aber was erwartest du jetzt, dass dir jemand die Schleife schreibt? Ich seh gerade auch nicht den Sinn was du mit 2 mio von 244 mio kombinationen willst.

 

[mfb]

Wenn es so einfach ist dann mach es doch vor.

Kein Ding. Die rechte Spalte sind die Kombinationen, ich habe eine andere Schrittweite gewählt um mehr Abwechslung in den ersten Zahlen zu haben.
Rechnet für 2 Millionen etwas, geht aber.

Wieso das ein Screenshot und nicht die Excel-Datei ist? Weil mich dein Poststil anwidert.

 

[Benrath]

Du hast das vergessen

 

[freesta]

Ich habe es in C# gelöst (die letzte zeile is wohl nur doppelt, weil das Programm noch läuft):

 

[piko]

Wie hier um die Wette getrollt wird.

 

[zoiX]

Fenix hätte aber auch wirklich freundlicher Fragen können. Schön, dass dieser Thread sich selbst moderiert...

 

[freesta]

Ich sehe hier eigentlich nichtmal Fragen. Gewünscht ist ja anscheinend ein Ansatz, ich versuch es mal:

Wenn wir uns an "Programmieren kann ich nicht" halten, sind wir wohl bei 0. Ich gehe also davon aus, dass du nicht weißt, was eine for-schleife ist oder wie man in irgendeiner Sprache etwas auf den Schirm ausgibt.
Mach am besten erstmal ein beliebiges Einsteigertutorial zum Thema Programmieren. Programmiersprache ist fast schon egal, es geht nur darum, die einfachsten Grundlagen wie Zuweisungen, Strings und Schleifen zu kennen. Nimm C#, oder Python, oder Java, oder C++, oder Perl, es ist wie gesagt fast wurscht.

Wenn du das hast, zum eigentlichen Problem:
Eigentlich dreht sich hier alles nur um Repräsentation von Zahlen bzw. Stringformatierung. Mathematisch ist das Problem nämlich einfach nur ein durchzählen aller natürlichen Zahlen von 0 (in der Schlüsselrepräsentation wäre das 111-111-111-111) bis 5^12-1=244140624 (entspricht 555-555-555-555). Die Frage ist also, wie rechne ich (Beispiel) die Zahl 244140624 nach 555-555-555-555 um? Eine mögliche Antwort ist die stellenweise Berechnung nach folgendem Schema:

Schritt 1.a: 244140624 % 5 + 1 = 5 (% ist der Modulooperator, den du in dem Programmiertutorial kennengelernt haben solltest)
1.b: 244140624 / 5 = 48828124 (/ für Division ohne Rest)
2.a: 48828124 % 5 + 1 = 55
2.b: 48828124 / 5= 9765624
3.a: 9765624 % 5 + 1 = 555
3.b: 9765624 / 5 = 1953124
4.a:1953124 % 5 + 1 = 5555
.
.
.
12.a: 4 % 5 +1 =555555555555

Was die Rechenzeit angeht ist das so umgesetzt nicht die schnellste Lösung, aber ich will jetzt nicht noch unnötig mit weiteren Alternativen verwirren.

 

[FenixAoW]

Kein Ding. Die rechte Spalte sind die Kombinationen, ich habe eine andere Schrittweite gewählt um mehr Abwechslung in den ersten Zahlen zu haben.
Rechnet für 2 Millionen etwas, geht aber.

Wieso das ein Screenshot und nicht die Excel-Datei ist? Weil mich dein Poststil anwidert.

Hier krachen einfach Technik und Mathematik aufeinander. Ich verstehe von Mathematik nichts, ihr offensichtlich von Technik. "Ist ja ganz einfach mach einfach dies, das" höre ich nun schon des Öfteren in diesem Thread, ohne wirklich eine Erklärung zu erkennen mit der ein Laie wie ich etwas anfangen kann.

Habe mir nun deine Variante ein wenig angesehen. Soweit ich das verstanden habe stellst du die Zahlen von 0 bis 5^12 im Fünfersystem dar (rechnest sie also vom Dezimal ins 5er um).

Was passiert mit den Zahlen die mehr als 12 stellig im 5er System sind? Wenn man die einfach weglässt, verfällt da soweit ich das verstanden habe die Garantie, dass sich die Kombinationen nicht wiederholen. Somit wäre das dann nicht wirklich brauchbar für die Praxis.


@Argumentekasper: Danke, schaue ich mir an.

 

[narc]

Was passiert mit den Zahlen die mehr als 12 stellig im 5er System sind?

Die werden nicht betrachtet, diese würden dann ja 13 Einstellmöglichkeiten erfordern, sie sind also für dich unbrauchbar.

Wenn man die einfach weglässt, verfällt da soweit ich das verstanden habe die Garantie, dass sich die Kombinationen nicht wiederholen. Somit wäre das dann nicht wirklich brauchbar für die Praxis.

Bin mir nicht sicher, ob ich dich verstehe. Aber wenn du 5^12 verschiedene Zahlen, die sich im Dezimalsystem unterscheiden, ins 5er-System umrechnest, sind ihre Darstellungen immer noch unterschiedlich. Und insbesondere erhält man so auch alle 12-stelligen Zahlen im 5er-System.
Und allgemein: Wieso sollte durch Weglassen von Zahlen die Eindeutigkeit wegfallen?

 

[FenixAoW]

Meine Überlegung war, dass eine zB.: ~16 stellige Nummer für sich selbst einzigartig ist aber die ersten 12 stellen davon vielleicht nicht. Nur die 12stelligen Zahlen zu nehmen wären dann wohl zu wenig.

 

[mfb]

Hier krachen einfach Technik und Mathematik aufeinander. Ich verstehe von Mathematik nichts, ihr offensichtlich von Technik.

Also fuer diesen Thread reicht mein Technikverstaendnis problemlos.

"Ist ja ganz einfach mach einfach dies, das" höre ich nun schon des Öfteren in diesem Thread, ohne wirklich eine Erklärung zu erkennen mit der ein Laie wie ich etwas anfangen kann.

Mag an der Art liegen, wie du fragst.

Habe mir nun deine Variante ein wenig angesehen. Soweit ich das verstanden habe stellst du die Zahlen von 0 bis 5^12 im Fünfersystem dar (rechnest sie also vom Dezimal ins 5er um).

Genau.

Was passiert mit den Zahlen die mehr als 12 stellig im 5er System sind?

Die habe ich nicht. Mit der Schrittweite von 93 wuerden die sowieso nicht auftreten, bei mir nehme ich jeweils den Rest, der bei einer Division durch 5^12 auftritt. Wiederholungen gaebe es erst nach 5^12 Schritten (also wenn alle Kombinationen einmal aufgetreten sind) - das liegt daran, dass meine Schrittweite und 5^12 keinen gemeinsamen Teiler haben. Das ist einfach zu schaffen, denn 5^12 hat nur Vielfache von 5 als Teiler, und meine Schrittweite ist nicht durch 5 teilbar.

Wenn man die einfach weglässt, verfällt da soweit ich das verstanden habe die Garantie, dass sich die Kombinationen nicht wiederholen. Somit wäre das dann nicht wirklich brauchbar für die Praxis.

Diese Garantie kann ich geben.

 

[FenixAoW]

Hm, jo dann kann ich diese Variante nicht verwenden, trotzdem danke.

Was meine Art angeht: So bin ich eben. Ein hartgesottener Hardliner und kein ausgelutschter Teebeutel. Dankbar bin ich trotzdem.

 

[mfb]

Hm, jo dann kann ich diese Variante nicht verwenden, trotzdem danke.

Doch klar kannst du. Jede erzeugte Kombination ist einmalig - solange du nicht mehr als ~244 Millionen (eben 5^12) davon erzeugst.

Wie gesagt, das kann ich garantieren.

 

[FenixAoW]

beim überfliegen ein "nicht" mit reingelesen