V.Petretto V.Petretto - 4 months ago 9
Python Question

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

using the

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


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



they are the same but
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


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
        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:
        yield permutation