Permutations With Unique Values

permutations with unique values

class unique_element:
    def __init__(self,value,occurrences):
        self.value = value
        self.occurrences = occurrences

def perm_unique(elements):
    eset=set(elements)
    listunique = [unique_element(i,elements.count(i)) for i in eset]
    u=len(elements)
    return perm_unique_helper(listunique,[0]*u,u-1)

def perm_unique_helper(listunique,result_list,d):
    if d < 0:
        yield tuple(result_list)
    else:
        for i in listunique:
            if i.occurrences > 0:
                result_list[d]=i.value
                i.occurrences-=1
                for g in  perm_unique_helper(listunique,result_list,d-1):
                    yield g
                i.occurrences+=1




a = list(perm_unique([1,1,2]))
print(a)

result:

[(2, 1, 1), (1, 2, 1), (1, 1, 2)]

EDIT (how this works):

I rewrote the above program to be longer but more readable.

I usually have a hard time explaining how something works, but let me try.
In order to understand how this works, you have to understand a similar but simpler program that would yield all permutations with repetitions.

def permutations_with_replacement(elements,n):
    return permutations_helper(elements,[0]*n,n-1)#this is generator

def permutations_helper(elements,result_list,d):
    if d<0:
        yield tuple(result_list)
    else:
        for i in elements:
            result_list[d]=i
            all_permutations = permutations_helper(elements,result_list,d-1)#this is generator
            for g in all_permutations:
                yield g

This program is obviously much simpler:
d stands for depth in permutations_helper and has two functions. One function is the stopping condition of our recursive algorithm, and the other is for the result list that is passed around.

Instead of returning each result, we yield it. If there were no function/operator yield we would have to push the result in some queue at the point of the stopping condition. But this way, once the stopping condition is met, the result is propagated through all stacks up to the caller. That is the purpose of

for g in perm_unique_helper(listunique,result_list,d-1): yield g
so each result is propagated up to caller.

Back to the original program:
we have a list of unique elements. Before we can use each element, we have to check how many of them are still available to push onto result_list. Working with this program is very similar to permutations_with_replacement. The difference is that each element cannot be repeated more times than it is in perm_unique_helper.

Prevent duplicates from itertools.permutations

There is no direct way to do that in itertools. The documentation for permutations() states:

Elements are treated as unique based on their position, not on their value.

This means that though the two As look equal to you, itertools treats them as if they are not equal, since they have different positions in the original string.

The number of the results you want is called the multinomial coefficient for 4 values, 2 equal and 2 others equal. You could get what you want by coding your own equivalent function to permutations but that would take a while to code and debug. (Perhaps call it multinomial though that word refers to a number, not the actual lists.) An easier way, perhaps slower in execution and memory usage but much faster in programming, is to use permutations and Python's set to remove the duplicates. You could do this:

from itertools import permutations

perm = permutations('AABB', 4)
for i in set(perm):
    print(i)

This may result in a different order to the printout. If you want to restore the original order, use sorted(set(perm)), since permutations returns in lexicographical order (if your original string was in sorted order).

Unique permutations with repeating elements in JavaScript

After having an equality criteria between the different permutations, we need to establish a canonical form for each pattern (equality class). We will then try to only generate those.

In your case, where order of 1s, 2s and 3s does not matter, we could decide that their respective first occurrences must be in the order 123, and 2 cannot appear without 1 and 3 not without 2. So whether the pattern is aabcbc, aacbcb, bbacac, …, or ccbaba, the only form that we want to generate is 112323. Or when the pattern is aaa/bbb/ccc we only generate 111 but not 222 or 333.

We can then write an algorithm which follows these rules for canonical forms:

function patterns(values, len) {
    function* recurse(list, used, depth) {
        if (depth == len) {
            yield list.slice();
        } else {
            for (let j=0; j<used; j++) { // only put already used values at this position
                list[depth] = values[j];
                yield* recurse(list, used, depth+1);
            }
            if (used < values.length) { // or the single next unused value
                list[depth] = values[used];
                yield* recurse(list, used+1, depth+1); // which is counted as used here
            }
        }
    }
    return recurse([], 0, 0);
}

This simply generates all combinations of a certain length from the distinct values, but you can use the same approach in your algorithm that generates permutations from a certain amount of non-unique values. It does get a bit more complicated though: the canonical form 121 cannot be achieved if we only have the values 122 available, but the pattern 212 still should be generated. We need to adjust our rule so that the ordering requirement is only amongst elements of the same number of occurrences. So we have to keep different used counts for them.

function permutationPatterns(elements) {
    const len = elements.length;
    const unique = new Map(elements.map(el => [el, {value: el, occurrences: 0}]));
    let max = 0;
    for (const el of elements) {
        const o = unique.get(el);
        max = Math.max(max, ++o.occurrences);
    }
    const byOccurrences = Array.from({length: max+1}, () => ({elements: [], used: 0}));
    for (const o of unique.values()) {
        byOccurrences[o.occurrences].elements.push(o);
    }

    function* generate(list, depth) {
        if (depth == len) {
            yield list.slice();
        } else {
            for (const options of byOccurrences) {
                options.used++;
                for (const option of options.elements.slice(0, options.used)) {
                    if (option.occurrences == 0) continue;
                    option.occurrences--;
                    list[depth] = option.value;
                    yield* generate(list, depth+1);
                    option.occurrences++;
                }
                options.used--;
            }
        }
    }
    return generate([], 0);
}

Itertools function to generate unique permutations

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')}

Generating Unique Permutations in Python

if i not in combos: will take a long time because membership testing in a list is (worst-case) O(N) -- it has to scan through each element. You can use a set instead:

>>> from itertools import permutations
>>> x = ["$5", "$10", "$10", "TAX", "$5", "20%", "BOGO", "BOGO", "TAX", "BOGO"]
>>> %time p = set(permutations(x, 9))
CPU times: user 0.88 s, sys: 0.01 s, total: 0.90 s
Wall time: 0.90 s
>>> len(p)
75600

R- Find Unique Permutations of Values

It should not be a dealbreaker that expand.grid includes all permutations. Just add a subset after:

combinations <- function(size, choose) {

  d <- do.call("expand.grid", rep(list(0:1), size))
  d[rowSums(d) == choose,]

}

combinations(size=10, choose=3)
#    Var1 Var2 Var3 Var4 Var5 Var6 Var7 Var8 Var9 Var10
# 8     1    1    1    0    0    0    0    0    0     0
# 12    1    1    0    1    0    0    0    0    0     0
# 14    1    0    1    1    0    0    0    0    0     0
# 15    0    1    1    1    0    0    0    0    0     0
# 20    1    1    0    0    1    0    0    0    0     0
# 22    1    0    1    0    1    0    0    0    0     0
...

---

Related Topics