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

Question

我在SPOJ Problem 423: Assignments上遇到问题。在

她给每个学生布置的作业都是唯一的，这样他就可以计算出每个问题的唯一数量。我想出了一种方法来将输入解析为一个名为preferences的列表列表。一个包含0和1的内部主题列表是一个整数。在

例如输入：

1 1 1
1 1 1
1 1 1

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

对于输入：

^{pr2}$

我得到了列表[[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（包括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年解决了这个问题——它仍然是世界上第十快的，但是它使用的内存比其他公认的解决方案要少得多。看看今天的代码，我不知道它在做什么-哈哈；-）

如果我没记错的话，这是一个“禁止位置排列”的例子。这是一个可以和“rook多项式”一起使用的搜索词。它可以归结为计算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))

Answer 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

Answer 3

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

以下摘录自Wikipedia article可能会有所帮助

The number of matchings in a graph is known as the Hosoya index of the graph. It is #P-complete to compute this quantity. It remains

P-complete in the special case of counting the number of perfect matchings in a given bipartite graph, because computing the permanent

of an arbitrary 0–1 matrix (another #P-complete problem) is the same as computing the number of perfect matchings in the bipartite graph having the given matrix as its biadjacency matrix. However, there exists a fully polynomial time randomized approximation scheme for counting the number of bipartite matchings.[10] A remarkable theorem of Kasteleyn states that the number of perfect matchings in a planar graph can be computed exactly in polynomial time via the FKT algorithm.

The number of perfect matchings in a complete graph Kn (with n even) is given by the double factorial (n − 1)!!.[11] The numbers of matchings in complete graphs, without constraining the matchings to be perfect, are given by the telephone numbers.[12]