Descrição

Dado um comprimento ne um tamanho de alfabeto k>0, seu programa deve determinar o número de cadeias com os parâmetros que possuem um número máximo de substrings exclusivas. No caso de k=2, isso gera OEIS A134457 .

Exemplo

Por exemplo, 2210tem as subsequências , 2, 22, 221, 2210, 2, 21, 210, 1, 10, e 0, para um total de 11. No entanto, 2é exibida duas vezes, de modo que só tem 10 subsequências exclusivos.

Isso é o máximo possível para um comprimento de 4 cordas que contém 3 símbolos diferentes, mas está vinculado a outras 35 cordas para um total de 36 cordas de amarração 0012, incluindo,, 2101e 0121. Portanto, para n=4e k=3, seu programa deve gerar 36.

Casos de teste

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
fonte

3

Você poderia dar alguns exemplos? É meio difícil seguir o desafio dessa descrição muito curta.

ETHproductions

Então, não n=2, k=3saída 9 11,12,21,22,31,32,33,13,23:?

precisa saber é o seguinte

@veganaiZe Os dígitos duplos têm uma substring repetida.

precisa saber é o seguinte

2

Geléia , 9 bytes

ṗµẆQLµ€ML

Experimente online!

Entrada em ordem inversa. Força bruta.

Freira Furada
fonte

Guardar a um byte, evitando a cadeia de três átomo com uma transposição e cauda:ṗẆQ$€ZṪL

Jonathan Allan

3

Pitão, 12 bytes

l.Ml{.:Z)^UE

Experimente online.

Força bruta pura.

Explicação

Implícito: anexado Qao programa.
Implícito: leia e avalie uma linha de entrada ( n) em Q.
E: leia e avalie uma linha de entrada ( k).
U: obtenha um intervalo [0, ..., k-1].
^: obtenha todas as nseqüências de caracteres de [0, ..., k-1].
.M: encontre os que dão o máximo de função f(Z):
- .:Z: encontre as substrings de Z
- {: remover duplicatas
- l: obtenha o número de substrings exclusivos
l: obtém o número de tais strings

PurkkaKoodari
fonte

2

Mathematica, 96 bytes

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

J42161217
fonte

2

Haskell, 82 bytes

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

Exemplo de uso: 9 # 2-> 40.

Como funciona:

       [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
fonte

Número máximo de substrings distintos