Encuentra las permutaciones donde ningún elemento permanece en su lugar

Question

Estoy trabajando con permutaciones donde cada elemento es diferente de su ubicación original. Me gustaría un algoritmo que dado {una longitud de entrada, fila y dígito}, me dé el número de salida. Aquí hay un ejemplo:

Si la longitud de entrada es cuatro, entonces todas las permutaciones de 0123 son:

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

Las permutaciones en las que ningún dígito está en el mismo lugar (cada dígito se ha movido):

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

La numeración comienza en 0, por lo que si la entrada a la función es {4,0,0}, la salida debería ser el 0º dígito (más a la izquierda) de la 0ª (primera) permutación. El primer dígito de 1032 es 1.

Si la entrada es {4,1,1} entonces la salida es el segundo dígito de 1230, que es 2.

El número de fila puede ser mayor que el número de permutaciones. En ese caso, tome el resto del módulo el número de permutaciones (en el caso anterior, fila módulo 9).

En el lenguaje c sería genial.

(No es tarea, es por trabajo. Cuckoo hashing si debes saberlo. Me gustaría seleccionar aleatoriamente los swaps que haré en cada etapa para ver si es mejor que BFS cuando el número de tablas es mayor que dos.)

Answer 1

Enfoque de fuerza bruta en Python (puede usarlo para probar su implementación en 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

¿Por qué no solo construir un árbol e iterar a través de él?

Por ejemplo, si tiene los dígitos 0123 , entonces sabe que el dígito más a la izquierda solo puede ser del set {1,2,3} . Esto actuaría como tu primer nivel en tu árbol.

Luego, si sigue el camino que comienza con 1, solo tiene tres opciones, {0, 2, 3} . Si sigue el camino que comienza con 2 en el primer nivel, solo tiene dos opciones {0,3} (ya que no puede usar 1 en el segundo dígito desde la izquierda y el 2 era ya utilizado (puede hacer pop 2 de su lista de opciones)), etc.

Lo que debe tener en cuenta en este enfoque es si llega al final de una rama con 3 como su única opción, en cuyo caso, simplemente la eliminaría.

Para n > 10 generar todas las permutaciones y luego el filtrado puede volverse problemático. Creo que construir el árbol lo recortaría significativamente.

Puedes construir el árbol sobre la marcha si es necesario. Su orden puede definirse por cómo atraviesa el árbol.