Eine magische Folge ist eine Folge von nicht negativen ganzen Zahlen, x[0..n-1]so dass es genau x[i]Instanzen von gibti

Zum Beispiel ist 6,2,1,0,0,0,1,0,0,0 eine magische Sequenz, da es 6 Nullen, 2 Einsen usw. gibt.

Schreiben Sie eine Funktion, die bei n alle magischen Folgen der Länge n ausgibt

Das Programm, das innerhalb von 10 Sekunden die richtige Ausgabe für den höchsten Wert von n erzeugen kann, gewinnt. (Alle Programme sind jedoch willkommen)

Zum Beispiel kann Alices Programm innerhalb von 10 Sekunden bis zu n = 15 verarbeiten, während Bobs innerhalb derselben Zeit bis zu n = 20 verarbeiten kann. Bob gewinnt.

Plattform: Linux 2.7GHz @ 4 CPUs

Python, n≈10 ⁸

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

Dies nutzt die Tatsache, die ich beweisen werde, dass die einzigen Magic-Sequenzen der Länge nsind:

• [1, 2, 1, 0]und [2, 0, 2, 0]fürn=4
• [2, 1, 2, 0, 0] zum n=5
• [n-4, 2, 1, 0, 0, ..., 0, 0, 1, 0, 0, 0] zum n>=7

Also, für n>=7, braucht man nur eine riesige Tupel zurück. Ich kann dies bis zu ungefähr n=10^8auf meinem Laptop tun , was wahrscheinlich durch den Speicher begrenzt ist. nicht mehr und es friert ein. (Dank an trichoplax für die Idee, Tupel anstelle von Listen zu verwenden.) Oder wenn man stattdessen ein Wörterbuch mit Einträgen ungleich Null drucken {0:n-4, 1:2, 2:1, (n-4):1}kann, kann man dies für ginormous tun n.

Ich beweise die Einzigartigkeit für n>=7; Die anderen können durch rohe Gewalt oder Fallarbeit überprüft werden.

Die Summe der Einträge von list die Gesamtzahl aller Nummern der Liste, dh deren Länge n. Die Liste enthält l[0]Nullen und daher n-l[0]Einträge ungleich Null. Aber per Definition l[0]muss ungleich Null sein, sonst erhalten wir einen Widerspruch, und jeder der anderen Einträge ungleich Null ist mindestens 1. Dies macht bereits eine Summe von l[0] + (n-l[0]-1)*1 = n-1aus der Gesamtsumme von aus n. l[0]Ohne zu zählen , kann es höchstens eine 2 geben und keinen Eintrag größer als 2.

Dies bedeutet jedoch, dass die einzigen Einträge ungleich Null sind l[0], l[1], l[2], and l[l[0]], deren Werte höchstens l[0]und eine Permutation von sind1,1,2 , die eine maximale Summe von ergibt l[0]+4. Da diese Summe nmindestens 7 ist, haben wir l[0]>=3und so l[l[0]]=1. Jetzt gibt es mindestens eine 1, was bedeutet l[1]>=1, aber wenn l[1]==1das eine andere ist 1, bedeutet dies l[1]>=2, dass l[1]es der Einzige ist 2. Dies ergibt l[2]=1, und alle verbleibenden Einträge sind 0also l[0]=n-4, was die Lösung vervollständigt.

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)

Führt eine Breitensuche nach möglichen Listen durch, füllt Einträge von rechts nach links aus und stoppt die Suche an einem Suffix, wenn dies nicht plausibel ist. Dies kann passieren, wenn:

• Die Summe der Einträge im Suffix überschreitet n(die Summe für die gesamte Liste muss sein n)
• Die gewichtete Summe i*l[i]im Suffix überschreitet n(die Summe für die gesamte Liste muss sein n)
• Jede Zahl wird öfter im Suffix angezeigt, als das Suffix vorschreibt
• Die Anzahl der verbleibenden unbesetzten Stellen ist zu gering, um alle Zahlen zu berücksichtigen, die mehrmals erscheinen müssen.

Ich hatte ursprünglich getestete Präfixe von links nach rechts, aber das ging langsamer.

Die Ausgaben bis n=30sind:

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]

Mit Ausnahme der ersten drei Listen [1, 2, 1, 0], [2, 0, 2, 0], [2, 1, 2, 0, 0]gibt es genau eine Liste für jede Länge n>6und sie hat die Form [n-4, 2, 1, ..., 0, 0, 1, 0, 0, 0]. Dieses Muster bleibt mindestens bis zu bestehen n=50. Ich vermute, es hält für immer an. In diesem Fall ist es trivial, eine große Anzahl davon auszugeben. Selbst wenn nicht, würde ein mathematisches Verständnis der möglichen Lösungen eine Suche erheblich beschleunigen.

Pyth - 15 Bytes

Verwendet Brute Force durch alle möglichen Sequenzen von len nund filtert dann.

f.A.eq/TkYT^UQQ

Die vollständige Erklärung folgt in Kürze.

Probieren Sie es hier online aus .

K, 26 Bytes

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

Wie Maltysens Ansatz, rohe Gewalt. Das Herzstück des Programms ist ein Prädikat, das prüft, ob ein bestimmter Vektor "magisch" ist:

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

Erstellen Sie einen Iota-Vektor, solange der Eingabevektor ( !#x) vorhanden ist, zählen Sie die Vorkommen jeder Ziffer ( (+/x=)') und vergleichen Sie das Ergebnis mit dem Eingabevektor ( x~). Wenn es eine Übereinstimmung gibt, haben Sie eine magische Sequenz.

Leider scheint dieser erste Stich ziemlich langsam zu sein. Beim Testen mit Kona auf meinem Laptop dauert es ungefähr 12 Sekunden, bis n = 7 verarbeitet ist. Ich muss etwas mehr darüber nachdenken.