生成二维数组的所有唯一排列

Question

我希望能够在Python中生成2D数组的所有唯一排列。 例如，以这个2D数组为例 [[1,1],[0,0]] 我希望得到以下结果

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

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

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

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

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

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

- patrick_corrigan

---

它们如何成为2D数组的排列？我只能看到您创建了四个数字“1,1,0,0”的排列，并将每个排列拆分成两个数组。 - ysakamoto

我不认为这是一个重复的问题。另一个问题是关于获取笛卡尔积的。它们完全不同。 - thefourtheye

@zmo 是的，它更接近那个问题，但我认为我们不能将其视为此问题的重复。 在这里我们有两个列表，操作员只想要唯一的排列。 - thefourtheye

好的，基于那个dup，并使用py3，他想要这样做：print (set(tuple([ ((p[0],p[1]),(p[2],p[3])) for p in itertools.permutations([1,1,0,0])]))) - zmo

（如承诺，将其作为此问题的重复投票 :-)），虽然那个也是一个不错的重复。也许我们应该在排列上共同编写一个社区wiki？ - zmo

Answer 1

你可以按照以下方式操作。

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

输出

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

- thefourtheye

Answer 2

这是你的数组的大致大小吗？如果很大，这种解决方案将会非常慢，但最终会起作用。对于这种大小的数组，Python内置的itertools是正确的选择，再加上一些numpy操作。

此外，唯一排列的数量取决于初始数组中不同元素的数量。因此，将数组展平，生成所有排列，重新调整为2x2（或所需大小），然后进行比较，就可以得到“唯一”的数组，正如你所理解的那样。

我在这里使用了循环（而不是理解）来使事情易于阅读/测试/检查。在实际使用之前，一定要转换为理解（更快，全面更好）。

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

- Joan Smith

---

最好使用列表推导式来代替向列表中添加元素。 - Erik Kaplun

编辑：我使用循环进行测试/可读性等。 - Joan Smith

Answer 3

有一种不太高效的方法可以实现，大概是这样的

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]

这提供了

>>> 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]

- DSM

Answer 4

编辑：这应该适用于任何维度和形状的二维数组。

基于这样一个想法，排列实际上只是结构化为2D列表的平面数字序列：

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

输出：

[[[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]]]

- Erik Kaplun

Answer 5

目前为止，这个问题已经存在了5年，但我找到了一个比之前给出的答案稍微好一点的答案（之前的答案非常有帮助）。这个答案考虑了更大的二维数组。

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)))])

输出：

[[[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]],
 ...

- Ryan Callihan