Zählen Sie die Anzahl der Möglichkeiten, LEGO Steine zu kombinieren

Ich habe eine beliebige Anordnung von Legosteinen. Ich habe auch einige Figuren aus 3 Legosteinen. Ich möchte herausfinden, wie viele Kombinationen von Figuren ich aus der aktuellen Legostein-Reihe erstellen kann.Zählen Sie die Anzahl der Möglichkeiten, LEGO Steine zu kombinieren

Jeder hat einige Referenzen für mich, damit ich dieses Problem lösen kann?

Welche Algorithmen kann ich verwenden? Irgendeine Theorie, die ich benutzen kann?

Vielen Dank im Voraus für jede Hilfe, die Sie zur Verfügung stellen können.

/Hans

Edit: Diese Frage wurde re-asked on the math stack exchange.

Quelle

2012-04-10 hansdam

Sind alle Legosteine identisch, wenn nicht, wie viele verschiedene Arten von Steinen gibt es? "Figuren", die aus einzigartigen Ziegelsteinen bestehen? Ich sollte mehr Gedanken und Mühe in Ihre Frage stecken. – ElKamina

Ich habe sechs Ziegelfarben, so könnte die Anordnung der Ziegel sein: blau, rot, rot, gelb, grün, gelb, orange, blau, gelb, weiß. Die Figuren bestehen aus 3 Steinen. Die verschiedenen Figuren sind: 1: gelb, weiß, blau; 2: blau, gelb, grün; 3: gelb, orange, blau; 4: gelb, rot, gelb; 5: gelb, blau; – hansdam

Nun, jede Kombination von drei ist eine gültige Kombination? – ElKamina

Würden Sie glauben, dass Probleme wie diese, oder zumindest ihre allgemeine Fälle sind tatsächlich noch offene Forschungsfragen? Sie machen hier echte mathematische Forschung. ;)

Søren Eilers, Mikkel Abrahamsen und Bergfinnur Durhuus haben an einem LEGO-Kombinations-Zählproblem gearbeitet, nämlich die number of unique ways you can arrange six identical 4x2 lego bricks. zu zählen. Sie können ihre Arbeit (inklusive Java-Code) zur Inspiration betrachten.

Von einem Skim über den Text, es scheint, dass sie das Problem zwei getrennte Wege gelöst:

eine rekursiven Block-Positionierung und Zählen Algorithmus.
Mit roher Gewalt - jede mögliche Positionierung der sechs Steine im Raum versucht

Hinweis: Die Anzahl der möglichen Kombinationen, auch für eine kleine Anzahl von Ziegeln (auch für die diejenigen, die Steine nicht berühren.) , ist groß. Das macht LEGO so spaßig.

Quelle

2012-04-10 19:12:30

Übrigens kann es sich lohnen, diese Frage auf math.stackexchange.com zu stellen. Das ist wirklich eine mathematische Frage, und Mathematiker werden bessere Antworten darauf geben können. –

Vielen Dank Li-aung Yip! Ich werde die Frage im anderen Forum stellen. – hansdam

Abhängig von der zu erwartenden Rechenkomplexität können Sie dynamische Programmierung verwenden.

Let x1, x2, ... xk eine Lösung sein, so dass x1 Kopien der Kombination 1, x2 Kopien der Kombination 2 ....

F ([]) = F ([x1 = 0] + F ([x1 = 1] ...

F ([x1]) = F ([x1, x2 = 0]) + F ([x1, x2 = 1]) ....

Die Komplexität dieser Lösung ist O (n^k), wobei n die Anzahl der Steine und k die Anzahl der Steine ist

Quelle

2012-04-10 22:24:25 ElKamina

Das ist eine ziemlich generische Antwort - wie ist dynamische Programmierung für die jeweilige Aufgabe relevant? –

@ Li-aungYip Warum? Dies ist eine sehr genaue Antwort. Welche Rolle verstehst du nicht? Wählen Sie im Grunde, wie viele Replikate der Form 1 Sie erstellen möchten und verwenden Sie den Rest der Bausteine, um andere Formen zu erstellen. – ElKamina

Zählen Sie die Anzahl der Möglichkeiten, LEGO Steine ​​zu kombinieren

Antwort

Verwandte Themen

Zählen Sie die Anzahl der Möglichkeiten, LEGO Steine zu kombinieren