# Como implementar algoritmos para gerar permutações?

+1 voto
424 visitas
perguntada Abr 20, 2016

## 1 Resposta

0 votos
respondida Abr 20, 2016 por (5,486 pontos)

Abaixo eu apresento vários algoritmos para a geração de permutações:

from collections import deque
import copy

def permutations_iterative_using_deque(myList):
n=len(myList)
u=deque()
for i in range(n):
if(i==0):
u.append([myList[0]])
else:
sizeu=len(u)
for j in range(sizeu):
v=u.popleft()[:]
sizev=len(v)
v.append(myList[i])
u.append(v[:]) # Note again v[:] instead of v
for k in range(sizev,0,-1):
aux=v[k]
v[k]=v[k-1]
v[k-1]=aux
u.append(v[:])
print u

def permutations_recursion(myList,u=[]):
n=len(myList)
sizeu=len(u)
if(sizeu==n):
print u
else:
u.append(myList[sizeu])
permutations_recursion(myList,u)
for i in range(sizeu+1):
aux=u[i]
u[i]=u[i-1]
u[i-1]=aux
permutations_recursion(myList,u)

def permutations_mimicking_recursion_using_stack(myList):
n=len(myList)
stack = [[myList[0]]]
while len(stack)!=0:
u=stack.pop()
sizeu=len(u)
if(sizeu==n):
print  u
else:
u.append(myList[sizeu])
stack.append(u[:]) # Discover the reason I am using u[:] instead of u
for j in range(sizeu,0,-1):
aux=u[j]
u[j]=u[j-1]
u[j-1]=aux
stack.append(u[:])

def permutations_iterative_using_deque_minimal_Change(myList):
n=len(myList)
u=deque() # List of all permutations
for i in range(n):
if(i==0):
u.append([myList[0]])
else:
sizeu=len(u)
right=True
for j in range(sizeu):
v=deque(u.popleft())
sizev=len(v)
if(right):
v.append(myList[i])
u.append(copy.copy(v)) # Note copy(v)
for k in range(sizev,0,-1):
aux=v[k]
v[k]=v[k-1]
v[k-1]=aux
u.append(copy.copy(v))
else:
v.appendleft(myList[i])
u.append(copy.copy(v)) # Note copy(v)
for k in range(0,sizev):
aux=v[k+1]
v[k+1]=v[k]
v[k]=aux
u.append(copy.copy(v))

if(right):
right=False
else:
right=True
print u

class Element:
def __init__(self, value,position):
self.value = value
self.arrow = 'left'
self.position=position

def change_arrow(self):
if (self.arrow=='left'):
self.arrow='right'
else:
self.arrow='left'

def finding_largest_mobile(myList):
n=len(myList)
maxMobileIndex=-1
maxMobile=-1
for i in range(n):
if((myList[i].arrow=='left')and(i>0)):
if(myList[i].position>myList[i-1].position):
if(myList[i].position>maxMobile):
maxMobile=myList[i].position
maxMobileIndex=i
if((myList[i].arrow=='right')and(i<n-1)):
if(myList[i].position>myList[i+1].position):
if(myList[i].position>maxMobile):
maxMobile=myList[i].position
maxMobileIndex=i
return maxMobileIndex

def johnson_trotter(myList):
n=len(myList)
u=[]
for i in range(n):
u.append(Element(myList[i],i))
print [u[i].value for i in range(n)]
hasMobile=True
while(hasMobile):
#for k in range(6):
maxMobileIndex=finding_largest_mobile(u)
#print "maxMobileIndex",maxMobileIndex
if(maxMobileIndex==-1):
hasMobile=False
else:
#print 'maxMobile',u[maxMobileIndex].value

for i in range(n):
if(u[i].position>u[maxMobileIndex].position):
u[i].change_arrow()

if(u[maxMobileIndex].arrow=='left'):
aux=u[maxMobileIndex]
u[maxMobileIndex]=u[maxMobileIndex-1]
u[maxMobileIndex-1]=aux
else: # right
aux=u[maxMobileIndex]
u[maxMobileIndex]=u[maxMobileIndex+1]
u[maxMobileIndex+1]=aux
print [u[i].value for i in range(n)]
#print [u[i].arrow for i in range(n)]

if __name__ == '__main__':

myList=['a','b','c']

print "Iterative using deque: "
permutations_iterative_using_deque(myList)

print "Recursion: "
permutations_recursion(myList)

print "Mimicking Recursion using stack: "
permutations_mimicking_recursion_using_stack(myList)

print "Iterative using deque minimal change: "
permutations_iterative_using_deque_minimal_Change(myList)

print 'Johnson_trotter'
johnson_trotter(myList)