Permutationen

cirion

ich hab die vage ahnung, dass diese frage eher was für ein paper wäre... gewöhnlich ist es schwierig genug, für einen gegebenen graphen zu sagen, ob er überhaupt einen hamiltonkreis enthält (darauf läuft's ja hinaus) - wie viele verschiedene ist selbst für viele recht einfache graphen noch nicht geklärt. nur eins ist sicher: es sind weniger als (n-1)! / 2

ru,
cirion

Wir können ja im Forum gemeinsam dran forschen.

cirion

interessant ist die frage allemal... wird nur nen ziemlicher datenbankfüller, wenn wir so empirisch weitermachen

ru,
cirion

OK: 1. Kann mal ein Mod die langen Zahlen durch [...] ersetzen?
2. Wie viel Möglichkeiten gibt es jetzt für n = 3?

und 3. Kann mal einer ein Bild des Graphen für n = 3,4 zeichen?

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.

http://imgur.com/dt3ar.png

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

http://www.research.att.com/~njas/sequences/?q=1%2C2%2C12%2C288&sort=0&fmt=0&language=english&go=Search

besseres bild:

123--------132----------231
  | --       |         --|
  |   \---   |      --/  |
  |       \--|  ---/     |
  |          +-/         |
  |       --/|  \---     |
  |   ---/   |      \--  |
  | -/       |         \-|
 321--------312----------213

hier 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