Maximale Anzahl unterschiedlicher Teilzeichenfolgen

9

Beschreibung

Bei einer bestimmten Länge nund Alphabetgröße k>0muss Ihr Programm die Anzahl der Zeichenfolgen mit den Parametern bestimmen, die eine maximale Anzahl eindeutiger Teilzeichenfolgen aufweisen. Im Fall von k=2erzeugt dies OEIS A134457 .

Beispiel

Zum Beispiel 2210den Teil hat , 2, 22, 221, 2210, 2, 21, 210, 1, 10, und 0, für insgesamt 11 jedoch 2erscheint zweimal, so dass nur es 10 einzigartigen Teil hat.

Dies sind so viele wie möglich für eine Zeichenfolge mit einer Länge von 4, die 3 verschiedene Symbole enthält. Sie werden jedoch mit 35 anderen Zeichenfolgen verknüpft 0012, sodass insgesamt 36 Zeichenfolgen einschließlich 2101, und 0121. Daher sollte Ihr Programm für n=4und k=336 ausgeben.

Testfälle

n    k    output

0    5    1
1    3    3
5    1    1
9    2    40
2    3    6
5    5    120
user1502040
quelle
3
Könnten Sie bitte einige Beispiele nennen? Es ist schwierig, der Herausforderung anhand dieser sehr kurzen Beschreibung zu folgen.
ETHproductions
Also nicht n=2, k=3Ausgabe 9 : 11,12,21,22,31,32,33,13,23?
veganaiZe
@veganaiZe Die zweistelligen Zahlen haben eine wiederholte Teilzeichenfolge.
user1502040

Antworten:

2

Gelee , 9 Bytes

ṗµẆQLµ€ML

Probieren Sie es online aus!

Eingabe in umgekehrter Reihenfolge. Rohe Gewalt.

Undichte Nonne
quelle
Speichern Sie ein Byte, indem Sie die Drei-Atom-Kette mit einer Transponierten und einem Schwanz vermeiden:ṗẆQ$€ZṪL
Jonathan Allan
3

Pyth, 12 Bytes

l.Ml{.:Z)^UE

Probieren Sie es online aus.

Reine rohe Gewalt.

Erläuterung

  • Implizit: Qan das Programm anhängen .
  • Implizit: Lesen und Auswerten einer Eingabezeile ( n) in Q.
  • E: Lesen und Auswerten einer Eingabezeile ( k).
  • U: eine Reichweite bekommen [0, ..., k-1].
  • ^: nHolen Sie sich alle -Längen-Zeichenfolgen von [0, ..., k-1].
  • .M: finde diejenigen, die ein Maximum für die Funktion geben f(Z):
    • .:Z: finde die Teilzeichenfolgen von Z
    • {: Duplikate entfernen
    • l: Ermittelt die Anzahl der eindeutigen Teilzeichenfolgen
  • l: Ermitteln Sie die Anzahl solcher Zeichenfolgen
PurkkaKoodari
quelle
2

Mathematica, 96 Bytes

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

Haskell, 82 Bytes

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

Anwendungsbeispiel: 9 # 2-> 40.

Wie es funktioniert:

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