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

Question

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.

Use something like `output2 = list(set(output))`, where `output` is what you got from `itertools`. — barak manos, Jun 09 '16 at 13:36
I need to iterate some numbers in all the positions inside the list, leaving alone the zero. — V.Petretto, Jun 09 '16 at 13:42

jsbueno · Accepted Answer · 2016-06-09T14:43:15.103

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:
                pivot_indexes.add(i)
        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
        seen.add(hperm)
        yield permutation

now you need to take a look at partitions of n where n is the number of zeros in the original list. The number of non-zero elements (k) is also important as they define the permissible partition types. for instance if k = 3 as in example above each partition can be expressed as a sum of k+1 values but not more. — Ma0, Jun 09 '16 at 14:08
no, I don't want them fixed, let me write an example of output: [0,0,1,0,8] [0,1,0,8,0] [1,0,8,0,0] [1,8,0,0,0] [8,0,1,0,0] and so on — V.Petretto, Jun 09 '16 at 14:16
(leaving this just to remark the comments above were about an earlier version of this answer. The current algorithm does permute the 0's) — jsbueno, Jun 09 '16 at 14:47

raayan · Answer 2 · 2016-06-09T14:01:37.870

2

Append each result to a List. Now you'll have every single possible combination and then do the following:

list(set(your_big_list))

Set will narrow down the list down to only the unique permutations. I'm not wholly sure if this is the problem you're trying to solve or you're worried about performance. Regardless just made an account so I thought I'd try to contribute something

edited Jun 09 '16 at 14:01

answered Jun 09 '16 at 13:42

raayan

86
5

1

the only problem i see with your approach is that it is computationally inefficient. There has to be a better way. – Ma0 Jun 09 '16 at 13:46
yes, the problem I'm trying to solve is for performance and speed. using large lists of numbers, for example of 30 or more, the program works too much time, and a lot of work is wasted, ergo not efficient. – V.Petretto Jun 09 '16 at 13:51
`Set` and `List` are not even Python built-ins. Maybe you meant `list` and `set` – jsbueno Jun 09 '16 at 13:53
Not to mention this does throw away not only all but one zeros (and their position) long with any other repetitions – jsbueno Jun 09 '16 at 13:57
Yeah fixed those capitalization issues. – raayan Jun 09 '16 at 14:04

score 0 · Answer 3 · answered Jun 09 '16 at 13:43

0

Your questions is unclear, but if you are trying to list the permutations without having 0 in your output, you can do it as follows:

from itertools import permutations
def perms( listy ):
    return permutations( [i for i in listy if i!=0])

answered Jun 09 '16 at 13:43

Brian

1,659
12
17

1

i don't think that this is what he wants but this can be the basis for it. you can now impregnate your permutations with 0s to generate even more combinations each of which has the length of the original list ☺ – Ma0 Jun 09 '16 at 13:45
1

I need the 0 in the output but I don't need it to be part of the permutation. this to avoid duplicate output and loss of cpu work. maybe I can create a base list of zeros and then insert the permuted numbers in it ? – V.Petretto Jun 09 '16 at 13:56

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

3 Answers3