Maksymalna liczba różnych podciągów

9

Opis

Biorąc pod uwagę długość ni rozmiar alfabetu k>0, twój program musi określić liczbę ciągów znaków z tymi parametrami, które mają maksymalną liczbę unikalnych podciągów. W przypadku k=2generuje to OEIS A134457 .

Przykład

Na przykład, 2210ma podciągi , 2, 22, 221, 2210, 2, 21, 210, 1, 10, i 0, w sumie 11. Niemniej jednak, 2pojawia się dwa razy, tak że ma tylko 10 niepowtarzalnych podciągów.

Jest to możliwe, aż do długości łańcucha 4 zawierającej 3 różne symbole, ale że wiąże się z 35 innych łańcuchów w sumie 36 tieing łańcuchów tym 0012, 2101oraz 0121. Dlatego dla n=4i k=3twój program powinien wypisać 36.

Przypadki testowe

n    k    output

0    5    1
1    3    3
5    1    1
9    2    40
2    3    6
5    5    120
użytkownik1502040
źródło
3
Czy mógłbyś podać kilka przykładów? Trudno jest podążać za wyzwaniem z tego bardzo krótkiego opisu.
ETHprodukcje
Więc nie n=2, k=3wyjście 9 11,12,21,22,31,32,33,13,23:?
veganaiZe
@veganaiZe Podwójne cyfry mają powtarzający się podłańcuch.
user1502040,

Odpowiedzi:

2

Galaretka , 9 bajtów

ṗµẆQLµ€ML

Wypróbuj online!

Wprowadź w odwrotnej kolejności. Brutalna siła.

Leaky Nun
źródło
Oszczędź bajt, unikając łańcucha trzech atomów z transpozycją i ogonem:ṗẆQ$€ZṪL
Jonathan Allan
3

Pyth, 12 bajtów

l.Ml{.:Z)^UE

Wypróbuj online.

Czysta brutalna siła.

Wyjaśnienie

  • Domniemany: dołącz Qdo programu.
  • Domniemany: przeczytaj i oceń linię input ( n) w Q.
  • E: przeczytaj i oceń linię input ( k).
  • U: uzyskać zasięg [0, ..., k-1].
  • ^: pobierz nciągi wszystkich długości [0, ..., k-1].
  • .M: znajdź te, które dają maksimum funkcji f(Z):
    • .:Z: znajdź podciągi dla Z
    • {: usuń duplikaty
    • l: uzyskaj liczbę unikalnych podciągów
  • l: uzyskaj liczbę takich ciągów
PurkkaKoodari
źródło
2

Mathematica, 96 bajtów

Last[Last/@Tally[Length@Union@Flatten[Table[Partition[#,i,1],{i,s}],1]&/@Tuples[Range@#2,s=#]]]&
J42161217
źródło
2

Haskell, 82 bajty

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

Przykład użycia: 9 # 2-> 40.

Jak to działa:

       [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
źródło