Encontrar as permutações onde há estadias elemento em lugar

Question

Eu estou trabalhando com permutações onde cada elemento é diferente da sua localização original. Eu gostaria de um algoritmo que dado {um comprimento de entrada, linha e dígitos}, vai me dar o número de saída. Aqui está um exemplo:

Se o comprimento de entrada é de quatro, então todas as permutações de 0123 são:

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

As permutações em que nenhum dígito é no mesmo lugar (todos os dígitos mudou):

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

A numeração começa em 0 por isso, se a entrada para a função é {4,0,0}, a saída deve ser a 0 (mais à esquerda) dígito do 0 (primeiro) de permutação. O primeiro algarismo de 1032 é 1.

Se a entrada é {4,1,1}, em seguida, a saída é o segundo digito de 1230, o qual é 2.

O número de linha pode ser maior do nubmer de permutações. Nesse caso, tomar o restante módulo do número de permutações (no caso acima, linha módulo 9).

Na linguagem c seria ótimo.

(não é uma lição de casa, é para o trabalho. Cuckoo hashing se você deve saber. Eu gostaria de selecionar aleatoriamente os swaps que eu vou estar fazendo em cada etapa para ver se ele é melhor do que BFS quando o número de mesas é maior do que dois.)

Answer 1

abordagem de força bruta em Python (você pode usá-lo para testar a sua implementação 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 que não construir uma árvore e iterate através dele?

Por exemplo, se você tem a 0123 dígitos, então você sabe que o dígito mais à esquerda pode ser apenas do set {1,2,3}. Este agiria como seu primeiro nível em sua árvore.

Então, se você percorrer o caminho começando com 1, você só tem três opções, {0, 2, 3}. Se você percorrer o caminho que começa com 2 no primeiro nível, você só tem duas opções {0,3} (desde que você não pode usar 1 no segundo dígito da esquerda ea 2 já foi usado (você pode colocar o 2 da sua lista de opções)), etc.

A coisa que atente para nesta abordagem é que se você chegar ao final de um ramo com 3 sendo a sua única opção, caso em que, você teria apenas excluí-lo.

Para n > 10 gerar todas as permutações e depois filtrando pode se tornar problemática. Acho construindo a árvore iria cortar essa significativamente.

Você pode construir a árvore na mosca se for necessário. Seu pedido pode ser definida pela forma como você percorrer a árvore.