Finden Sie die Permutationen in denen kein Element an seinem Platz bleibt

Question

Ich arbeite mit Permutationen, wobei jedes Element unterscheidet sich von seinem ursprünglichen Standort ist. Ich würde einen Algorithmus wie die gegebene {eine Eingabelänge, Zeile und Ziffer}, gibt mir die Ausgangsnummer. Hier ein Beispiel:

Wenn die Eingabelänge vier ist, dann werden alle Permutationen von 0123 sind:

0123,0132,0213,0231,0312,0321,
1023,1032,1203,1230,1302,1320,
2013,2031,2103,2130,2301,2310,
3012,3021,3102,3120,3201,3210

Die Permutationen, in denen keine Ziffer an der gleichen Stelle ist (jede Ziffer bewegt hat):

1032,1230,1302,
2031,2301,2310,
3012,3201,3210

Die Nummerierung beginnt bei 0 so, wenn die Eingabe in die Funktion {4,0,0}, sollte die Ausgabe der 0-te (ganz links) Ziffer der 0-te (erste) Permutation sein. Die erste Ziffer von 1032 ist 1.

Wenn die Eingabe {4,1,1} dann ist der Ausgang der die zweite Ziffer von 1230, die 2 ist.

Die Zeilennummer kann die nubmer von Permutationen größer sein. In diesem Fall übernimmt die restliche, die Anzahl der Permutationen modulo (in dem obigen Fall, Reihe modulo 9).

In der C-Sprache wäre toll.

(Es ist nicht Hausaufgaben, dann ist es für die Arbeit. Cuckoo Hashing, wenn Sie wissen müssen. Ich mag zufällig die Swaps zu wählen, die ich in jeder Phase machen würde, um zu sehen, ob es besser ist, als BFS, wenn die Anzahl der Tabellen ist größer als zwei.)

Answer 1

Brute-Force-Ansatz in Python (Sie es verwenden, können Sie Ihre C-Implementierung zu testen):

#!/usr/bin/env python
from itertools import ifilter, islice, permutations

def f(length, row, digit):
    """
    >>> f(4, 0, 0)
    1
    >>> f(4, 1, 1)
    2
    """
    # 1. enumerate all permutations of range (range(3) -> [0,1,2], ..)
    # 2. filter out permutations that have digits inplace
    # 3. get n-th permutation (n -> row)
    # 4. get n-th digit of the permutation (n -> digit)
    return nth(ifilter(not_inplace, permutations(range(length))), row)[digit]

def not_inplace(indexes):
    """Return True if all indexes are not on their places.

    """
    return all(i != d for i, d in enumerate(indexes))

def nth(iterable, n, default=None):
    """Return the nth item or a default value.

    http://docs.python.org/library/itertools.html#recipes
    """
    return next(islice(iterable, n, None), default)

if __name__=="__main__":
    import doctest; doctest.testmod()

Answer 2

Warum nicht einfach einen Baum bauen und durchläuft das?

Zum Beispiel, wenn Sie die Ziffern 0123 haben, dann wissen Sie, dass die am weitesten links stehende Ziffer nur vom set {1,2,3} sein kann. Dies würde als erste Stufe in Ihrem Baum handeln.

Wenn Sie dann den Pfad beginnend mit 1 gehen, Sie haben nur drei Optionen, {0, 2, 3}. Wenn Sie den Pfad mit 2 in der ersten Ebene, beginnend nach unten gehen, haben Sie nur zwei Möglichkeiten {0,3} (da Sie nicht 1 in der zweiten Ziffer von der linken Seite verwenden und wurde die 2 bereits verwendet (Sie können die 2 aus der Liste Pop könnten Auswahl)) usw.

Die Sache in diesem Ansatz zu achten ist, wenn Sie an das Ende eines Zweiges erhalten mit 3 Ihrer einzigen Option sein, wobei in diesem Fall, Sie würden es einfach löschen.

Für n > 10 alle Permutationen zu erzeugen und dann kann Filterung problematisch werden. Ich denke, der Baum würde dies trimmen deutlich Aufbau aus.

Sie können den Baum im Fluge bauen, wenn es sein muss. Ihr Auftrag kann durch definiert werden, wie Sie durchqueren den Baum.