python - 计算从列表列表中选择唯一元素的方法数

Question

我在使用 SPOJ Problem 423: Assignments 时遇到了问题.

该问题要求我计算 n 个不同主题的可能分配给 n 个不同学生的数量，以便每个学生都能得到他/她喜欢的一个主题。我想出了一种方法来将输入解析为名为 preferences 的列表列表。每个内部列表是一个学生喜欢的主题列表(用 0 到 n-1 之间的整数表示)。

例如输入:

1 1 1
1 1 1
1 1 1

我得到 [[0, 1, 2], [0, 1, 2], [0, 1, 2]]。

对于输入:

1 0 0 1 0 0 0 0 0 1 1 
1 1 1 1 1 0 1 0 1 0 0 
1 0 0 1 0 0 1 1 0 1 0 
1 0 1 1 1 0 1 1 0 1 1 
0 1 1 1 0 1 0 0 1 1 1 
1 1 1 0 0 1 0 0 0 0 0 
0 0 0 0 1 0 1 0 0 0 1 
1 0 1 1 0 0 0 0 0 0 1 
0 0 1 0 1 1 0 0 0 1 1 
1 1 1 0 0 0 1 0 1 0 1 
1 0 0 0 1 1 1 1 0 0 0

我得到列表 [[0, 3, 9, 10], [0, 1, 2, 3, 4, 6, 8], [0, 3, 6, 7, 9], [ 0, 2, 3, 4, 6, 7, 9, 10], [1, 2, 3, 5, 8, 9, 10], [0, 1, 2, 5], [4, 6, 10] , [0, 2, 3, 10], [2, 4, 5, 9, 10], [0, 1, 2, 6, 8, 10], [0, 4, 5, 6, 7]].

现在我需要做的是计算我可以从每个内部列表中选择一个唯一数字的方式的数量，以便没有元素被选择两次，并且 0 和 n-1 之间的每个数字在所有选择中恰好被选择一次。对于第一个示例输入，这是微不足道的，它是 3! = 6。但是在第二个例子中，我很难想出一种方法来计算有效选择的数量。对于第二个输入，他们给出的答案是 7588，但我不知道如何得出这个答案。

我已经尝试了查找 [0,...,n-1] 的所有排列并尝试查看它们是否是基于集合成员的有效组合的蛮力方法，但它太慢了，它确实让我崩溃了当我尝试遍历 11! = 39916800 排列。所以我需要做的是找到一种更有效的计数方法。

到目前为止，这是我的代码。它目前所做的只是将来自 stdin 的输入解析为一个名为 preferences 的列表列表，并将其打印到 stdout。

def main():
    t = int(raw_input())
    from itertools import repeat
    for _ in repeat(None, t):
        n = int(raw_input())
        preferences = [[] for _ in repeat(None, n)]
        for student in xrange(n):
            row = map(int, raw_input().split())
            for i in xrange(len(row)):
                if row[i] == 1:
                    preferences[student].append(i)
        print preferences


if __name__ == '__main__':
    main()

有什么方法可以有效地计算它吗？欢迎任何提示/提示。我不指望任何人为我解决问题。我只是对应该如何处理这个问题感到困惑。

Answer 1

我看到我在 2005 年解决了那个问题 - 它仍然是那里第 10 快的，但使用的内存比其他公认的解决方案少得多。今天看代码，我不知道它在做什么 - LOL ;-)

如果我没记错的话，这是一个“禁止位置排列”的例子。这是您可以使用的搜索词，连同“车多项式”。它归结为计算 0-1 矩阵的“永久”(另一个搜索词)，这是一项计算量大的任务。这就是为什么您在 SPOJ 上看不到针对此问题的公认 Python 解决方案(我用 C 语言编写了我的解决方案)。

所以，那里没有答案，但有很多东西需要研究 ;-) 获得一个被接受的程序更多的是学习数学而不是聪明的编程。

一个提示:在我的笔记中，我看到我通过包含全 1 的特殊外壳输入矩阵节省了大量的运行时间。在这种情况下，结果只是 N 的阶乘(对于 N×N 输入)。祝你好运:-)

剧透警告!

这显示了一种相对简单的方法来实现 Ryser 的 0-1 矩阵公式。行被视为普通整数，索引子集也被视为普通整数。可以添加许多微优化(例如，如果 prod 变为 0，则提前跳出循环；如果矩阵完全为 1，则返回 math.factorial(n) ; 等)。

_pc = []
for i in range(256):
    c = 0
    while i:
        # clear last set bit
        i &= i-1
        c += 1
    _pc.append(c)

def popcount(i):
    "Return number of bits set."
    result = 0
    while i:
        result += _pc[i & 0xff]
        i >>= 8
    return result

def perm(a):
    "Return permanent of 0-1 matrix.  Each row is an int."
    result = 0
    n = len(a)
    for s in range(1 << n):
        prod = 1
        for row in a:
            prod *= popcount(row & s)
        if popcount(s) & 1:
            result -= prod
        else:
            result += prod
    if n & 1:
        result = -result
    return result

def matrix2ints(a):
    return [int("".join(map(str, row)), 2)
            for row in a]

def matrix_perm(a):
    "Return permanent of 0-1 matrix."
    return perm(matrix2ints(a))