kPow989
kPow989

Reputation: 426

Itertools function to generate unique permutations

I want to know if there is an itertools way to produce the following combinations/permutations:

list = ['x', 'o']

# when character 'x' is allowed to occupy 1 place with total places of 4:

a = [['o','o','o','x'],
     ['o','o','x','o'],
     ['o','x','o','o'],
     ['x','o','o','o']]

# when character 'x' is allowed to occupy 2 places with total places of 4:

b = [['o','o','x','x'],
     ['o','x','x','o'],
     ['x','x','o','o'],
     ['x','o','x','o'],
     ['o','x','o','x'],
     ['x','o','o','x']]

I was wondering if there was a way to do this using itertools.product or a similar function to achieve this?

Upvotes: 2

Views: 2123

Answers (2)

MSeifert
MSeifert

Reputation: 152647

You could create your own function (or generator) based on itertools.combinations:

from itertools import combinations

def equivalence_permutations(x, o):
    """Create all unique permutations with `x` x'es and `o` o's."""
    total = x+o
    for indices in combinations(range(total), x):
        lst = ['o']*total
        for index in indices:
            lst[index] = 'x'
        yield lst

The combinations makes sure the indices are unique without needing to use set or any other greedy operation. So it should be much faster in those cases. For example:

>>> list(equivalence_permutations(2, 2))  # 2 x and 2 o
[['x', 'x', 'o', 'o'],
 ['x', 'o', 'x', 'o'],
 ['x', 'o', 'o', 'x'],
 ['o', 'x', 'x', 'o'],
 ['o', 'x', 'o', 'x'],
 ['o', 'o', 'x', 'x']]

>>> list(equivalence_permutations(1, 3))  # 1 x and 3 o
[['x', 'o', 'o', 'o'],
 ['o', 'x', 'o', 'o'],
 ['o', 'o', 'x', 'o'],
 ['o', 'o', 'o', 'x']]

Upvotes: 3

Vinícius Figueiredo
Vinícius Figueiredo

Reputation: 6518

itertools.permutations also accepts strings as paramater:

from itertools import permutations
>>> list(permutations("ooox"))
[('o', 'o', 'o', 'x'), ('o', 'o', 'x', 'o'), ('o', 'o', 'o', 'x'), ('o', 'o', 'x', 'o'), ('o', 'x', 'o', 'o'), ('o', 'x', 'o', 'o'), ('o', 'o', 'o', 'x'), ('o', 'o', 'x', 'o'), ('o', 'o', 'o', 'x'), ('o', 'o', 'x', 'o'), ('o', 'x', 'o', 'o'), ('o', 'x', 'o', 'o'), ('o', 'o', 'o', 'x'), ('o', 'o', 'x', 'o'), ('o', 'o', 'o', 'x'), ('o', 'o', 'x', 'o'), ('o', 'x', 'o', 'o'), ('o', 'x', 'o', 'o'), ('x', 'o', 'o', 'o'), ('x', 'o', 'o', 'o'), ('x', 'o', 'o', 'o'), ('x', 'o', 'o', 'o'), ('x', 'o', 'o', 'o'), ('x', 'o', 'o', 'o')]

and

>>> list(permutations("ooxx"))
[('o', 'o', 'x', 'x'), ('o', 'o', 'x', 'x'), ('o', 'x', 'o', 'x'), ('o', 'x', 'x', 'o'), ('o', 'x', 'o', 'x'), ('o', 'x', 'x', 'o'), ('o', 'o', 'x', 'x'), ('o', 'o', 'x', 'x'), ('o', 'x', 'o', 'x'), ('o', 'x', 'x', 'o'), ('o', 'x', 'o', 'x'), ('o', 'x', 'x', 'o'), ('x', 'o', 'o', 'x'), ('x', 'o', 'x', 'o'), ('x', 'o', 'o', 'x'), ('x', 'o', 'x', 'o'), ('x', 'x', 'o', 'o'), ('x', 'x', 'o', 'o'), ('x', 'o', 'o', 'x'), ('x', 'o', 'x', 'o'), ('x', 'o', 'o', 'x'), ('x', 'o', 'x', 'o'), ('x', 'x', 'o', 'o'), ('x', 'x', 'o', 'o')]

To store them in a list of lists as shown in your question you can use map(list, permutations("ooox")).

As you mentioned in the comment section, we can write a specific function for that job, that takes the inputs you want, but notice this will behave in a not so desired way when the first string is not of length 1:

from itertools import permutations
def iterate(lst, length, places):
    return set(permutations(lst[0]*(length-places)+lst[1]*places))

Demo:

>>> from pprint import pprint
>>> pprint(iterate(["o","x"], 4, 1))
{('o', 'o', 'o', 'x'),
 ('o', 'o', 'x', 'o'),
 ('o', 'x', 'o', 'o'),
 ('x', 'o', 'o', 'o')}
>>> pprint(iterate(["o","x"], 4, 2))
{('o', 'o', 'x', 'x'),
 ('o', 'x', 'o', 'x'),
 ('o', 'x', 'x', 'o'),
 ('x', 'o', 'o', 'x'),
 ('x', 'o', 'x', 'o'),
 ('x', 'x', 'o', 'o')}

Upvotes: 3

Related Questions