2

我在处理SPOJ 问题 423：作业时遇到问题。

该问题要求我计算 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排列。所以我需要做的是找到一种更有效的计算方法。

到目前为止，这是我的代码。它目前所做的只是将来自标准输入的输入解析为一个名为首选项的列表列表并将其打印到标准输出。

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

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

4

3 回答 3

3

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

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

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

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

剧透警告！

这显示了为 0-1 矩阵实现 Ryser 公式的相对简单的方法。行被视为普通整数，索引子集也被视为普通整数。可以添加许多微优化（例如，如果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))
于 2013-10-20T02:31:26.453 回答
2

这是一个简单的实现（使用第二个示例矩阵）：

>>> M = [[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]]
>>> L = len(M)
>>> M = [[k for k in xrange(L) if l[k] == 1] for l in M] # Gets the indices of '1's

>>> def count_assignment(taken,row):
       if row >= L: return 1
       c = 0
       for e in M[row]:
          if e not in taken: c = c + count_assignment(taken + [e], row + 1)
       return c

>>> count_assignment([], 0)
7588
于 2013-10-20T02:56:53.217 回答
1

问题是计算图中最大二分匹配的总数。

以下来自维基百科文章的摘录可能会有所帮助

图中的匹配数称为图的 Hosoya 指数。计算这个数量是#P-complete。它仍然存在

P-complete 在计算给定二分图中完美匹配数的特殊情况下，因为计算永久

任意0-1矩阵（另一个#P-完全问题）的计算与计算以给定矩阵作为其邻接矩阵的二分图中的完美匹配数相同。然而，存在一个完全多项式时间随机近似方案来计算二分匹配的数量。 [10] Kasteleyn 的一个显着定理指出，平面图中完美匹配的数量可以通过 FKT 算法在多项式时间内精确计算。

完全图 Kn（n 偶数）中完美匹配的数量由双阶乘 (n − 1) 给出！！。 [11] 完整图中的匹配数，不限制匹配是完美的，由电话号码给出。 [12]

于 2013-10-20T02:35:23.333 回答