一组学生可以用多少种方式坐成一排，同一班级的学生必须交替就座

Question

有来自N班级的M学生，A[i]是来自class_i，sum(A[i]) == M的学生人数。所有这些学生都将与M座位排成一排，同一班级没有两个学生坐在一起。

这些M学生可以通过多少种有效的方式排成一排就座？

例如，如果N= 2，A= {1，2}，则输出应为2；

如果N= 2，A= {1，3}，则输出应为0；

如果N= 3，A= {1，2，3}，则输出应为120。

技术规格:n< 47；Ai < 47；sum(A) < 447；

如果输出大于1000000007，则输出(结果% 1000000007)。

Answer 1

这个解决方案可能不是最优的，但我认为这是一个很好的开始。

这个问题有两个组成部分：

学生座位标签(X ways)

• Assigning a

• to a (Y

1. )

)

最终答案等于X*Y。

第二部分非常简单。Y= A(1)!A(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)

Answer 2

考虑下面的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和get_id的基本memoization方案就开始崩溃了。要查看这一点，请查看进度

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

有人愿意改进一下吗？

Answer 3

首先请注意，给定输入列表A的有效座位排列，例如sum(A)=n，当新的大小为m的类别到达时，很容易计算有效座位排列的数量：

• 适合m新学生在所有可能的n+1有效位置(有n老学生，这意味着n+1有效位置)。这是组合的确切定义，并且有C(n+1,m)这样的组合。然后，
• 对m新学生进行置换，以获得所有可能的有效座位安排。

因此，新的尺寸m的到来使有效座位安排的数量乘以C(n+1,m) * m!。这建议使用以下算法(在Python中)：

import math
import scipy.misc

def f(A) :
    if len(A) == 2 :
        a,b = A
        if a == b  : 
        # two solutions o+o+ and +o+o without order consideration, then multiply by 2! * 2! to get all possible orders within classes
            return math.factorial(a) * math.factorial(b) * 2 
        elif abs( a - b ) == 1 : 
        # o+o+o without order consideration, then multiply by 2! * 3! to get all possible orders within classes
            return math.factorial(a) * math.factorial(b)
        else : # no solution
            return 0
    else : # the number of valid arrangement is multiplied by C(n+1,m) * m!
        return sum( f(A[:i]+A[i+1:]) * scipy.misc.comb( sum(A)-ai + 1, ai ) * math.factorial(ai) for i, ai in enumerate(A) )

让我们检查一下，我们得到的结果是否与OP的示例相同：

f( [ 1,2 ] )
2

f( [ 1,3 ] )
0

f( [ 1, 2, 3 ] )
120.0

它起作用了!让我们以三个班级为例，每班30名学生：

f( [ 30, 30, 30 ] )
2.6058794190003256e+115 # this is greater than the number of baryons in the universe!