Na ile sposobów można grupa studentów siedzące w rzędzie, uczniowie z tej samej klasy muszą przełączać

Question

Istnieje M studenci z N klas A[i] jest liczba studentów z class_i, sum(A[i]) == M. Wszyscy uczniowie będą siedzieć z rzędu z miejscami siedzącymi M, a nie ma 2 uczniów z tej samej klasy siedzących obok siebie.

Jak wielu ważnych sposobów może te osoby M siedzieć z rzędu?

Na przykład: , jeśli N = 2, A = {1, 2}, wynik powinien wynosić 2;

jeśli N = 2, A = {1, 3}, wynik powinien wynosić 0;

gdy n = 3, A = {1, 2, 3} dane wyjściowe powinny być 120.

Specyfikacja techniczna: N < 47; A [i] < 47; suma (A) < 447;

jeśli wynik jest większy niż 1000000007, niż wynik (wynik% 1000000007).

Answer 1

To rozwiązanie może nie być optymalne, ale uważam, że to dobry początek.

Istnieją dwa składniki tego problemu:

1. Oznakowanie każde miejsce w klasie (X sposoby)
2. Przypisywanie miejsce do studenta (Y sposoby)

odpowiedź końcowa jest równa się X * Y.

Część 2 jest bardzo prosta. Y = A (1)! A (2)! ... * A (N)!

Obliczanie pierwszej części jest jednak trudne. Możesz użyć DP, aby go rozwiązać. Złożoność = N * A (1) A (2) ... * (n) (który jest zbyt drogie do gustu)

problemem 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

Rozważmy następujący kod Pythona:

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 

wygląda na to, że robi się podstawowe przypadki rację:

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

Jednak podstawowy schemat zapamiętywania przy użyciu mem i get_id zaczyna kruszyć się przed wymaganiami, o których wspomniałeś.Aby to zobaczyć, obserwować postęp

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) 

który daje

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 

ostrożność, aby ktokolwiek ją poprawić?

Answer 3

pierwsze zauważyć, że podane poprawny układ siedzeń na liście wejściowej A takie, że sum(A)=n, łatwo jest obliczyć liczbę ważnych ustaleń siedzących gdy nowa klasa wielkości m przybywa:

• Zamontować m nowy studenci na wszystkich możliwych n+1 ważnych stanowiskach (jest n starych uczniów, co oznacza n+1 ważnych pozycji). Jest to dokładna definicja kombinacji i istnieją takie kombinacje.
• Następnie prześlij nowych studentów, aby uzyskać wszystkie możliwe poprawne ustawienia siedzeń.

Dlatego pojawienie się nowej klasy wielkości m pomnożył liczbę ważnych ustaleń siedzących przez C(n+1,m) * m!. To sugeruje następujący algorytm (w Pythonie):

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

Sprawdźmy, że mamy takie same wyniki jak w przykładach PO:

f([ 1,2 ]) 
2 

f([ 1,3 ]) 
0 

f([ 1, 2, 3 ]) 
120.0 

to działa! Spróbujmy z trzech klas 30 uczniów „nr 2 uczniowie z tej samej klasy siedzieć obok siebie”

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