Question

Como implementar algoritmos para gerar permutações?

Answer 1

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)