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