Partitionieren Sie eine Liste!

10

Bei dieser Herausforderung müssen Sie eine Liste partitionieren, in der Partitionen eine maximale Größe, eine minimale Größe und eine bevorzugte Größe haben. Ich werde die Notation verwenden (min,pref,max) , um die Größen in dieser Herausforderung anzugeben.

Für diejenigen, die mit der Partitionierung nicht vertraut sind, wurde die folgende Liste in Teile von 3 unterteilt:
[0..9] -> [[0,1,2],[3,4,5],[6,7,8]]

Wenn die Liste nicht gleichmäßig teilbar ist, müssen die Partitionen so nahe wie möglich an der bevorzugten Größe liegen : [0..10], (2,4,5) -> [[0,1,2,3],[4,5,6],[7,8,9]]. Diese Aufteilung ist vorzuziehen [[0,1,2,3],[4,5,6,7],[8,9]], obwohl letztere mehr von der bevorzugten Länge hat. Formal müssen wir die Summe (partitionLength-preferredSize)^2für jede Partition minimieren .

Die Reihenfolge der Partitionslängen spielt keine Rolle: Für [0..5], (2,3,3), entweder [[0,1,2],[3,4]]oder [[0,1],[2,3,4]]funktioniert. Wenn keine Partition möglich ist, geben Sie ein leeres Array zurück : [0..7], (4,4,5) -> [].

Sie können davon ausgehen 1<=min<=pref<=max, dass das an Sie übergebene Array ein nicht leeres Array von Ganzzahlen ist. Das Array wird immer das erste Argument sein. Sie können min, max und pref in beliebiger Reihenfolge und als Tupel oder als separate Argumente akzeptieren.

Ihr Programm muss in wenigen Sekunden ausgeführt werden. Grundsätzlich ist es nicht zulässig, jede mögliche Partitionsgröße innerhalb der Grenzen zu durchlaufen.

Testfälle:

[1], (1,3,4)         -> [[1]]
[100], (1,2,3)       -> [[100]]
[1,2], (1,1,2)       -> [[1],[2]]
[1,2], (1,2,2)       -> [[1,2]]
[1,2], (1,3,3)       -> [[1,2]]
[1,2,3], (1,2,3)     -> [[1,2],[3]] or [[1,2,3]]
[1,2,3,4], (1,3,4)   -> [[1,2,3,4]]
[1,2,3,4,5], (3,3,4) -> []
[1,2,3,4,5], (2,2,2) -> []
[1,2,3,4,5], (3,3,5) -> [[1,2,3,4,5]]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49], (2,6,6) -> [[1,2,3,4,5,6],[7,8,9,10,11,12],[13,14,15,16,17,18],[19,20,21,22,23,24],[25,26,27,28,29],[30,31,32,33,34],[35,36,37,38,39],[40,41,42,43,44],[45,46,47,48,49]]

Dies ist ein , also streben Sie so wenig Bytes wie möglich in Ihrer Lieblingssprache an!

Nathan Merrill
quelle
Die von Ihnen verwendete Notation [a..b]schließt ein aund aus b, richtig?
Alex A.
A inklusive, B exklusiv.
Nathan Merrill
Beachten Sie, dass Ihre Interpretation von a nicht mit einer Partition aus der Mengenlehre
identisch
Aber es ist effektiv äquivalent zu integer Partitionierung.
Nathan Merrill
Was ist, wenn es keine Lösung gibt?
Feersum

Antworten:

2

Haskell, 152

_%0=[]
s%k|(a,b)<-splitAt(div(z s)k)s=a:b%(k-1)
z=length
f s n p x=snd$minimum$(z s*p^2,[]):[(sum[(z x-p)^2|x<-s%k],s%k)|k<-[-div(-z s)x..div(z s)n]]

Wenn es in einer Partition zwei Listen gibt, deren Länge sich um zwei oder mehr unterscheidet, ist es immer vorteilhaft, die größere Liste zu verkleinern und die kleinere Liste zu vergrößern. Daher müssen wir nur Partitionen mit nur zwei Listengrößen berücksichtigen, was die Berechnung vereinfacht.

Das Programm wird dann auf allen möglichen Listenmengen in der Partition ausgeführt. Angesichts der Anzahl der Listen in der Partition wird die Punktzahl eindeutig bestimmt. Das Programm berechnet eine passende Partition und deren Punktzahl.

dann findet es das Gesamtminimum und gibt es zurück.

Verwendung: Eingabe wie f [1,2,3,4,5] 1 3 4( fist die Funktion, die die Herausforderung löst)

Obwohl es möglich ist, die beste Option vollständig numerisch zu berechnen und die Liste erst dann entsprechend zu partitionieren, wurden zu viele Bytes benötigt. Meine letzte Version dieses Ansatzes ist jedoch:

_%0=[]
s%k|(a,b)<-splitAt(div(length s)k)s=a:b%(k-1)
f s n p x|l<-length s=(s%)$snd$minimum$(l*p^2,0):[(k*j^2+mod l k*(1-2*j),k)|k<-[1..div l n],k*x>=l,j<-[p-div l k]]
stolzer haskeller
quelle
1

CJam, 70

q~:S;_,[0L]a{_S2=e<),S0=>f{[__S1=-_*\]@@-j.+}[esL]a+:e<}j1={/(\e_}/;]p

Probieren Sie es online aus

Der Code findet mithilfe der dynamischen Programmierung (über gespeicherte Rekursion) eine optimale Folge von Partitionsgrößen basierend auf der Listengröße. Anschließend wird die Liste partitioniert.

Aditsu beenden, weil SE böse ist
quelle