La description

Étant donné une longueur net une taille d'alphabet k>0, votre programme doit déterminer le nombre de chaînes avec ces paramètres qui ont un nombre maximal de sous-chaînes uniques. Dans le cas de k=2, cela génère OEIS A134457 .

Exemple

Par exemple, 2210a les sous - chaînes , 2, 22, 221, 2210, 2, 21, 210, 1, 10et 0, pour un total de 11. Toutefois, 2apparaît deux fois, il n'a que 10 sous - chaînes uniques.

C'est autant que possible pour une chaîne de longueur 4 contenant 3 symboles différents, mais elle est liée à 35 autres chaînes pour un total de 36 chaînes de liaison 0012, y compris 2101, et 0121. Par conséquent, pour n=4et k=3, votre programme devrait afficher 36.

Cas de test

n    k    output

0    5    1
1    3    3
5    1    1
9    2    40
2    3    6
5    5    120

code-golf combinatorics user1502040
la source

3

Pourriez-vous donner quelques exemples? Il est difficile de suivre le défi à partir de cette très courte description.

ETHproductions

Alors, non n=2, k=3sortie 9 11,12,21,22,31,32,33,13,23:?

veganaiZe

@veganaiZe Les deux chiffres ont une sous-chaîne répétée.

user1502040

2

Gelée , 9 octets

ṗµẆQLµ€ML

Essayez-le en ligne!

Saisie dans l'ordre inverse. Force brute.

Leaky Nun
la source

Économisez un octet en évitant la chaîne à trois atomes avec une transposition et une queue:ṗẆQ$€ZṪL

Jonathan Allan

3

Pyth, 12 octets

l.Ml{.:Z)^UE

Essayez-le en ligne.

Force brute pure.

Explication

Implicite: ajout Qau programme.
Implicite: lire et évaluer une ligne d'entrée ( n) dans Q.
E: lire et évaluer une ligne d'entrée ( k).
U: obtenir une gamme [0, ..., k-1].
^: obtenir des nchaînes de toutes longueurs [0, ..., k-1].
.M: trouvez ceux qui donnent un maximum de fonction f(Z):
- .:Z: trouver les sous-chaînes de Z
- {: supprimer les doublons
- l: obtenir le nombre de sous-chaînes uniques
l: obtenir le nombre de telles chaînes

PurkkaKoodari
la source

2

Mathematica, 96 octets

Last[Last/@Tally[Length@Union@Flatten[Table[Partition[#,i,1],{i,s}],1]&/@Tuples[Range@#2,s=#]]]&

J42161217
la source

2

Haskell, 82 octets

import Data.Lists
l=length
n#k=l$argmaxes(l.nub.powerslice)$mapM id$[1..k]<$[1..n]

Exemple d'utilisation: 9 # 2-> 40.

Comment ça fonctionne:

       [1..k]<$[1..n]  --  make a list of n copies of the list [1..k]
      mapM id          --  make a list of all combinations thereof, where
                       --  the 1st element is from the f1st list, 2nd from 2nd etc
  argmaxes             --  find all elements which give the maximum value for function:
     l.nub.powerslice  --    length of the list of unique sublists
l                      --  take the length of this list

nimi
la source

Nombre maximum de sous-chaînes distinctes