Séquences de Skolem
Une séquence Skolem est une séquence de 2n
nombres où chaque nombre i
entre 1
et n
se produit exactement deux fois, et la distance entre les deux occurrences de i
est exactement des i
étapes. Voici quelques exemples de séquences Skolem:
1 1
1 1 4 2 3 2 4 3
16 13 15 12 14 4 7 3 11 4 3 9 10 7 13 12 16 15 14 11 9 8 10 2 6 2 5 1 1 8 6 5
Les séquences suivantes ne sont pas des séquences Skolem:
1 2 1 2 (The distance between the 1's is 2, not 1)
3 1 1 3 (The number 2 is missing)
1 1 2 1 1 2 (There are four 1's)
Objectif
Écrivez un programme, une fonction ou une expression pour compter le nombre de toutes les séquences Skolem d'une longueur donnée. Plus explicitement, votre entrée est un entier n
et votre sortie est le nombre de séquences Skolem de longueur 2n
. Cette séquence a une entrée OEIS . Pour n = 0
, vous pouvez retourner soit 0
ou 1
. Les premières valeurs, à partir de 0
, sont
0, 1, 0, 0, 6, 10, 0, 0, 504, 2656, 0, 0, 455936, 3040560, 0, 0, 1400156768
Règles et notation
C'est le golf de code. Le format de sortie est laxiste dans des limites raisonnables.
0, 1, 0, 0, 6...
votre question? Est-ce l'extrait de code, si oui, quelle langue est-ce?0
? Si vous allez l'admettre0
comme une entrée valide, la sortie devrait l'être1
.Réponses:
GolfScript,
4846 caractèresLa version plus rapide ( essayez en ligne ) - s'exécute assez rapidement, par exemple
n=8
prend environ deux secondes. Et l'approche choisie prend vraiment peu de caractères.Cette version fonctionne également avec les bitmasks. Il construit le tableau de résultats possible à partir de 1, c'est-à-dire pour
n=3
:Alors que certains résultats (comme 000011) ont deux suites possibles, d'autres (par exemple 001100) n'en ont pas et sont supprimés du tableau de résultats.
Explication du code:
la source
Expression J, 47 caractères
Exemple:
Prend environ 30 secondes pour
y=:5
sur ma machine.l'algorithme est aussi lent que possible:
~.(i.!+:y)A.,~>:i.y
génère chaque permutation1 2 .. y 1 2 .. y
et supprime les entrées en double((=&{:+.2-#@])#;.2)\"1
calcule:(...)\"1
pour chaque préfixe de chaque ligne:#;.2
compte les éléments avant chaque occurrence du dernier élément#@]
compte le nombre de comptes (c'est-à-dire le nombre d'occurrences du dernier élément)=&{:
détermine "l'égalité" "des" "derniers éléments" de la liste de comptage et de la liste d'origine.+.
est un OU logique.=&{:+.2-#@]
lit "soit les derniers éléments [de la liste de comptage et la liste d'origine] sont égaux, soit il n'y a qu'un seul élément [dans la liste de comptage] plutôt que deux".*/"1
multiplie (ET logique) sur les lignes de la table de conditions, déterminant quelles permutations sont des séquences de Skolem.+/
additionne les uns et les zéros ensemble.la source
GolfScript (46 caractères)
Il s'agit d'une expression qui prend des entrées sur la pile. Pour le transformer en un programme complet qui prend des entrées sur stdin, ajoutez
~
Il est assez inefficace - la plupart des économies que j'ai réalisées en jouant au golf à partir de 56 caractères non golfés l'ont été en élargissant la gamme de boucles de manière à ne pas introduire de résultats incorrects mais à calculer les déchets.
L'approche consiste à masquer au niveau du bit les produits cartésiens. Par exemple (en utilisant binaire pour les masques) pour
n=4
le code non golfé, le xor de chaque élément du produit cartésien serait calculé[00000011 00000110 ... 11000000] x [00000101 00001010 ... 10100000] x ... x [00010001 ... 10001000]
. Tout résultat avec 8 bits ne pouvait être obtenu que par des masques sans chevauchement.Afin d'optimiser la taille plutôt que la vitesse, le code accumule des produits partiels (
S1 u S1xS2 u S1xS2xS3 ...
) et fait que chaque produit soit2n
composé d' éléments plutôt que simplement ceux2n-1-i
qui peuvent réellement contribuer à une séquence valide.La vitesse
La version golfée dure
n=5
10 secondes sur mon ordinateur et plus de 5 minutesn=6
. La version originale non golfée calculen=5
en moins d'une seconde etn=6
en environ 1 minute. Avec un simple filtre sur les résultats intermédiaires, il peut calculern=8
en 30 secondes. Je l'ai joué à 66 caractères (en tant que programme - 65 caractères comme expression) tout en gardant les boucles aussi restreintes que possible et en filtrant les collisions intermédiaires:la source
GolfScript, 49 caractères
Attend le nombre
n
sur STDIN. C'est du code-golf - n'essayez pas le code avecn
plus de 5.la source
Sauge, 70
C'est un peu plus court que mon original.
Comment ça fonctionne:
Étant donné une matrice 0/1, le problème de couverture exact pour cette matrice est de trouver un sous-ensemble des lignes qui résument (sous forme d'entiers) au vecteur tout-en-un. Par exemple,
a une solution
Mon approche préférée des problèmes consiste à les convertir en un problème de couverture exact. Les séquences de Skolem facilitent efficacement cela. Je fais un problème de couverture exacte où les solutions sont en bijection avec des séquences Skolem de longueur
2n
. Par exemple, une ligne du problème pourn=6
estoù un 1 en position
a < n
signifie que le symbolea
est utilisé. Les positions restantes correspondent aux emplacements réels de la séquence. Une couverture exacte correspond à chaque symbole utilisé une seule fois et à chaque emplacement rempli une seule fois. Par construction, tout symbolek
dans un emplacement estk
éloigné de son partenaire.Dans Sage,
DLXCPP
est une implémentation de "liens dansants" - elle résout le problème de couverture exacte d'une manière exceptionnellement gracieuse. C'est l'un de mes algorithmes préférés, et être à la surface dans Sage rend l'énumération combinatoire une joie.la source
len(list(...))
économisera 4 caractères.len(list(...))
pour n = 16. Et cela tuerait complètement le runtime.