Descripción

Dada una longitud ny un tamaño de alfabeto k>0, su programa debe determinar el número de cadenas con esos parámetros que tienen un número máximo de subcadenas únicas. En el caso de k=2, esto genera OEIS A134457 .

Ejemplo

Por ejemplo, 2210tiene las subcadenas , 2, 22, 221, 2210, 2, 21, 210, 1, 10, y 0, para un total de 11. Sin embargo,2 aparece dos veces, por lo que sólo tiene 10 subcadenas únicas.

Este es el mayor número posible para una longitud de 4 cadena que contiene 3 símbolos diferentes, pero los lazos con otros 35 cuerdas para un total de 36 cuerdas tieing incluyendo 0012, 2101, y 0121. Por lo tanto, para n=4yk=3 , su programa debería generar 36.

Casos de prueba

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
fuente

3

¿Podría por favor dar algunos ejemplos? Es un poco difícil seguir el desafío de esa breve descripción.

ETHproductions

Entonces, ¿no n=2, k=3salida 9 11,12,21,22,31,32,33,13,23:?

veganaiZe

@veganaiZe Los dos dígitos tienen una subcadena repetida.

user1502040

2

Jalea , 9 bytes

ṗµẆQLµ€ML

Pruébalo en línea!

Entrada en orden inverso. Fuerza bruta.

Monja permeable
fuente

Ahorre un byte evitando la cadena de tres átomos con una transposición y una cola:ṗẆQ$€ZṪL

Jonathan Allan

3

Pyth, 12 bytes

l.Ml{.:Z)^UE

Pruébalo en línea.

Pura fuerza bruta.

Explicación

Implícito: agregar Q al programa.
Implícito: leer y evaluar una línea de entrada ( n) en Q.
E: lee y evalúa una línea de entrada ( k).
U: obtener un rango [0, ..., k-1].
^: obtener ncadenas de todas las longitudes de [0, ..., k-1].
.M: encuentra los que dan un máximo para la función f(Z):
- .:Z: encontrar las subcadenas de Z
- {: eliminar duplicados
- l: obtener el número de subcadenas únicas
l: obtener el número de tales cadenas

PurkkaKoodari
fuente

2

Mathematica, 96 bytes

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

J42161217
fuente

2

Haskell, 82 bytes

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

Ejemplo de uso: 9 # 2-> 40.

Cómo 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
fuente

Número máximo de subcadenas distintas