Trova le permutazioni in cui nessun elemento rimane in posizione

Question

Sto lavorando con permutazioni in cui ogni elemento è diverso dalla sua posizione originale. Vorrei un algoritmo che fornisse {una lunghezza, una riga e una cifra di input, che mi fornisse il numero di output. Ecco un esempio:

Se la lunghezza di input è quattro, tutte le permutazioni di 0123 sono:

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

Le permutazioni in cui nessuna cifra è nello stesso posto (ogni cifra si è spostata):

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

La numerazione inizia da 0, quindi se l'input per la funzione è {4,0,0}, l'output dovrebbe essere la 0a cifra (all'estrema sinistra) della 0a (prima) permutazione. La prima cifra di 1032 è 1.

Se l'input è {4,1,1}, allora l'output è la seconda cifra di 1230, che è 2.

Il numero di riga potrebbe essere maggiore del numero di permutazioni. In tal caso, prendi il resto del modulo il numero di permutazioni (nel caso precedente, riga modulo 9).

Nel linguaggio c sarebbe fantastico.

(Non sono compiti a casa, è per lavoro. Cuckoo hashing se devi saperlo. Vorrei selezionare casualmente gli swap che farò in ogni fase per vedere se è meglio di BFS quando il numero di tabelle è maggiore di due.)

Answer 1

Approccio a forza bruta in Python (puoi usarlo per testare l'implementazione in C):

#!/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

Perché non solo costruire un albero e iterarlo?

Ad esempio, se hai le cifre 0123 , allora sai che la cifra più a sinistra può essere solo dal set {1,2,3} . Questo fungerebbe da primo livello nel tuo albero.

Quindi, se segui il percorso che inizia con 1, hai solo tre opzioni, {0, 2, 3} . Se segui il percorso che inizia con 2 nel primo livello, hai solo due opzioni {0,3} (poiché non puoi usare 1 nella seconda cifra da sinistra e il 2 era già usato (potresti far apparire i 2 dal tuo elenco di scelte), ecc.

La cosa a cui prestare attenzione in questo approccio è se arrivi alla fine di un ramo con 3 come unica opzione, nel qual caso, la elimineresti semplicemente

Per n > 10 generare tutte le permutazioni e quindi il filtraggio può diventare problematico. Penso che costruire l'albero dovrebbe tagliare questo in modo significativo.

Se necessario, puoi costruire l'albero al volo. Il tuo ordine può essere definito da come attraversi l'albero.