Une séquence magique est une séquence d'entiers non négatifs x[0..n-1]telle qu'il existe exactement des x[i]instances dei

Par exemple, 6,2,1,0,0,0,1,1,0,0,0 est une séquence magique car il y a 6 0, 2 1, etc.

Écrire une fonction qui, lorsqu'elle est donnée n, génère toutes les séquences magiques de longueur n

Le programme qui peut produire la sortie correcte pour la valeur la plus élevée de n en 10 secondes gagne. (Cependant, tous les programmes sont les bienvenus)

Par exemple, le programme d'Alice peut gérer jusqu'à n = 15 en 10 secondes tandis que Bob peut gérer jusqu'à n = 20 dans le même temps. Bob gagne.

Plateforme: Linux 2,7 GHz @ 4 processeurs

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

Cela utilise le fait, que je vais prouver, que les seules séquences Magic de longueur nsont:

• [1, 2, 1, 0]et [2, 0, 2, 0]pourn=4
• [2, 1, 2, 0, 0] pour n=5
• [n-4, 2, 1, 0, 0, ..., 0, 0, 1, 0, 0, 0] pour n>=7

Donc, pour n>=7, il suffit de retourner un énorme tuple. Je peux le faire jusqu'à environ n=10^8sur mon ordinateur portable, ce qui est probablement limité par la mémoire; plus et il gèle. (Merci à trichoplax pour l'idée d'utiliser des tuples plutôt que des listes.) Ou, si l'on peut imprimer un dictionnaire d'entrées non nulles {0:n-4, 1:2, 2:1, (n-4):1}, on peut le faire pour ginormous n.

Je prouve l'unicité de n>=7; les autres peuvent être vérifiés par la force brute ou le traitement des dossiers.

La somme des entrées de lest le nombre total de tous les numéros de la liste, qui est sa longueur n. La liste contient des l[0]zéros et donc des n-l[0]entrées non nulles. Mais par définition l[0]doit être différent de zéro ou nous obtenons une contradiction, et chacune des autres entrées non nulles est au moins 1. Cela représente déjà une somme de l[0] + (n-l[0]-1)*1 = n-1sur la somme globale de n. Donc, sans compter l[0], il peut y avoir au plus un 2 et aucune entrée plus grande que 2.

Mais cela signifie que les seules entrées non nulles sont l[0], l[1], l[2], and l[l[0]], dont les valeurs sont au maximum l[0]et une permutation de 1,1,2, ce qui donne une somme maximale de l[0]+4. Puisque cette somme est n, qui est au moins 7, nous l'avons l[0]>=3, et ainsi l[l[0]]=1. Maintenant, il y en a au moins un 1, ce qui signifie l[1]>=1, mais si l[1]==1c'est un autre 1, alors l[1]>=2, ce qui implique l[1]est le seul 2. Cela donne l[2]=1, et toutes les entrées restantes le sont 0, donc l[0]=n-4, ce qui complète la solution.

Python 3, n≈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)

Effectue une recherche en premier des listes possibles, remplit les entrées de droite à gauche, arrête la recherche à un suffixe si elle n'est pas plausible, ce qui peut se produire si:

• La somme des entrées du suffixe dépasse n(la somme de la liste entière doit être n)
• La somme pondérée de i*l[i]dans le suffixe dépasse n(la somme pour la liste entière doit être n)
• Tout nombre apparaît dans le suffixe plus de fois que le suffixe indique qu'il devrait
• Le nombre de places non remplies restantes est trop petit pour tenir compte de tous les nombres qui doivent apparaître plusieurs fois.

J'avais des préfixes testés d'origine de gauche à droite, mais cela s'est fait plus lentement.

Les sorties jusqu'à n=30sont les suivantes:

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]

À l'exception des trois premières listes [1, 2, 1, 0], [2, 0, 2, 0], [2, 1, 2, 0, 0], il y a exactement une liste de chaque longueur n>6et elle a la forme [n-4, 2, 1, ..., 0, 0, 1, 0, 0, 0]. Ce schéma persiste jusqu'à au moins n=50. Je soupçonne que cela tient pour toujours, auquel cas il est trivial d'en afficher un grand nombre. Même si ce n'est pas le cas, une compréhension mathématique des solutions possibles accélérerait considérablement la recherche.

Pyth - 15 octets

Utilise la force brute par toutes les séquences possibles de len npuis de filtres.

f.A.eq/TkYT^UQQ

Une explication complète à venir.

Essayez-le ici en ligne .

K, 26 octets

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

Comme l'approche de Maltysen, la force brute. Le cœur du programme est un prédicat qui teste si un vecteur donné est "magique":

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

Construisez un vecteur iota tant que le vecteur d'entrée ( !#x), comptez les occurrences de chaque chiffre ( (+/x=)') et comparez le résultat avec le vecteur d'entrée ( x~). S'il y a une correspondance, vous avez une séquence magique.

Malheureusement, ce premier coup de couteau semble être assez lent. En utilisant Kona sur mon ordinateur portable, il faut environ 12 secondes pour gérer n = 7. Je dois y réfléchir un peu plus.