CODEWITHSUNDEEP
pythonpython-itertools
JoeJackJessieJames
JoeJackJessieJames

Reputation: 759

Permutation without duplicates in Python

I have N positions, and each position can be either 0 or 1. I have fixed number of 1s, and I want to permutate these fixed number of 1s in these N positions.

from itertools import permutations
p = [0 for k in xrange(6)]
for k in xrange(0,3):
        p[k] = 1
print(list(permutations(p)))

But above result contains four [0,0,0,1,1,1] in the list. I only want one of them. How can I get rid of these duplicates?

Upvotes: 14

Views: 27685

Answers (3)

hiro protagonist
hiro protagonist

Reputation: 46849

what you are looking for is a multiset permutation.

sympy provides the function multiset_permutations:

from sympy.utilities.iterables import multiset_permutations

n_zeros, n_ones = 3, 3
for perm in multiset_permutations(n_zeros * (0,) + n_ones * (1,)):
    print(perm)

which outputs:

[0, 0, 0, 1, 1, 1]
[0, 0, 1, 0, 1, 1]
[0, 0, 1, 1, 0, 1]
[0, 0, 1, 1, 1, 0]
[0, 1, 0, 0, 1, 1]
[0, 1, 0, 1, 0, 1]
[0, 1, 0, 1, 1, 0]
[0, 1, 1, 0, 0, 1]
[0, 1, 1, 0, 1, 0]
[0, 1, 1, 1, 0, 0]
[1, 0, 0, 0, 1, 1]
[1, 0, 0, 1, 0, 1]
[1, 0, 0, 1, 1, 0]
[1, 0, 1, 0, 0, 1]
[1, 0, 1, 0, 1, 0]
[1, 0, 1, 1, 0, 0]
[1, 1, 0, 0, 0, 1]
[1, 1, 0, 0, 1, 0]
[1, 1, 0, 1, 0, 0]
[1, 1, 1, 0, 0, 0]

Upvotes: 3

Ry-
Ry-

Reputation: 224904

You could grab the positions of the 1s instead:

from itertools import combinations


def place_ones(size, count):
    for positions in combinations(range(size), count):
        p = [0] * size

        for i in positions:
            p[i] = 1

        yield p

In action:

>>> list(place_ones(6, 3))
[
    [1, 1, 1, 0, 0, 0],
    [1, 1, 0, 1, 0, 0],
    [1, 1, 0, 0, 1, 0],
    [1, 1, 0, 0, 0, 1],
    [1, 0, 1, 1, 0, 0],
    [1, 0, 1, 0, 1, 0],
    [1, 0, 1, 0, 0, 1],
    [1, 0, 0, 1, 1, 0],
    [1, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 1, 1],
    [0, 1, 1, 1, 0, 0],
    [0, 1, 1, 0, 1, 0],
    [0, 1, 1, 0, 0, 1],
    [0, 1, 0, 1, 1, 0],
    [0, 1, 0, 1, 0, 1],
    [0, 1, 0, 0, 1, 1],
    [0, 0, 1, 1, 1, 0],
    [0, 0, 1, 1, 0, 1],
    [0, 0, 1, 0, 1, 1],
    [0, 0, 0, 1, 1, 1],
]

Upvotes: 13

Peter Pei Guo
Peter Pei Guo

Reputation: 7870

Set is perfect for this, as set does not not contain any duplicated element:

set(permutations(p))

Upvotes: 7

Related Questions