5

のクラスのM生徒がいます。の生徒数はです。これらの生徒はすべて一列に並んで座り、同じクラスの生徒が 2 人隣り合うことはありません。NA[i]class_isum(A[i]) == MM

Mこれらの生徒が一列に並んで座ることができる有効な方法はいくつありますか?

たとえば、N = 2、A = {1, 2} の場合、出力は 2 になります。

N = 2、A = {1, 3} の場合、出力は 0 になります。

N = 3、A = {1, 2, 3} の場合、出力は 120 になります。

技術仕様: N < 47; A[i] < 47; 合計 (A) < 447;

出力が 1000000007 より大きい場合は、出力 (結果 % 1000000007) よりも大きくなります。

4

3 に答える 3

0

次の Python コードを検討してください。

import math

mem={}

def get_id(A, forbidden):
    count = {}
    for a in A:
        if a<>forbidden:
            n = A[a]
            count[n] = count.get(n,0)+1
    return frozenset( [A.get(forbidden, 0)] + count.items() )

def class_seatings(A, forbidden=None):
    if sum(A.values())==1:
        if forbidden in A:
            return 0
        else:
            return 1
    ssum = 0
    for a in A:
        if a <> forbidden:
            n = A[a]
            A2 = dict(A) 
            if n==1:
                del A2[a]
            else:
                A2[a] -= 1
            id = get_id(A2, a)
            if id not in mem:
                mem[id] = class_seatings(A2, a)
            cs = mem[id]
            ssum += cs
    return ssum

def student_seatings(A):
    assert all(map(lambda x: x>0, A.values()))
    facts = map(lambda x: math.factorial(x), A.values())
    mult = reduce(lambda x,y: x*y, facts, 1)
    return mult*class_seatings(A) % 1000000007

基本的なケースを正しく取得しているようです：

>>> student_seatings( {1:1, 2:2} )
2
>>> student_seatings( {1:1, 2:2, 3:3} )
120
>>> student_seatings( {1:1, 2:3} )
0
>>> student_seatings( {1:2, 2:2} )
8

memただし、 andを使用した基本的なメモ化スキームget_idは、あなたが言及する要件の前に崩壊し始めます。これを確認するには、進行状況を見てください

mem={}
for upper in range(2,11):
    A = dict( (x,x) for x in range(1,upper) )   
    print len(A), student_seatings(A)
    print len(mem)

利回り

1 1
0
2 2
4
3 120
20
4 309312
83
5 579005048
329
6 462179000
1286
7 481882817
5004
8 678263090
19447
9 992777307
75581

誰かがそれを改善したいですか？

于 2013-08-06T00:54:49.053 に答える
0

この解決策は最適ではないかもしれませんが、良いスタートだと思います。

この問題には 2 つの要素があります。

  1. クラスごとに各座席にラベルを付ける (X 方法)
  2. 生徒に席を割り当てる (Y 方法)

最終的な答えは X*Y に等しくなります。

パート 2 は非常に簡単です。Y = A(1)! あ(2)！...*A(N)!

ただし、最初の部分を計算するのは難しいです。DP を使用して解決できます。複雑さ = N*A(1) A(2) ...*A(N) (これは私の好みには高すぎます)

DPの問題は次のとおりです。

F(a1、a2、..、an、last_letter=1) = F(a1-1、a2、..、an、last_letter!=1)+F(a1、a2-1、..、an、last_letter! =1)+...+F(a1,a2,..,an-1,last_letter!=1)

于 2013-03-29T16:15:17.433 に答える