python：找到一组的所有拉丁方（或列数较少的部分方）

Question

编辑：
感谢评论者 Douglas Zare，我已将此 post 的标题重命名为更适合可能正在寻找类似内容的任何其他人的术语。下面 David Eisenstat 的代码非常有用。

原版POST:
对于缺乏适当的集合论术语，我深表歉意......但我在这里有点超出了我的深度（尽管我怀疑这是一个简单的问题）。我正在尝试开发一种算法，该算法将接受一个集合、一个数字 K 和 return 所有可能的 "complete" 分区，其中 K-sized 个子集和集合 coverage=K 使得：

任何给定的子集都不会重复
将所有子集中的第 n 项组合起来给出集合的完整划分
所有子集中的第 n 个项在其余子集中是唯一的

例如：

function({A, B, C, D}, 2)

应该return所有可能的集合如下：

[AB, BC, CD, DA]
[AB, BD, CA, DC]
[AC, BD, CA, DB]
[AD, DA, CB, BC]
[BC, CA, DB, AD]
...

另外，物有所值

单个子集中的元素顺序无关紧要（只要遵守其他三个规则

所以下面是等价的：

[AB, BA, CD, DC] = [BA, AB, DC, CD] = [AB, BA, DC, CD] = [BA, AB, CD, DC]

和

各个子集的顺序重要：

所以以下是不同的：

[BC, CA, DB, AD] ≠ [CA, BC, AD, DB]

换句话说，在矩阵方面：我正在寻找具有 rows=len(set) 和 columns=K 的所有矩阵，这样每一列都有精确的覆盖，并且没有任何项目在任何行中出现超过一次。

function({A, B, C, D}, 3)

return 所有矩阵都像下面这样...

ABC      ADB    
BCD      DCA    
CDA      CBD    
DAB      BAC

我希望在 python 中得到答案，并且使用像 numpy 这样的库很好......但也将不胜感激一般的算法策略。我认为 Algorithm X 之类的东西可能会派上用场......但我一直无法从那里跳到这里概述的问题......

Answer 1

回溯搜索可行。 Python 3:

import itertools
import operator


def valid(cols_so_far):
    for i, col1 in enumerate(cols_so_far):
        for col2 in cols_so_far[i + 1:]:
            if any(map(operator.eq, col1, col2)):
                return False
    return True


def enum(letters, k, cols_so_far=None):
    if cols_so_far is None:
        cols_so_far = (tuple(letters),)
    if not valid(cols_so_far):
        pass
    elif len(cols_so_far) == k:
        yield tuple(zip(*cols_so_far))  # transpose
    else:
        for perm in itertools.permutations(letters):
            yield from enum(letters, k, cols_so_far + (perm,))

python：找到一组的所有拉丁方（或列数较少的部分方）

python: find all Latin Squares of a set (or partial square with fewer columns)

python

algorithm

permutation

combinatorics