Permutationen
-
sdfdsf schrieb:
So aus Neugierde: Wofür brauchst du das?
Größtenteils Neugierde. Es hat mit serieller Musik angefangen und sich dann selbstständig gemacht.
-
Was schonmal klar ist: Wenn man eine Folge hat, dann sind auch alle Folgen, in denen die Ziffern beliebig, aber fest permutiert werden, zulässig. Also gibt es mindestens n! zulässige Folgen, und die Anzahl der zulässigen Folgen ist durch n! teilbar.
-
Jetzt bleibt die Frage: Gibt es eine zulässige Folge, die man auf diese Weise nicht erhält. Dazu bräuchten wir die Anzahl der zulässigen Folgen für n=3.
-
Ich vermute: Es gibt a_1 = 1, a_n = n!*a_{n-1} Möglichkeiten
-
besseres bild:
123--------132----------231 | -- | --| | \--- | --/ | | \--| ---/ | | +-/ | | --/| \--- | | ---/ | \-- | | -/ | \-| 321--------312----------213hier sieht man auch schön
die symmetrie: man kann eine ecke mit der im halbquader diagonalliegenden mitte tauschen, da dise elemente die gleichen nachbarn haben.12 für n = 3 hab' ich auch. wie hast du 288 ausgerechnet?
-
HotzPlotzKlotz schrieb:
12 für n = 3 hab' ich auch. wie hast du 288 ausgerechnet?
12 die mit 123 starten...
-
HotzPlotzKlotz schrieb:
HotzPlotzKlotz schrieb:
12 für n = 3 hab' ich auch. wie hast du 288 ausgerechnet?
12 die mit 123 starten...
Ich will alle zählen, also beliebiger Anfang. Meine Vermutung ist falsch, es sind mehr. Mehr in Kürze.
-
dsfsdf schrieb:
HotzPlotzKlotz schrieb:
HotzPlotzKlotz schrieb:
12 für n = 3 hab' ich auch. wie hast du 288 ausgerechnet?
12 die mit 123 starten...
Ich will alle zählen, also beliebiger Anfang. Meine Vermutung ist falsch, es sind mehr. Mehr in Kürze.
das wäre dann 12 * 3! = 72
-
Ich glaub, ich habs jetzt:
a_1 = 1
a_n = a_{n-1} * (Anzahl der Möglichkeiten, n! aus {1,...,n} auszuwählen, wobei je a_{n-1} gleich sind)
-
ne, sorry, ist falsch.
-
sdfsfd schrieb:
Ich glaub, ich habs jetzt:
a_1 = 1
a_n = a_{n-1} * (Anzahl der Möglichkeiten, n! aus {1,...,n} auszuwählen, wobei je a_{n-1} gleich sind)den ausdruck in den klammern versteh' ich nicht. was bedeutet "n! auswählen"?
-
Ich glaube es ist so: (n!)!/(n-1)![h]n[/h]
-
dfgdg schrieb:
Ich glaube es ist so: (n!)!/(n-1)![h]n[/h]
bei mir kommt für n = 3 72 raus, wie per hand. siehe skript
from itertools import permutations from math import factorial n = 3 l = [i for i in permutations(range(1, n + 1))] def numdiff(a, b): assert len(a) == len(b) return sum( (int(a[i] != b[i]) for i in xrange(len(a))) ) count = 0 for en, pp in enumerate(permutations(l)): passed = 1 for i, p in enumerate(pp): if numdiff(pp[i], pp[ (i + 1) % factorial(n)]) != 2: passed = 0 break count += passed print count
-
kannst du mal n=4 ausrechnen?
-
sdfsdf schrieb:
kannst du mal n=4 ausrechnen?
nein, zu lang für brute-force
-
-
was dann zu einem artikel führt, der wenigstens eine untere abschätzung der anzahl liefert:
El-Hashash, M., Burgiel, H., & Hassan, A. (2008) On the Hamiltonicity of the Permutahedron. Congressus Numerantium, (189), 145-160
ru,
cirion
-
cirion schrieb:
was dann zu einem artikel führt, der wenigstens eine untere abschätzung der anzahl liefert:
El-Hashash, M., Burgiel, H., & Hassan, A. (2008) On the Hamiltonicity of the Permutahedron. Congressus Numerantium, (189), 145-160
ru,
ciriongibt's das online? google scholar ist unergiebig...
-
http://www.m-hikari.com/ijcms-password2009/1-4-2009/elhashashIJCMS1-4-2009.pdf Da wird bewiesen, was wir schon wissen: Es gibt einen Hamiltonkreis. Der Beweis ist wie der von mir oben.
-
dsfdfsd schrieb:
http://www.m-hikari.com/ijcms-password2009/1-4-2009/elhashashIJCMS1-4-2009.pdf Da wird bewiesen, was wir schon wissen: Es gibt einen Hamiltonkreis. Der Beweis ist wie der von mir oben.
aber die Referenz [3], wo auch eine Anzahl abgeschätzt wird, habe ich nicht online gefunden.
