Prise en compte des indices lors de la recherche de permutations de list int en utilisant la récursivité en python?

Question

J'essaye de trouver toutes les permutations d'une liste d'entiers d'une gamme spécifique en utilisant la récursivité. Par exemple, si lst = [0,1,2], un appel à def permute(lst, 0, 1) doit renvoyer [[0,1], [1,0]] dans ce format. De même, un appel à permute(lst, 0, 2) doit renvoyer [[0,1,2], [0,2,1]...].

Jusqu'à présent, mon code ne fonctionne que pour trouver des permutations d'une liste complète, de l'index 0 à len (LST):

def permute(lst, low, high): 
    if low == high: 
     print(lst) 
    for index in range(low, high + 1): 
      lst[index], lst[low] = lst[low], lst[index] 
      permute(lst, low + 1, high) 
      lst[index], lst[low] = lst[low], lst[index] 

Où low = 0 et high est le len(lst).

Si je change les indices dans ce code, je n'obtiens pas une sortie correcte. Toute suggestion sur la façon de prendre en compte les indices?

Answer 1

Vous pouvez le faire avec une fonction récursive intérieure, .: par exemple

def permute(lst, start, end): 
    def permutations(l): 
     if len(l) <= 1: 
      return [l] 
     a = [] 
     for p in permutations(l[:-1]): 
      for i in range(len(l)): 
       a.append(p[i:] + [l[-1]] + p[:i]) 
     return a 
    return permutations(lst[start:end+1]) 

In [] 
lst = [0,1,2,3,4] 
permute(lst, 0, 1) 

Out[]: 
[[0, 1], [1, 0]] 

In [] 
permute(lst, 0, 2) 

Out[]: 
[[0, 1, 2], [1, 2, 0], [2, 0, 1], [1, 0, 2], [0, 2, 1], [2, 1, 0]] 

Answer 2

Voici une version de votre code qui utilise un argument supplémentaire pour rappeler la position de départ de la liste. J'ai changé votre fonction en un générateur récursif, donc il donne les valeurs, plutôt que de les imprimer. J'ai également changé high à stop, ce qui est compatible avec la convention utilisée dans le découpage de Python par exemple, seq[start:stop], et range(start, stop).

def permute(lst, start, stop, low=None): 
    if low == stop - 1: 
     yield lst[start:stop] 
    if low is None: 
     low = start 
    for index in range(low, stop): 
      lst[index], lst[low] = lst[low], lst[index] 
      for t in permute(lst, start, stop, low + 1): 
       yield t 
      lst[index], lst[low] = lst[low], lst[index] 

# Test 
lst = list(range(5)) 
print(list(permute(lst, 1, 4))) 

for t in permute(lst, 0, 3): 
    print(t) 

sortie

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]] 
[0, 1, 2] 
[0, 2, 1] 
[1, 0, 2] 
[1, 2, 0] 
[2, 1, 0] 
[2, 0, 1] 

---

Ce code fonctionne de façon identique sur Python 2 & 3, bien que dans Python 3, il peut être un peu plus efficace (et plus compact) en utilisant le yield from syntaxe. Remplacez cette for t in permute ... boucle avec

yield from permute(lst, start, stop, low + 1) 

En Python 3, vous pouvez également créer une liste des valeurs d'une manière plus compacte:

[*permute(lst, 1, 4)] 

---

Enfin, voici un autre générateur récursif construit de votre algorithme, mais il permute toute la liste. Bien sûr, vous pouvez l'appeler avec une fonction d'interface pour permuter une sous-liste.

def permuter(lst): 
    if not lst: 
     yield lst 
    for index in range(len(lst)): 
     lst[index], lst[0] = lst[0], lst[index] 
     first = lst[:1] 
     for t in permuter(lst[1:]): 
      yield first + t 
     lst[index], lst[0] = lst[0], lst[index] 

def permute(lst, start, stop): 
    yield from permuter(lst[start:stop]) 

lst = list(range(5)) 
print(list(permute(lst, 1, 4)))