List of all permutations but without opposite numbers

Question

I need to create a list of all the permutation but excluding that ones where there is the same number changed of sign.

For example, from the sequence

[-2, -1, 1, 2]

I would obtain all permutations like these:

[-2, -1], [-2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2], [2, -1], [2, 1]

At the moment I use the following code:

permutation_items = []
permutations = itertools.permutations(range_items, items)
permutation_item = list(permutations)

where for example range_items = [-2, -1, 1, 2] and items = 2

Then to eliminate all opposite duplicates I use

for element in permutation_items:
    flag=0
    for j in element:
        if ((j in element) & ((j*-1) in element)):
            flag = 1
            break
    if flag == 0:
        all_solutions.append(element)

I think this is not the best way because first I create a list with all permutations then I delete those I don't want, could you suggest a better way? Also because if I need to create a list of permutations with 10 or more numbers it becomes very big...

Do you think I'll have some problems with these dimensions?

Please note: with these permutations I need to do further operations (I need to find the minimum number of permutations that give all possible couples of numbers), so I think I need to store them in a variable, also because at the end of my algorithm I need to store results in a file.

...ok guys, your answer are very good and I like your interest...now, if I use for my variable 'range_items' a list of 30 elements (positives and negatives) the time used by the code is very big, I am thinking to ask you for a multithread solution (so I can load the code in a cluster with many cores)...is it feasible?

Answer 1

You are basically asking how to combine permutation and product. The following is much more efficient (and simpler) than rejection: You generate all permutations exactly once, and then twiddle the signs. It is asymptotically optimal in terms of time O(N!) and space O(1):

def plusAndMinusPermutations(items):
    for p in permutations(items):
        for signs in product([-1,1], repeat=len(items)):
            yield [a*sign for a,sign in zip(p,signs)]

(using itertools as the OP is)

Demo:

>>> list( plusAndMinusPermutations([1,2]) )
[
 [-1, -2], 
 [-1, 2], 
 [1, -2],
 [1, 2],
 [-2, -1],
 [-2, 1],
 [2, -1],
 [2, 1]
]

This is more efficient by a factor of factorial(N)!!! (Assuming you were using it for lengths larger than 2.)

Alternatively, we can combine them in the opposite order (and map list onto the tuples if you'd like):

def plusAndMinusPermutations(items):
    for signed in product(*[[-a,a] for a in items]):
        for p in permutations(signed):
            yield p

>>> list( plusAndMinusPermutations([1,2]) )
[
 (-1, -2), 
 (-2, -1), 
 (-1, 2), 
 (2, -1), 
 (1, -2), 
 (-2, 1), 
 (1, 2), 
 (2, 1)
]

---

edit in response to OP edit:

I need to find the minimum number of permutations that give all possible couples of numbers --OP

I'm not sure what this mean, but based on how you've phrased it, you almost certainly don't need to do any of this. Just brute-force the problem for numbers from 0 to 10 using your existing method, then input the results into http://oeis.org/ and you will probably find an explicit formula.

Answer 2

The following uses the same rejection approach as your code, but is much more efficient:

(s for s in itertools.permutations(l, 2) if len(set(map(abs, s))) == len(s))

where l is the sequence.

The only tricky bit is len(set(map(abs, s))) == len(s). It puts the absolute values of all elements of the permutation into a set, and ensures that the set has the same size as the permutation.

To make it even faster, you can replace len(s) with the length of the permutation (2 in the example above).

The only algorithmic improvement that I can think of is to remove duplicate numbers from the original sequence. Whether or not that buys you much depends on whether you're like to have duplicates in the first place.

Answer 3

I thought about it a bit more, and I think you'll like this:

from collections import defaultdict
from itertools import permutations, product

def make_groups(seq):
    found = defaultdict(set)
    for num in seq:
        found[abs(num)].add(num)
    return [list(v) for v in found.itervalues()]

def selective_permutations(seq, r=None):
    for g in permutations(make_groups(seq), r):
        for p in product(*g):
            yield p

It takes your input sequence - for example [-2, -1, 0, 1, 2] - and groups it by mutually-exclusive values - so [[-2, 2], [-1, 1], [0]].

It then runs permutations on the groups - so you will get, for example, [[-2, 2], [-1, 1]] - then runs product against the resulting groups, yielding [[-2, -1], [-2, 1], [2, -1], [2, 1]], which is what we were looking for.

It respects the r parameter (for sequence length), and does an optimally efficient job on both balanced and unbalanced sequences - so, for example:

for p in selective_permutations([-3,-2,1,2], 2):
    print p

results in

(1, 2)
(1, -2)
(1, -3)
(2, 1)
(-2, 1)
(2, -3)
(-2, -3)
(-3, 1)
(-3, 2)
(-3, -2)

without having to discard any combinations.

Hope that helps! ;-)

Answer 4

assuming you only wants the numbers in pairs (if not you have to do something with recursion), and no equal numbers in the sequence

def make_perm(sequens):
    perm_s = []
    for e1 in sequens:
        for e2 in sequens:
            if abs(e1) != abs(e2):
               perm_s += [[e1,e2]] 

    return perm_s

print make_perm([-2,-1,1,2])

output:

[[-2, -1], [-2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2], [2, -1], [2, 1]]

this solution handles different item length.

def perm(list_to_perm,perm_l,items):
    if len(perm_l) == items:
        print perm_l
    else:
        for i in  list_to_perm:

            if i not in perm_l:
                if -i not in perm_l:
                    perm(list_to_perm,list(perm_l) +[i],items)


a = [-2,-1,1,2]
perm(a,[],2)

output:

[-2, -1]
[-2, 1]
[-1, -2]
[-1, 2]
[1, -2]
[1, 2]
[2, -1]
[2, 1]

Answer 5

This may seem a bit strange. I'm still learning python. I'm duplicating code so the order is more natural. There are probably shortcuts. This turns out to be the answer to a Rosalind.info problem. I don't like the code, it's a bit noisy but it works.

    def signedPerm(x):
        if len(x) == 1:
            yield x
            x[0]*=-1
            yield x
        else:
            for i in range(len(x)):
            for s in [1, -1]:
            y=[x[i]*s]
            for j in signedPerm(x[:i]+x[i+1:]):
              yield y+j

then call

    [x for x in signedPerm(list(set([abs(y) for y in [-1, -2, 1, 4]])))]