Backtracking problem

Joan Pallarès joan.pallares at gmail.com
Fri Jul 18 18:39:30 CEST 2008


Hi,

In my first message in the list I'm going to ask you to solve this problem
or at least help me to solve it by myself:

We have a list a couples created this way:
*parejas = [(1, 'a'), (1, 'b'), (1, 'c'), (1, 'd'),
               (2, 'a'), (2, 'b'), (2, 'c'),
               (3, 'a'), (3, 'b'), (3, 'c'), (3, 'd')]*

We want to get all te possible combinations in an ordered way. Good
combinations examples are:
*1a,2b,3c
1a,2b,3d
1b,2a,3c*

As you note, the numbers or characters cannont be repeated.
The objective is to get one possible combination and if the user wants
another possible combination he can get it. And if he wants to get bak the
previous combiantion is also has to be possible. That's way I said to *get
all possible combinations in an ordered way.
*
I made a Backtracking algorithm and I get the first result, but I'm not able
to get the following result. Any help?


My code, just in case it helps you:
*parejas = [(1, 'a'), (1, 'b'), (1, 'c'), (1, 'd'),
           (2, 'a'), (2, 'b'), (2, 'c'),
           (3, 'a'), (3, 'b'), (3, 'c'), (3, 'd')]
print parejas

listasCorrectas = []
lista = []

def numerosDiferentes(lista):
    numeros = []
    letras = []
    for numero,letra in lista:
        numeros.append(numero)
        letras.append(letra)
    if len(numeros) == len(set(numeros)) and len(letras) ==
len(set(letras)):
        return True
    return False


def backTracking(parejas,lista):
    if len(lista) == 3 and numerosDiferentes(lista):
        listasCorrectas.append(lista)
        print 'LISTA CORRECTA',lista

        return

    if len(lista) < 2:
        lista.append(parejas[0])
        print lista
        backTracking(parejas[1:],lista)

    while(not numerosDiferentes(lista) and len(lista)>1):
        lista = lista[:-1]


    lista.append(parejas[0])
    print lista
    backTracking(parejas[1:],lista)

backTracking(parejas,lista)*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20080718/81345d01/attachment.html>


More information about the Python-list mailing list