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 donné {une longueur d'entrée, ligne et chiffre}, me donnera le numéro de sortie. Voici un exemple:

Si la longueur d'entrée est de quatre, toutes les permutations desont:

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 dont aucun chiffre est au même endroit (chaque chiffre est déplacé):

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

La numérotation commence à 0, donc si l'entrée à la fonction est {4,0,0}, la sortie doit être le 0ème chiffre (le plus à gauche) de la 0e (première) permutation. Le premier chiffre de 1032 est 1.

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

Le numéro de ligne est peut-être plus le nubmer de permutations. Dans ce cas, prendre le reste modulo le nombre de permutations (dans le cas ci-dessus, ligne modulo 9).

Dans la langue c serait génial.

(Ce ne sont pas des devoirs, c'est pour le travail.) Si vous devez savoir, j'aimerais sélectionner aléatoirement les swaps que je ferai à chaque étape pour voir si c'est mieux que BFS quand le nombre de tables . est supérieur à deux)

Answer 1

approche 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 itérer à travers elle? Par exemple, si vous avez les chiffres 0123, alors vous savez que le chiffre le plus à gauche ne peut être que set {1,2,3}. Cela agirait comme votre premier niveau dans votre arbre. Ensuite, si vous descendez le chemin commençant par 1, vous avez seulement trois options, {0, 2, 3}. Si vous descendez le chemin commençant par 2 dans le premier niveau, vous n'avez que deux options {0,3} (puisque vous ne pouvez pas utiliser 1 dans le deuxième chiffre à partir de la gauche et le 2 était déjà utilisé (vous pourriez faire apparaître les 2 de votre liste de choix)), etc.

La chose à surveiller dans cette approche est si vous arrivez à la fin d'une branche avec 3 étant votre seule option, dans ce cas, vous devez simplement le 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 construire l'arbre à la volée si besoin est. Votre commande peut être définie par la façon dont vous traversez l'arbre.