Magiczna sekwencja to sekwencja liczb całkowitych nieujemnych, x[0..n-1]tak że istnieją dokładnie takie x[i]przypadkii

Na przykład 6,2,1,0,0,0,1,0,0,0 to magiczna sekwencja, ponieważ jest 6 0, 2 1 i tak dalej.

Napisz funkcję, która gdy otrzyma n, wyświetla wszystkie magiczne sekwencje o długości n

Wygrywa program, który może wygenerować poprawny wynik dla najwyższej wartości n w ciągu 10 sekund. (Wszystkie programy są mile widziane)

Na przykład program Alice może poradzić sobie z wartością do n = 15 w ciągu 10 sekund, podczas gdy program Boba może poradzić sobie z wartością do n = 20 w tym samym czasie. Bob wygrywa.

Platforma: Linux 2.7GHz @ 4 procesory

Python, nr ^{10 8}

def magic_sequences(n):
    if n==4:
        return (1, 2, 1, 0),(2, 0, 2, 0) 
    elif n==5:
        return (2, 1, 2, 0, 0),
    elif n>=7:
        return (n-4,2,1)+(0,)*(n-7)+(1,0,0,0),
    else:
        return ()

Wykorzystuje to fakt, który udowodnię, że jedynymi magicznymi sekwencjami długości nsą:

• [1, 2, 1, 0]i [2, 0, 2, 0]dlan=4
• [2, 1, 2, 0, 0] dla n=5
• [n-4, 2, 1, 0, 0, ..., 0, 0, 1, 0, 0, 0] dla n>=7

Tak więc, n>=7wystarczy zwrócić ogromną krotkę. Mogę to zrobić w przybliżeniu n=10^8na moim laptopie, co prawdopodobnie jest ograniczone pamięcią; i już się zawiesza. (Dzięki trichoplax za pomysł użycia krotek zamiast list.) Lub, jeśli zamiast tego można wydrukować słownik niezerowych wpisów, {0:n-4, 1:2, 2:1, (n-4):1}można to zrobić dla ginormous n.

Udowadniam wyjątkowość n>=7; pozostałe można sprawdzić za pomocą brutalnej siły lub pracy w skrzynce.

Suma wpisów lto łączna liczba wszystkich liczb na liście, czyli jej długość n. Lista ma l[0]zera, a więc n-l[0]niezerowe wpisy. Ale z definicji l[0]musi być niezerowa lub otrzymujemy sprzeczność, a każdy z niezerowych wpisów ma co najmniej 1. To już stanowi sumę z l[0] + (n-l[0]-1)*1 = n-1ogólnej sumy n. Więc nie licząc l[0], może być najwyżej jeden 2 i żaden wpis większy niż 2.

Ale to oznacza, że ​​jedynymi niezerowymi wpisami są l[0], l[1], l[2], and l[l[0]], których wartości są co najwyżej, l[0]i permutacja 1,1,2, co daje maksymalną sumę l[0]+4. Ponieważ ta suma wynosi nco najmniej 7, mamy l[0]>=3i tak l[l[0]]=1. Teraz jest co najmniej jeden 1, co oznacza l[1]>=1, ale jeśli l[1]==1to inny 1, to l[1]>=2znaczy, że l[1]jest samotny 2. To daje l[2]=1, a wszystkie pozostałe wpisy są 0, więc l[0]=n-4, co uzupełnia rozwiązanie.

Python 3, nr 40

def plausible_suffix(l,N):
    if sum(l)>N:
        return False

    pairs = [(N-1-i,l[i]) for i in range(len(l))]

    if sum(i*x for i,x in pairs)>N:
        return False

    num_remaining = N - len(l)

    for index, desired_count in pairs:
        count = l.count(index)
        more_needed = desired_count - count
        if more_needed<0: 
            return False
        num_remaining -= more_needed
        if num_remaining<0:
            return False
    return True

plausible_func = plausible_suffix

def generate_magic(N):
    l=[0]
    while l:
        extend = False
        if plausible_func(l,N):
            if len(l)==N:
                yield l[::-1]
            else:
                extend = True
        if extend:
            l.append(0)
        else:
            while l[-1]>=N-2:
                l.pop(-1)
                if not l:raise StopIteration
            l[-1]+=1

n=40 #test parameter

if n>0:
    for x in generate_magic(n):
        print(n,x)

Wykonuje pierwsze wyszukiwanie możliwych list, wypełniając wpisy od prawej do lewej, zatrzymując wyszukiwanie z sufiksem, jeśli nie jest prawdopodobne, co może się zdarzyć, jeśli:

• Suma wpisów w sufiksie przekracza n(suma dla całej listy musi być n)
• Suma ważona i*l[i]przyrostka przekracza n(suma dla całej listy musi być n)
• Dowolna liczba pojawia się w sufiksie więcej razy niż przyrostek mówi, że powinien
• Liczba pozostałych niewypełnionych miejsc jest zbyt mała, aby uwzględnić wszystkie liczby, które muszą pojawić się więcej razy.

Miałem oryginalne przetestowane prefiksy od lewej do prawej, ale poszło to wolniej.

Wyjścia do n=30to:

4 [1, 2, 1, 0]
4 [2, 0, 2, 0]
5 [2, 1, 2, 0, 0]
7 [3, 2, 1, 1, 0, 0, 0]
8 [4, 2, 1, 0, 1, 0, 0, 0]
9 [5, 2, 1, 0, 0, 1, 0, 0, 0]
10 [6, 2, 1, 0, 0, 0, 1, 0, 0, 0]
11 [7, 2, 1, 0, 0, 0, 0, 1, 0, 0, 0]
12 [8, 2, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0]
13 [9, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
14 [10, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
15 [11, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
16 [12, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
17 [13, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
18 [14, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
19 [15, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
20 [16, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
21 [17, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
22 [18, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
23 [19, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
24 [20, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
25 [21, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
26 [22, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
27 [23, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
28 [24, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
29 [25, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
30 [26, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]

Z wyjątkiem pierwszych trzech list [1, 2, 1, 0], [2, 0, 2, 0], [2, 1, 2, 0, 0]istnieje dokładnie jedna lista każdej długości n>6i ma ona formę [n-4, 2, 1, ..., 0, 0, 1, 0, 0, 0]. Ten wzór utrzymuje się co najmniej n=50. Podejrzewam, że zachowuje się wiecznie, w takim przypadku generowanie ogromnej liczby z nich jest banalne. Nawet jeśli nie, matematyczne zrozumienie możliwych rozwiązań znacznie przyspieszy wyszukiwanie.

Pyth - 15 bajtów

Używa brutalnej siły we wszystkich możliwych sekwencjach len, na następnie filtruje.

f.A.eq/TkYT^UQQ

Pełne wyjaśnienie już wkrótce.

Wypróbuj tutaj online .

K, 26 bajtów

{f@&{x~(+/x=)'!#x}'f:!x#x}

Podobnie jak podejście Maltysena, brutalna siła. Sercem programu jest predykat, który sprawdza, czy dany wektor jest „magiczny”:

{x~(+/x=)'!#x}

Zbuduj wektor jota tak długo, jak wektor wejściowy ( !#x), policz wystąpienia każdej cyfry ( (+/x=)') i porównaj wynik z wektorem wejściowym ( x~). Jeśli jest dopasowanie, masz magiczną sekwencję.

Niestety, ten pierwszy dźgnięcie wydaje się być dość powolny. Testowanie przy użyciu Kona na moim laptopie zajmuje około 12 sekund, aby obsłużyć n = 7. Muszę to przemyśleć.