CODEWITHSUNDEEP
pythonlistpermutation
user3238710
user3238710

Reputation: 3

List of permutations with repeated elements

I'm trying to create a function that takes in a list of elements and recursively returns a list containing all permutations (of length r) of that list. However, if there is a -1 on the list, it should be able to be repeated.

For example, with the list [0, -1, 2] with r = 2 I would want returned [0, -1], [-1, 0], [0, 2], [2, 0], [-1, 2], [2, -1] and [-1, -1].

Here is my function so far:

def permutations(i, iterable, used, current, comboList, r):
    if (i == len(iterable):
        return
    if (len(current) == r):
        comboList.append(current)
        print current
        return
    elif (used[i] != 1):
        current.append(iterable[i])
        if (iterable[i][0] != -1):
            used[i] = 1 
    for j in range(0, len(iterable)):
        permutations(j+1, iterable, used, current, comboList, r)
        used[i] = 0
    return comboList

As you can see, I'm incorrectly trying to utilized a "visited list" that keeps track of what elements of the list have and have not been visited.

Upvotes: 0

Views: 520

Answers (2)

Karl Knechtel
Karl Knechtel

Reputation: 61643

Leverage itertools.permutations. You (apparently) want permutations that use any number of -1s, as well as possibly the other elements; but you want to discard duplicates.

We can allow any number of -1s by simply providing as many -1s as elements we are choosing.

We can discard duplicates by using a set.

import itertools
def unique_permutations_with_negative_ones(iterable, size):
    # make a copy for inspection and modification.
    candidates = tuple(iterable)
    if -1 in candidates:
        # ensure enough -1s.
        candidates += ((-1,) * (size - candidates.count(-1)))
    return set(itertools.permutations(candidates, size))

Let's try it:

>>> unique_permutations_with_negative_ones((0, -1, 2), 2)
{(2, -1), (-1, 0), (-1, 2), (2, 0), (-1, -1), (0, -1), (0, 2)}

Upvotes: 0

Steve Jessop
Steve Jessop

Reputation: 279405

There's probably a neater way, but something like this completely untested code:

def apply_mask(mask, perm):
    return [perm.pop() if m else -1 for m in mask]

def permutations(iterable, r):
    if -1 not in iterable:
        # easy case
        return map(list, itertools.permutations(iterable, r)))
    iterable = [x for x in iterable if x != -1]
    def iter_values():
        for mask in itertools.product((True, False), repeat=r):
            for perm in itertools.permutations(iterable, sum(mask)):
                yield apply_mask(mask, list(perm))
    return list(iter_values())

That is to say: first iterate over all possible "masks", where the mask tells you which elements will contain -1 and which will contain another value. Then for each mask, iterate over all permutations of the "other values". Finally, use apply_mask to slot the values and the -1s into the right places in the result.

Upvotes: 1

Related Questions