Trouver les permutations où aucun élément ne reste en place

Question

Je travaille avec des permutations où chaque élément est différent de son emplacement d'origine. Je voudrais un algorithme qui donne {une longueur d'entrée, ligne et chiffre}, me donnera le nombre de sortie. Voici un exemple:

Si la longueur en entrée est quatre, toutes les permutations de 0123 sont:

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

Les permutations dans lesquelles aucun chiffre n'est au même endroit (chaque chiffre a été déplacé):

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

La numérotation commence à 0; par conséquent, si l'entrée de la fonction est {4,0,0}, le résultat doit correspondre au 0ème chiffre (le plus à gauche) de la 0ème (première) permutation. Le premier chiffre de 1032 est 1.

Si l'entrée est {4,1,1}, la sortie est le deuxième chiffre de 1230, qui est 2.

Le numéro de ligne peut être supérieur au nombre de permutations. Dans ce cas, prenez le reste modulo le nombre de permutations (dans le cas ci-dessus, rangée modulo 9).

Dans le langage c, ce serait génial.

(Ce ne sont pas des devoirs, mais bien du travail. Cacao si vous devez savoir. J'aimerais sélectionner au hasard les échanges que je ferai à chaque étape pour voir si c'est meilleur que BFS lorsque le nombre de tables est supérieur à deux.)

Answer 1

Approche par force brute en Python (vous pouvez l’utiliser pour tester votre implémentation 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

Pourquoi ne pas simplement construire un arbre et le parcourir?

Par exemple, si vous avez les chiffres 0123 , vous savez que le chiffre le plus à gauche ne peut provenir que du set {1,2,3} . Cela agirait comme votre premier niveau dans votre arbre.

Ensuite, si vous suivez le chemin commençant par 1, vous ne disposez que de trois options, {0, 2, 3} . Si vous descendez le chemin commençant par 2 au premier niveau, vous n’avez que deux options {0,3} (vous ne pouvez pas utiliser 1 dans le deuxième chiffre à partir de la gauche et le 2 était déjà utilisé (vous pouvez extraire le 2 de votre liste de choix)), etc.

Dans cette approche, il convient de rester vigilant si vous arrivez à la fin d'une branche avec 3 comme seule option, auquel cas il vous suffirait de la supprimer.

Pour n > 10 générer toutes les permutations puis filtrer peut devenir problématique. Je pense que la construction de l'arbre réduirait cela de manière significative.

Vous pouvez créer l’arbre à la volée si besoin est. Votre commande peut être définie par la façon dont vous parcourez l’arbre.