V.Petretto - 2 years ago 86
Python Question

# How to generate permutations of a list without “moving” zeros. in Python

using the

`itertools`
tool, I have all the possible permutations of a given list of numbers, but if the list is as follows:

``````List=[0,0,0,0,3,6,0,0,5,0,0]
``````

`itertools`
does not "know" that iterating the zeros is wasted work, for example the following iterations will appear in the results:

``````List=[0,3,0,0,0,6,0,0,5,0,0]

List=[0,3,0,0,0,6,0,0,5,0,0]
``````

they are the same but
`itertools`
just takes the first zero ( for example ) and moves it at the fourth place in the list and vice-versa.

The question is: how can I iterate only some selected numbers and left alone others such like zero ? it can be with or without
`itertools`
.

Voilá - it works now - after getting the permutations on the "meat", I further get all possible combnations for the "0"s positions and yield one permutation for each possible set of "0 positions" for each permutation of the non-0s:

``````from itertools import permutations, combinations

def permut_with_pivot(sequence, pivot=0):
pivot_indexes = set()
seq_len = 0
def yield_non_pivots():
nonlocal seq_len
for i, item in enumerate(sequence):
if item != pivot:
yield item
else:
seq_len = i + 1

def fill_pivots(permutation):
for pivot_positions in combinations(range(seq_len), len(pivot_indexes)):
sequence = iter(permutation)
yield tuple ((pivot if i in pivot_positions else next(sequence)) for i in range(seq_len))

for permutation in permutations(yield_non_pivots()):
for filled_permutation in fill_pivots(permutation):
yield filled_permutation
``````

(I've used Python's 3 "nonlocal" keyword - if you are still on Python 2.7, you will have to take another approach, like making `seq_len` be a list with a single item you can then repplace on the inner function)

My second try (the working one is actually the 3rd)

This is a naive approach that just keeps a cache of the already "seen" permutations - it saves on the work done to each permutation but notonthe work to generate all possible permutations:

``````from itertools import permutations

def non_repeating_permutations(seq):
seen = set()
for permutation in permutations(seq):
hperm = hash(permutation)
if hperm in seen:
continue