Python 中的排列，每个位置都有不同的选项

Question

我正在尝试为类似数独的谜题编写求解器，有时我想找到一行的所有可能组合。一行必须包含从 1 到 6 的数字，且不得重复。一般来说，会有6个！ = 一行有 720 种组合。但是因为我已经缩小了我的选择范围，可能的选择列表看起来像这样：

行 = [[1, 2, 3, 4], [1, 2, 3], [1, 2, 3, 6], [1, 2, 4], [1, 3, 4, 5, 6 ], [2, 3, 4, 5]]

或者像这样，已经找到一些数字：

行 = [[1, 2, 3], [1, 2, 3], 5, 6, [1, 3, 4], [2, 3, 4]]

我想出的解决方案涉及使用 itertools product 函数来获取所有可能的重复项组合，然后筛选结果列表以删除所有重复项的选项：

from itertools import product

def get_permutations(row):
    # this line is needed to turn ints (digits that are already found)
    # into sets with the length of 1:
    row = [s.copy() if isinstance(s, set) else {s} for s in row]

    # this is where we get all possible permutations with duplicates:
    prod = product(*row)
    # in this example, we have 2880 permutations with duplicates

    without_duplicates = [value for value in prod if len(value) == len(set(value))]
    # without duplicates, there's only 32 variations
    return without_duplicates

r = [{1, 2, 3, 4}, {1, 2, 3}, {1, 2, 3, 6}, {1, 2, 4}, {1, 3, 4, 5, 6}, {2, 3, 4, 5}]
perm = get_permutations(r)

这种方法的问题是我们创建了数千个排列只是为了将它们缩小到几十个。它对于 6x6 的拼图效果相对较好，但对于更大的拼图来说效率太低，其中数千会变成数百万。所以也许有一种方法可以不在我们的列表中包含重复项。

Answer 1

如果你增量地建立你的笛卡尔积，你可以在它们呈指数增长之前去掉重复的条目。这是一个代码片段，正是这样做的：

from itertools import product
from collections.abc import Iterable

def uniq_prod(sets):
    result = [(x,) for x in next(sets)]
    
    for selection in sets:
        result = [tup + (x,) for tup in result for x in selection.difference(tup)]
        
    return result

def get_perms_fast(row):
    return uniq_prod(set(s) if isinstance(s, Iterable) else {s} for s in row)

在您的示例输入上运行它：

>>> row = [{1, 2, 3, 4}, {1, 2, 3}, {1, 2, 3, 6}, {1, 2, 4}, {1, 3, 4, 5, 6}, {2, 3, 4, 5}]
>>> print(get_perms_fast(row))
[(1, 2, 3, 4, 6, 5), (1, 2, 6, 4, 3, 5), (1, 2, 6, 4, 5, 3), (1, 3, 2, 4, 6, 5), (1, 3, 6, 2, 4, 5), (1, 3, 6, 2, 5, 4), (1, 3, 6, 4, 5, 2), (2, 1, 3, 4, 6, 5), (2, 1, 6, 4, 3, 5), (2, 1, 6, 4, 5, 3), (2, 3, 1, 4, 6, 5), (2, 3, 6, 1, 4, 5), (2, 3, 6, 1, 5, 4), (2, 3, 6, 4, 1, 5), (3, 1, 2, 4, 6, 5), (3, 1, 6, 2, 4, 5), (3, 1, 6, 2, 5, 4), (3, 1, 6, 4, 5, 2), (3, 2, 1, 4, 6, 5), (3, 2, 6, 1, 4, 5), (3, 2, 6, 1, 5, 4), (3, 2, 6, 4, 1, 5), (4, 1, 3, 2, 6, 5), (4, 1, 6, 2, 3, 5), (4, 1, 6, 2, 5, 3), (4, 2, 3, 1, 6, 5), (4, 2, 6, 1, 3, 5), (4, 2, 6, 1, 5, 3), (4, 3, 1, 2, 6, 5), (4, 3, 2, 1, 6, 5), (4, 3, 6, 1, 5, 2), (4, 3, 6, 2, 1, 5)]