How to remove all round table permutations from all permutations of a 1d Numpy array?

Question

I have this vector: [a,a,b,c,c] It is a pattern that is repeating itself in infinity, and I want to find all circular unique permutations of it.

[a,a,b,c,c] = [a,b,c,c,a] not ok (shifted 1 step to the right)

[a,a,b,c,c] = [b,c,c,a,a] not ok (shifted 2 steps to the right)

[a,c,b,a,c] ok [b,c,a,a,c] ok

An analogy would be: A round table with 5 seats. Position two males, to females and one child (genderless) in all possible unique ways.

is there a smart function for this numpy, scipy etc Would really much appreciate help.

Br Erik

How is the first one not ok and the second yes? What is your definition of circular? — Tomerikoo, May 07 '20 at 10:42
It is a rotating device so the pattern is repeating in infinity. ...1,1,0,-1,-1,1,1,0,-1,-1... so it doesn't matter where we start looking. — Erik Nyström, May 07 '20 at 10:55
Your second "ok" example `[1,-1,0,1,-1]` does not appear in that pattern, so why is it ok? — k_ssb, May 07 '20 at 11:01
Thats the point it, is not in that pattern... I want to have all unique patterns. If we have a round table with 5 seats I want to position the persons (values) i all the unique ways. Where the first person sits does not matter.. — Erik Nyström, May 07 '20 at 11:37

score 1 · Accepted Answer · answered May 07 '20 at 13:31

If I understand you correctly, then something like this can help you

from itertools import permutations


vector = [1,-1,0,1,-1]
unique_permutations = set(permutations(vector))
already_reviewed = []
for p in list(unique_permutations):
    if p not in already_reviewed:
        circular_permutations = [p[i:] + p[:i] for i in range(len(p))]
        already_reviewed.extend(circular_permutations)
        unique_permutations.difference_update(circular_permutations[1:])

print(unique_permutations)

Joe · Answer 2 · 2020-05-07T15:43:36.880

I created a vectorized solution inspired by this and this:

import numpy as np
from itertools import permutations

a = [1,1,0,-1,-1]

perms = np.array(list(set(permutations(a))))

# create all possible cyclic permutations, 
all_cyclic = np.array([np.roll(a, i) for i in range(perms.shape[1])])

def find_rows(remove_me, from_here):
    b = remove_me
    a = from_here

    # expand axis for broadcasting
    idx = a[:, np.newaxis, :] == b[np.newaxis ,: ,:]
    print(idx.shape)

    # in broadcasted array find identical arrays .all(-1)
    # that are IN `from_here`
    return idx.all(-1).any(-1)

x = find_rows(all_cyclic, perms)

# now we need to invert the result  
not_x = np.logical_not(x)

# now we can use not_x to pick the non-cyclic things
# from perms
perms_without = perms[not_x]

# TEST
for _ in all_cyclic:

    # to bool: numpy.array(old_matrix, dtype=bool)
    # or old_matrix != 0

    diff = (_ - perms) != 0
    print('in perms', np.any(np.all(np.logical_not(diff), axis=-1)))

    diff = _ - perms_without
    print('in perms without', np.any(np.all(np.logical_not(diff), axis=-1)))

Thanks for the answer but it is not the cyclic permutations i want. I want all permutation with the cyclic ones excluded... — Erik Nyström, May 07 '20 at 13:10
Hm, your question states *I want to find all circular unique permutations*. Or you may have to write *I want to find all permutations but without circular permutations* Maybe you are using circular in a misleading way as this would be something like all shifted 1, all shifted 2, etc. around the table. — Joe, May 07 '20 at 14:27

How to remove all round table permutations from all permutations of a 1d Numpy array?

2 Answers2