2

SPOJ Problem 423: Assignmentsに問題があります。

この問題では、n 個の固有のトピックを n 個の固有の生徒に割り当てることができる割り当ての数を数えて、各生徒が好きなトピックを 1 つだけ取得できるようにすることを求めています。入力を と呼ばれるリストのリストに解析する方法を思いつきましたpreferences。各内部リストは、1 人の生徒が好きなトピック (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]]。

今私がする必要があるのは、各内部リストから一意の番号を選択できる方法の数を数えることです。これにより、要素が 2 回選択されず、0 から n-1 までの各番号がすべての選択の中で 1 回だけ選択されます。最初の入力例では、これは自明3! = 6です。しかし、2 番目の例では、有効な選択の数を数える方法がわかりません。彼らは2番目の入力に対して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 番目に高速ですが、他の受け入れられている解決策よりもはるかに少ないメモリを使用します。今日のコードを見ると、それが何をしているのかわかりません - 笑 ;-)

私の記憶が正しければ、これは「禁止された位置の順列」の例です。これは、「ルーク多項式」とともに使用できる検索用語です。要約すると、0-1 行列の「永続的」(別の検索用語) を計算することになりますが、これは計算コストの高いタスクです。そのため、SPOJ でこの問題に対する受け入れられた Python ソリューションが表示されません (私は C で記述しました)。

ですから、そこには答えはありませんが、調査すべきことがたくさんあります ;-) このプログラムで受け入れられるプログラムを取得するには、巧妙なプログラミングよりも数学を勉強することが重要です。

1 つのヒント: 私のノートでは、すべて 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))
于 2013-10-20T02:31:26.453 に答える
2

これは素朴な実装です（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 に答える