Backtracking Algorithm with conditional Python

Question

Backtracking Algorithm with conditional Python

Navigation

#1 by (1 votes)
#2 by (1 votes)

2

I am trying to solve an exercise that I think is quite simple, given a list, print all the possible combinations / permutations of x elements. That is, take out all possible combinations but give a filter for the results.

At the moment I have this:

def permutation( list , start , end ):
    if (start == end ):
        print list
    else:
        for i in xrange(start , end + 1):
            list[start] , list[i] = list[i] , list[start]            
            permutation( list , start + 1 , end )
            list[start] , list[i] = list[i] , list[start] #Backtracking

Example: list% co_of% of 2 elements, expected result% co_of%

And another doubt that I have is if there is any way to do it but with repetitions. With the previous example, the desired result: [a,b,c]

In my proposed exercise the list has 45 elements and combinations of 20 elements are requested.

python python-2.x

asked by niveloner 07.12.2016 в 12:30

source

2 answers

Problems with C libraries Eclipse create new combination keys

score 1 · Answer 1

There is a module in the standard librarian, itertools , that implements efficient iterators for many types of combinations.

from itertools import combinations, combinations_with_replacement

lista = [a, b, c]

# dos elementos, sin repetición
sin_repeticion = [x for x in combinations(lista, 2)]

# dos elementos, con repetición
con_repeticion = [x for x in combinations_with_replacement(lista, 2)]

link

The filter can be set as a conditional in the list comprehension or in a loop for on the iterator.

score 1 · Answer 2

A very simple way to solve it would be simply using list comprehension

mi_lista = [1,2,3,4]
# para los elementos con repeticiones, obtenemos una lista de tuplas
print [ (x,y) for x in mi_lista for y in mi_lista ]
# para los elementos sin repeticón solo agregamos la condición,
# para que los elementos x,y sean diferentes
print [ (x,y) for x in mi_lista for y in mi_lista if x!=y]