Permutationen
-
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.