Geek asks and answers

In how many students can a group of students pass in a row, students of the same class must alternate

There are students Mof classes N, A[i]- the number of students class_i, sum(A[i]) == M. All these students will sit next to the Mseats, and 2 students from the same class are sitting next to each other.

How many acceptable ways can these students Msit in a row?

For example, if N = 2, A = {1, 2}, the output should be 2;

if N = 2, A = {1, 3}, the output should be 0;

if N = 3, A = {1, 2, 3}, the output should be 120.

Technical specification: N <47; A [i] 47; sum (A) 447;

if the output is greater than 1000000007 than the output (result% 1000000007).

+5
source share
3 answers

, , .

:

  • (X )
  • ( Y)

X * Y.

2 . 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,.., -1, last_letter!= 1)

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

memoization mem 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

- ?

0

, A, , sum(A)=n, , m:

  • m n+1 ( n , n+1 ). , .
  • m, .

Therefore, the arrival of a new size class mmultiplied the number of valid seats by C(n+1,m) * m!. This offers the following algorithm (in 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) )

Check that we get the same results as the OP examples:

f( [ 1,2 ] )
2

f( [ 1,3 ] )
0

f( [ 1, 2, 3 ] )
120.0

It works! Try three classes of 30 students:

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

More articles:


All Articles