Speedcube.de Forum
Alle Permutation "durchwürfeln" - Druckversion

+- Speedcube.de Forum (https://forum.speedcube.de)
+-- Forum: Speedcubing (https://forum.speedcube.de/forumdisplay.php?fid=7)
+--- Forum: Cubing Allgemein (https://forum.speedcube.de/forumdisplay.php?fid=9)
+--- Thema: Alle Permutation "durchwürfeln" (/showthread.php?tid=3623)

Seiten: 1 2


Alle Permutation "durchwürfeln" - mcc - 20.04.2013

Hallo,

dies ist eher eine theoretische Frage, aber deren Beantwortung würde mich dennoch interessieren:

Wenn man nur lange genug eine bestimmte Zugfolge an einem zum Start gelösten Cube ausführt, landet man nach einer bestimmten Anzahl von Zügen wieder am Anfang.

Oder mit anderen Worten: Einen sehr kleinen Teil aller möglichen Farbanordnungen hat man dann "durchgewürfelt".

Aber:
Gibt es auch eine (wahrscheinlich ziemlich lange) Zugfolge, die sämtliche Farb-/Cubie-Anordnungen durchspielt, wenn man sie nur oft genug anwendet?

Vielen Dank für jede Information und Hilfe im Voraus!

Gruß
mcc


RE: Alle Permutation "durchwürfeln" - Elf - 20.04.2013

Meinst du all hundert trillionen verschiedenen "Stellungen" eines Würfels??

Wenn ja ist das garantiert möglich, dauert aber saaaaaaaauuuuuuuuuulange!!!


RE: Alle Permutation "durchwürfeln" - Taurelin - 21.04.2013

In der englischen wikipedia-Version gibt es folgende Antwort:

Zitat:The largest order of an element in G is 1260. For example, (RU^2D^{-1}BD^{-1})^{1260} = E.

Das heißt, es gibt keine Zugfolge, die sämtliche 43 Trillionen Stellungen durchgeht, sondern die längste führt nach 1260 Durchläufen wieder zum gelösten Würfel.


RE: Alle Permutation "durchwürfeln" - mcc - 21.04.2013

Moin moin Taurelin,

Was passiert aber, wenn...

Es sei die Zugfolge R,L',R' jene die alle 1260 Permutationen dieses G
abdeckt (das ist ein Beispiel...die Zugfolge ist viiiiel zu kurz, aber ich will
hier nicht alles mit Zügen vollkleckern... Wink

Nun hänge ich aber an die Zugfolge etwas an:
R,L',R',D

Dadurch wird der Ausgangszustand von R,L',R' um eine Drehung
permutiert und wieder laufen 1260 (andere) Permutationen ab.

R,L',R' bildet immer 1260 Permutationen ab...das sagt die Wikipedia.
WELCHE das sind, hängt vom Ausgangszustand ab.

Den kann ich aber durch vor-/nachgelagerte Züge selbst wieder
permutieren.

Wie also sieht also die Zugfolge aus, die alle Permutationen durchspielt?

Gruß
mcc


RE: Alle Permutation "durchwürfeln" - Taurelin - 21.04.2013

Der Begriff "Ordnung eines Elements" besagt , dass man nach einer entsprechenden Anzahl von Durchführungen wieder beim neutralen Element - also beim Ausgangszustand - landet.

Je nachdem von welchem Muster du ausgehst, bekommst du natürlich auch andere Muster mittendrin. Aber eine Zugfolge, bei der du alle möglichen Stellungen durchgehst, ohne dass eine Stellung doppelt auftaucht, gibt es nicht.

Mal ein konkretes Beispiel:

Nehmen wir den "Algorithmus" R' (also nur den einen Zug). Dieses Element hätte in der Gruppe die Ordnung 4, denn wenn du diesen Algorithmus 4x durchführst, bist du wieder in der Ausgangsstellung.

Angenommen, du machst vorher eine andere Drehung, z.B. U. Dann kannst du ebenfalls den Algorithmus R' 4x ausführen. Dann ist der Würfel natürlich nicht gelöst, aber wieder in einem Zustand, den du vorher bereits hattest.


Die Frage nach einer Zugfolge, die alle 43 Trillionen Stellungen durchspielt, lässt sich rein praktisch wohl kaum beantworten. Und vom theoretischen Standpunkt ist sie auch nicht so interessant, weil die fixe Marke der höchsten Ordnung (=1260) existiert, aber im Vergleich zur Gesamtzahl doch sehr klein ist.


RE: Alle Permutation "durchwürfeln" - moritz - 21.04.2013

(21.04.2013, 10:10)mcc schrieb: Es sei die Zugfolge R,L',R' jene die alle 1260 Permutationen dieses G
abdeckt (das ist ein Beispiel...die Zugfolge ist viiiiel zu kurz, aber ich will
hier nicht alles mit Zügen vollkleckern... Wink

Nun hänge ich aber an die Zugfolge etwas an:
R,L',R',D

Dadurch wird der Ausgangszustand von R,L',R' um eine Drehung
permutiert und wieder laufen 1260 (andere) Permutationen ab.

R,L',R' bildet immer 1260 Permutationen ab...das sagt die Wikipedia.
WELCHE das sind, hängt vom Ausgangszustand ab.

bin mir nicht ganz sicher was du damit sagen willst... wenn ich eine z.b. zugfolge der ordnung 63 nehme (R U) und einen zug dranhänge (U') dann hab ich eine zugfolge der ordnung 4?!

aber vllt klären sich alle deine fragen durch das hier:
angenommen es gibt eine zugfolge A die alle permutationen durchläuft, also insebsondere bei bei n-facher anwendung ein R ergibt und nach m-facher anwendung ein U. dann ergibt sich R U = A*n A*m = A*(n+m) = A*(m+n) = A*m A*n = U R was offensichtlich falsch ist. => so ein A kann nicht existieren.

es gibt aber eine zugfolge, die alle zustände durchläuft, wenn man sie ein einziges mal ausführt und nach jeder 90°-drehung die resultierende permutation als durchlaufen zählt. nähere infos: http://bruce.cubing.net/ham333/rubikhamiltonexplanation.html


RE: Alle Permutation "durchwürfeln" - mcc - 21.04.2013

Moin moin moritz,

meiner Meinung nach hinkt Deine Schlussfolgerung
"was offensichtlich falsch ist. => so ein A kann nicht existieren."
dahingehend, dass sie Deine Annahme als richtig vorraussetzt.
Denn dies ist die andere Möglichkeit warum es "offensichtlich falsch"
ist Wink

Gilt denn bei Würfelbewegungen/zügen das Kommutativgesetz?
Also: Ist das Ergebnis von R U dasselbe von wie von U R?

Die Sache mit dem Hamiltonian circuit ist allerdings schon schwer
interessant.
Mehr von diesem Stoff ! Smile)

Gruß
mcc


RE: Alle Permutation "durchwürfeln" - Taurelin - 21.04.2013

(21.04.2013, 14:05)mcc schrieb: Gilt denn bei Würfelbewegungen/zügen das Kommutativgesetz?
Also: Ist das Ergebnis von R U dasselbe von wie von U R?

Nein.

Beweis: Guck dir den Würfel in beiden Fällen einfach mal an.


Edit:
Ich merke gerade, dass meine Argumentation im Hinblick auf die Ordnung komplett am Thema vorbei war. Bitte um Entschuldigung. Facepalm


RE: Alle Permutation "durchwürfeln" - mcc - 21.04.2013

Moin moin Taurelin

"Beweis: Guck dir den Würfel in beiden Fällen einfach mal an."

...äh...meine Frage war eher rhetorischer Art... Wink

Gruß
mcc


RE: Alle Permutation "durchwürfeln" - moritz - 23.04.2013

(21.04.2013, 14:05)mcc schrieb: Moin moin moritz,

meiner Meinung nach hinkt Deine Schlussfolgerung
"was offensichtlich falsch ist. => so ein A kann nicht existieren."
dahingehend, dass sie Deine Annahme als richtig vorraussetzt.
Denn dies ist die andere Möglichkeit warum es "offensichtlich falsch"
ist Wink
öhm ne das is schon richtig so. http://de.wikipedia.org/wiki/Reductio_ad_absurdum


(21.04.2013, 14:05)mcc schrieb: Gilt denn bei Würfelbewegungen/zügen das Kommutativgesetz?
Also: Ist das Ergebnis von R U dasselbe von wie von U R?
kommt drauf an was genau du festhältst... wenn du was haben willst was mit ALLEM kommutiert dann ist das das zentrum der gruppe (bestehend aus id (=nichtstun) und superflip (=alle edges flippen)). wenn du zu einer bestimmten permutation X alle permuationen wissen willst die damit kommutieren dann bilden die sogar eine untergruppe. (und die ist insbesondere nicht leer) mit anderen worten ist das der stabilisator von X bezüglich der gruppenoperation "konjugation": http://de.wikipedia.org/wiki/Gruppenoperation#Stabilisator
(21.04.2013, 14:05)mcc schrieb: Mehr von diesem Stoff ! Smile)
bon appetit Wink