Finden Sie die Permutationen, wo kein Element an Ort und Stelle bleibt

Question

Ich arbeite mit Permutationen, bei denen jedes Element von seinem ursprünglichen Speicherort unterscheidet. Ich möchte einen Algorithmus, der {Eingabe Länge, Zeile und Zahl} gibt mir die Ausgabe Nummer. Hier ein Beispiel:

Wenn die Eingabelänge vier ist, dann werden alle Permutationen vonsind:

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):

Die Nummerierung beginnt bei 0. Wenn also die Eingabe der Funktion {4,0,0} ist, sollte die Ausgabe die 0. (ganz links) Ziffer der 0. (ersten) Permutation sein. Erste Ziffer von 1032 ist 1.

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

Die Zeilennummer größer die nubmer sein könnte von Permutationen. In diesem Fall nehmen Sie den Rest modulo die Anzahl der Permutationen (im obigen Fall Zeile modulo 9).

In der c-Sprache wäre großartig.

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

Answer 1

Ansatz Brute-force in Python (Sie Ihre C-Implementierung zu testen, verwenden):

#!/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 durch sie nicht nur einen Baum bauen und iterieren?

Zum Beispiel, wenn Sie die Ziffern haben 0123, dann wissen Sie, dass die linke Ziffer kann nur aus der set {1,2,3} sein. Dies würde als Ihre erste Ebene in Ihrem Baum fungieren.

Dann, wenn Sie den Pfad beginnend mit 1 gehen, haben Sie nur drei Optionen, {0, 2, 3}. Wenn du den Pfad beginnend mit 2 in der ersten Ebene herunterfährst, hast du nur zwei Optionen {0,3} (da du 1 nicht in der zweiten Ziffer von links verwenden kannst und die 2 bereits benutzt wurde (du könntest die 2 aus deiner Liste entfernen) Auswahlmöglichkeiten)) usw.

Die Sache, auf die man bei diesem Ansatz achten sollte, ist, wenn man bis zum Ende einer Verzweigung kommt, bei der 3 die einzige Option ist. In diesem Fall würde man sie einfach löschen.

Für n > 10 Generieren aller Permutationen und dann Filterung kann problematisch werden. Ich denke, wenn man den Baum ausbaute, würde das erheblich abnehmen.

Sie können den Baum bei Bedarf spontan erstellen. Ihre Bestellung kann definiert werden, indem Sie den Baum durchlaufen.