Permutations de récursion Python

vous voulez faire la récursion, donc vous devez d'abord savoir comment la récursion fonctionnerait. Dans ce cas, il est le suivant:

permutation [a,b,c,...] = [a + permutation[b,c,...], b + permutation[a,c,..], ...]

et comme condition finale:

permutation [a] = [a]

ainsi la récursion divise la liste en sous-listes avec un élément extrait à chaque fois. Cet élément est ensuite ajouté au recto de chacune des permutations de la sous-liste.

donc en pseudo-code:

def permutation(s):
   if len(s) == 1:
     return [s]

   perm_list = [] # resulting list
   for a in s:
     remaining_elements = [x for x in s if x != a]
     z = permutation(remaining_elements) # permutations of sublist

     for t in z:
       perm_list.append([a] + t)

   return perm_list

est-ce que ça aide?

pensez récursivement au scénario de base et construisez à partir de cette intuition.

1) Que se passe-t-il lorsqu'il n'y a qu'un caractère 'c'? Il n'y a qu'une seule permutation de cet élément, et donc nous retournons une liste contenant seulement cet élément.

2) Comment Pouvons-nous Générer la permutation suivante étant donné la dernière? Ajouter une lettre supplémentaire " a "à toutes les positions possibles dans la permutation précédente" c "nous donne "ca", "ac".

3) Nous pouvons continuer à construire des permutations de plus en plus grandes en ajoutant un caractère additionnel à toutes les positions possibles dans chaque permutation antérieure.

Le code suivant renvoie une liste d'un caractère si la chaîne a un caractère ou moins. Sinon, pour toutes les permutations n'incluant pas le dernier caractère de la chaîne s[-1], nous générons une nouvelle chaîne pour chaque position où nous pourrions inclure ce caractère et ajouter la nouvelle chaîne à notre liste actuelle de permutations.

def permutations(s):
    if len(s) <= 1:
        return [s]
    else:
        perms = []
        for e in permutations(s[:-1]):
            for i in xrange(len(e)+1):
                perms.append(e[:i] + s[-1] + e[i:])
        return perms

quand vous êtes perdu dans la fonction récursive, vous devriez dessiner l'arbre d'appel. La version suivante (inspiré @Ben réponse) garder l'entrée de commande (si l'entrée est dans l'ordre lexicographique, la liste des permutations seront, '012' -> ['012', '021', '102', '120', '201', '210'] .

def permut2(mystr):
    if len(mystr) <= 1:
        return [mystr]
    res = []
    for elt in mystr:
        permutations = permut2(mystr.replace(elt, ""))
        for permutation in permutations:
            res.append(elt + permutation)
    return res

la version suivante fonctionne pour les chaînes et les listes, notez que l'étape de reconstruction n'est pas la même:

def permut(array):
    if len(array) == 1:
        return [array]
    res = []
    for permutation in permut(array[1:]):
        for i in range(len(array)):
            res.append(permutation[:i] + array[0:1] + permutation[i:])
    return res

comme un exercice, vous devriez dessiner l'arbre d'appel des ces fonctions, faites-vous remarquez quelque chose ?

def permutations(string_input, array, fixed_value=""):
    for ch in string_input:
        permutations(string_input.replace(ch, ""), array, fixed_value + ch)
    if not string_input:
        array.append(fixed_value)

vous pouvez l'appeler par

array = []
permutations("cat", array)
print array

je sais que c'est un moi aussi, mais je pense que cela pourrait être plus facile pour certaines personnes de comprendre....

1. le cas de base est lorsque l'entrée n'est qu'un caractère.
2. configure une boucle for qui itère à travers chacune des lettres de la chaîne.
3. un autre pour boucle Permute récursivement à travers toutes les autres possibilités.

def permuter(s):

out = []

if len(s) == 1:
    out = [s]
else:
    for i,let in enumerate(s):
        for perm in permute(s[:i]+s[i+1:]):
            out += [let+perm]
return out