Có bao nhiêu cách có thể một nhóm sinh viên được ngồi trong một hàng, các sinh viên đến từ cùng lớp phải luân phiên

Question

Có M sinh viên đến từ N lớp, A[i] là số lượng sinh viên từ class_i, sum(A[i]) == M. Tất cả các học sinh này sẽ ngồi liên tiếp với M chỗ ngồi, và không có 2 học sinh từ cùng một lớp ngồi cạnh nhau.

Có bao nhiêu cách hợp lệ để các học sinh này có thể ngồi trong một hàng?

Ví dụ: nếu N = 2, A = {1, 2}, đầu ra phải là 2;

nếu N = 2, A = {1, 3}, đầu ra phải bằng 0;

nếu N = 3, A = {1, 2, 3}, sản lượng nên được 120.

Thông số kỹ thuật: N < 47; A [i] < 47; tổng (A) < 447;

nếu đầu ra lớn hơn 1000000007, so với đầu ra (kết quả% 1000000007).

Answer 1

Giải pháp này có thể không tối ưu, nhưng tôi nghĩ đó là một khởi đầu tốt.

Có hai thành phần cho vấn đề này:

1. Ghi nhãn mỗi ghế để một lớp (cách X)
2. Gán một chỗ ngồi cho học sinh (Y cách)

câu trả lời cuối cùng là bằng X * Y.

Phần 2 rất dễ dàng. Y = A (1)! A (2)! ... * A (N)!

Tính toán phần đầu tiên là khó khăn. Bạn có thể sử dụng DP để giải quyết nó. Phức tạp = N * A (1) A (2) ... * A (N) (đó là quá đắt đối với hương vị của tôi)

DP vấn đề là:

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

xem xét mã python sau:

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 

Dường như nó được các trường hợp cơ bản đúng:

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

Tuy nhiên, lược đồ ghi nhớ cơ bản bằng cách sử dụng mem và get_id bắt đầu sụp đổ trước các yêu cầu bạn đề cập.Để thấy điều này, xem sự tiến triển

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) 

trong đó sản lượng

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 

chăm sóc Bất cứ ai cũng để cải thiện nó?

Answer 3

thông báo đầu tiên mà đưa ra một sắp xếp chỗ ngồi có giá trị trong danh sách đầu vào A mà sum(A)=n, nó rất dễ dàng để tính toán số lượng sắp xếp chỗ ngồi hợp lệ khi một lớp mới có kích thước m đến:

• Fit các m mới học sinh ở tất cả các vị trí có thể n+1 hợp lệ (có n học sinh cũ, có nghĩa là n+1 vị trí hợp lệ). Đây là định nghĩa kết hợp chính xác và có C(n+1,m) kết hợp như vậy.
• Sau đó, hãy cho phép sinh viên mới m nhận tất cả các sắp xếp chỗ ngồi hợp lệ có thể có.

Do đó, sự xuất hiện của lớp học mới có kích thước m đã nhân số lượng chỗ ngồi hợp lệ theo số C(n+1,m) * m!. Điều này cho thấy các thuật toán sau (bằng 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)) 

Hãy kiểm tra xem chúng tôi nhận được kết quả tương tự như ví dụ của OP:

f([ 1,2 ]) 
2 

f([ 1,3 ]) 
0 

f([ 1, 2, 3 ]) 
120.0 

Nó hoạt động! Hãy thử với ba lớp học của 30 học sinh: "không có 2 học sinh từ lớp cùng ngồi cạnh nhau"

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