Generate all unique permutations of 2d array

Question

I would like to be able to generate all unique permutations of a 2d array in python.

For example take this 2d array [[1,1],[0,0]] I would like back

[[0,0],
[1,1]]

[[0,1],
[0,1]]

[[0,1]
[1,0]]

[[1,0]
[0,1]]

[[1,0]
[1,0]]

[[1,1]
[0,0]]

how are they permutations of 2d array? I can only see that you created permutations of four numbers `1,1,0,0` and split each permutation into two arrays. — ysakamoto, Feb 22 '14 at 20:21
I don't see how this is a duplicate. The other question is about getting cartesian product. They both are totally different. — thefourtheye, Feb 23 '14 at 03:37
it's indeed not a duplicate of *that* one, but more a dup of http://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list-in-python?rq=1 — zmo, Feb 23 '14 at 03:43
@zmo Yup, it is closer to that one but we cannot consider that as a dup of this question, I believe. We have two lists here and the OP wants only the unique permutations. — thefourtheye, Feb 23 '14 at 03:46
well, based on that dup, and using py3, he wants this: `print (set(tuple([ ((p[0],p[1]),(p[2],p[3])) for p in itertools.permutations([1,1,0,0])])))` — zmo, Feb 23 '14 at 03:52
@zmo `print([[[i1, i2], [i3, i4]] for i1, i2, i3, i4 in set(permutations(chain.from_iterable(data)))])` — thefourtheye, Feb 23 '14 at 03:54
(as promised, voting as dup of [that one](http://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list-in-python) :-) ), though [that one](http://stackoverflow.com/questions/13408213/code-for-generating-all-unique-permutations-recursively) is a nice dup as well. Maybe should we work a community wiki on permutations? — zmo, Feb 24 '14 at 01:10

score 2 · Accepted Answer · answered Feb 23 '14 at 04:12

You can do it like this

d = [[1, 1], [0, 0]]
from itertools import permutations, chain
from pprint import pprint
pprint(sorted([i[:2], i[2:]] for i in set(permutations(chain.from_iterable(d)))))

Output

[[[0, 0], [1, 1]],
 [[0, 1], [0, 1]],
 [[0, 1], [1, 0]],
 [[1, 0], [0, 1]],
 [[1, 0], [1, 0]],
 [[1, 1], [0, 0]]]

score 1 · Answer 2 · answered Feb 22 '14 at 20:24

Is this the approximate size of your array? If it's huge, this solution will be mightily slow, but will work eventually. For arrays of this size, python's built in itertools are the way to go, plus some numpy manipulation.

Additionally, the number of unique permutations depends on the number of elements in your initial array that are different. So flattening the array, producing all the permutations, reshaping into 2x2 (or your desired size), and comparing will get you the "unique" arrays, as you seem to mean it.

I've used loops here (rather than comprehensions) to make things easy to read/test/check. Definitely translate to comprehensions (faster, all around better) before you use for real.

a = np.array([[1,1],[0,0]]).flatten()
permutes = []
for i in permutations(a):
    permutes.append((np.array(i).reshape((2,2))))

unique_permutes = [permutes[0]]
for i in permutes[1:]:
    one_equal = False
    for unique in unique_permutes:
        if np.array_equal(i, unique):
            one_equal = True
            break
    if not one_equal:
        unique_permutes.append(i)

print len(unique_permutes) #same as what you wanted
for i in unique_permutes: #prints pretilly for sanity checking
    print i

Would be nicer to use list-comprehensions for this instead of `append`ing to lists. — Erik Kaplun, Feb 22 '14 at 20:26
Edited- I wrote this with loops for testing/readability, etc. — Joan Smith, Feb 22 '14 at 20:28

score 1 · Answer 3 · answered Feb 22 '14 at 20:27

One -- not particularly efficient -- way to do it would be something like

from itertools import permutations, chain, islice

def uniperm_arrays(arr):
    flat = chain.from_iterable(arr)
    perms = set(permutations(flat))
    for perm in perms:
        pit = iter(perm)
        yield [list(islice(pit, len(row))) for row in arr]

which gives

>>> uu = uniperm_arrays([[1,1],[0,0]])
>>> for u in uu:
...     for row in u:
...         print(row)
...     print()
...     
[1, 0]
[1, 0]

[1, 1]
[0, 0]

[0, 0]
[1, 1]

[1, 0]
[0, 1]

[0, 1]
[1, 0]

[0, 1]
[0, 1]

Erik Kaplun · Answer 4 · 2014-02-25T13:42:54.037

EDIT this should work on 2d arrays of any dimension and shape.

Based on the idea that the permutations are really just flat number sequences structured as a 2D list:

from itertools import permutations

def tbl_perms(table):
    flat = (j for i in table for j in i)
    flat_permutations = iter(sorted(set(permutations(flat))))

    # convert back to the original structure
    while flat_permutations:
        flat_table = list(flat_permutations.next())  # because you can't pop() from tuple
        yield [[flat_table.pop(0) for _ in row] for row in table]

result = tbl_perms([[1, 1], [0, 0]])
pprint(list(result))

result = tbl_perms([[1, 1, 1], [0, 0, 0]])
pprint(list(result))

result = tbl_perms([[1, 2, 3], ['a', 'b']])
pprint(list(result))

Output:

[[[0, 0], [1, 1]], [[0, 1], [0, 1]], [[0, 1], [1, 0]], [[1, 0], [0, 1]], [[1, 0], [1, 0]], [[1, 1], [0, 0]]]
[[[0, 0, 0], [1, 1, 1]], [[0, 0, 1], [0, 1, 1]], [[0, 0, 1], [1, 0, 1]], [[0, 0, 1], [1, 1, 0]], [[0, 1, 0], [0, 1, 1]], [[0, 1, 0], [1, 0, 1]], [[0, 1, 0], [1, 1, 0]], [[0, 1, 1], [0, 0, 1]], [[0, 1, 1], [0, 1, 0]], [[0, 1, 1], [1, 0, 0]], [[1, 0, 0], [0, 1, 1]], [[1, 0, 0], [1, 0, 1]], [[1, 0, 0], [1, 1, 0]], [[1, 0, 1], [0, 0, 1]], [[1, 0, 1], [0, 1, 0]], [[1, 0, 1], [1, 0, 0]], [[1, 1, 0], [0, 0, 1]], [[1, 1, 0], [0, 1, 0]], [[1, 1, 0], [1, 0, 0]], [[1, 1, 1], [0, 0, 0]]]
[[[1, 2, 3], ['a', 'b']], [[1, 2, 3], ['b', 'a']], [[1, 2, 'a'], [3, 'b']], [[1, 2, 'a'], ['b', 3]], [[1, 2, 'b'], [3, 'a']], [[1, 2, 'b'], ['a', 3]], [[1, 3, 2], ['a', 'b']], [[1, 3, 2], ['b', 'a']], [[1, 3, 'a'], [2, 'b']], [[1, 3, 'a'], ['b', 2]], [[1, 3, 'b'], [2, 'a']], [[1, 3, 'b'], ['a', 2]], [[1, 'a', 2], [3, 'b']], [[1, 'a', 2], ['b', 3]], [[1, 'a', 3], [2, 'b']], [[1, 'a', 3], ['b', 2]], [[1, 'a', 'b'], [2, 3]], [[1, 'a', 'b'], [3, 2]], [[1, 'b', 2], [3, 'a']], [[1, 'b', 2], ['a', 3]], [[1, 'b', 3], [2, 'a']], [[1, 'b', 3], ['a', 2]], [[1, 'b', 'a'], [2, 3]], [[1, 'b', 'a'], [3, 2]], [[2, 1, 3], ['a', 'b']], [[2, 1, 3], ['b', 'a']], [[2, 1, 'a'], [3, 'b']], [[2, 1, 'a'], ['b', 3]], [[2, 1, 'b'], [3, 'a']], [[2, 1, 'b'], ['a', 3]], [[2, 3, 1], ['a', 'b']], [[2, 3, 1], ['b', 'a']], [[2, 3, 'a'], [1, 'b']], [[2, 3, 'a'], ['b', 1]], [[2, 3, 'b'], [1, 'a']], [[2, 3, 'b'], ['a', 1]], [[2, 'a', 1], [3, 'b']], [[2, 'a', 1], ['b', 3]], [[2, 'a', 3], [1, 'b']], [[2, 'a', 3], ['b', 1]], [[2, 'a', 'b'], [1, 3]], [[2, 'a', 'b'], [3, 1]], [[2, 'b', 1], [3, 'a']], [[2, 'b', 1], ['a', 3]], [[2, 'b', 3], [1, 'a']], [[2, 'b', 3], ['a', 1]], [[2, 'b', 'a'], [1, 3]], [[2, 'b', 'a'], [3, 1]], [[3, 1, 2], ['a', 'b']], [[3, 1, 2], ['b', 'a']], [[3, 1, 'a'], [2, 'b']], [[3, 1, 'a'], ['b', 2]], [[3, 1, 'b'], [2, 'a']], [[3, 1, 'b'], ['a', 2]], [[3, 2, 1], ['a', 'b']], [[3, 2, 1], ['b', 'a']], [[3, 2, 'a'], [1, 'b']], [[3, 2, 'a'], ['b', 1]], [[3, 2, 'b'], [1, 'a']], [[3, 2, 'b'], ['a', 1]], [[3, 'a', 1], [2, 'b']], [[3, 'a', 1], ['b', 2]], [[3, 'a', 2], [1, 'b']], [[3, 'a', 2], ['b', 1]], [[3, 'a', 'b'], [1, 2]], [[3, 'a', 'b'], [2, 1]], [[3, 'b', 1], [2, 'a']], [[3, 'b', 1], ['a', 2]], [[3, 'b', 2], [1, 'a']], [[3, 'b', 2], ['a', 1]], [[3, 'b', 'a'], [1, 2]], [[3, 'b', 'a'], [2, 1]], [['a', 1, 2], [3, 'b']], [['a', 1, 2], ['b', 3]], [['a', 1, 3], [2, 'b']], [['a', 1, 3], ['b', 2]], [['a', 1, 'b'], [2, 3]], [['a', 1, 'b'], [3, 2]], [['a', 2, 1], [3, 'b']], [['a', 2, 1], ['b', 3]], [['a', 2, 3], [1, 'b']], [['a', 2, 3], ['b', 1]], [['a', 2, 'b'], [1, 3]], [['a', 2, 'b'], [3, 1]], [['a', 3, 1], [2, 'b']], [['a', 3, 1], ['b', 2]], [['a', 3, 2], [1, 'b']], [['a', 3, 2], ['b', 1]], [['a', 3, 'b'], [1, 2]], [['a', 3, 'b'], [2, 1]], [['a', 'b', 1], [2, 3]], [['a', 'b', 1], [3, 2]], [['a', 'b', 2], [1, 3]], [['a', 'b', 2], [3, 1]], [['a', 'b', 3], [1, 2]], [['a', 'b', 3], [2, 1]], [['b', 1, 2], [3, 'a']], [['b', 1, 2], ['a', 3]], [['b', 1, 3], [2, 'a']], [['b', 1, 3], ['a', 2]], [['b', 1, 'a'], [2, 3]], [['b', 1, 'a'], [3, 2]], [['b', 2, 1], [3, 'a']], [['b', 2, 1], ['a', 3]], [['b', 2, 3], [1, 'a']], [['b', 2, 3], ['a', 1]], [['b', 2, 'a'], [1, 3]], [['b', 2, 'a'], [3, 1]], [['b', 3, 1], [2, 'a']], [['b', 3, 1], ['a', 2]], [['b', 3, 2], [1, 'a']], [['b', 3, 2], ['a', 1]], [['b', 3, 'a'], [1, 2]], [['b', 3, 'a'], [2, 1]], [['b', 'a', 1], [2, 3]], [['b', 'a', 1], [3, 2]], [['b', 'a', 2], [1, 3]], [['b', 'a', 2], [3, 1]], [['b', 'a', 3], [1, 2]], [['b', 'a', 3], [2, 1]]]

score 0 · Answer 5 · answered Jul 25 '19 at 08:42

At this point, this question has been up for 5 years, but I found a slightly better answer than the one given (which was quite helpful). This answer accounts for larger 2d arrays.

from itertools import permutations, chain
from pprint import pprint
d = np.array([[1, 1], [0, 0]])
pprint([np.array(i).reshape(d.shape).tolist() for i in set(permutations(chain.from_iterable(d)))])

OUTPUT:

[[[1, 1], [0, 2], [2, 0]],
 [[1, 0], [1, 0], [2, 2]],
 [[1, 0], [0, 2], [1, 2]],
 [[1, 2], [1, 0], [2, 0]],
 [[1, 0], [1, 2], [0, 2]],
 [[2, 1], [0, 2], [1, 0]],
 [[2, 1], [0, 0], [2, 1]],
 [[1, 2], [0, 2], [1, 0]],
 [[2, 0], [0, 2], [1, 1]],
 [[2, 1], [0, 1], [0, 2]],
 [[1, 1], [2, 0], [0, 2]],
 [[2, 0], [1, 0], [1, 2]],
 [[1, 0], [2, 2], [0, 1]],
 [[1, 2], [0, 1], [0, 2]],
 [[0, 2], [2, 0], [1, 1]],
 ...

Generate all unique permutations of 2d array

5 Answers5

Linked