Backtracking Algorithm with conditional Python

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.

asked by niveloner 07.12.2016 в 12:30
source

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)]
``````

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

``````mi_lista = [1,2,3,4]