Particionar uma lista!

10

Nesse desafio, você precisa particionar uma lista, onde as partições têm um tamanho máximo, um tamanho mínimo e um tamanho preferido. Usarei a notação (min,pref,max) para indicar os tamanhos neste desafio.

Para aqueles não familiarizados com o particionamento, a lista a seguir foi particionada em partes de 3:
[0..9] -> [[0,1,2],[3,4,5],[6,7,8]]

Quando a lista não é divisível, você precisa das partições para ser o mais próximo ao tamanho preferido possível: [0..10], (2,4,5) -> [[0,1,2,3],[4,5,6],[7,8,9]]. Essa partição é preferível [[0,1,2,3],[4,5,6,7],[8,9]], mesmo que a última tenha mais do comprimento preferido. Formalmente, precisamos minimizar a soma de (partitionLength-preferredSize)^2para cada partição.

A ordem dos comprimentos das partições não importa: For [0..5], (2,3,3), ou [[0,1,2],[3,4]]ou [[0,1],[2,3,4]]funciona. Se não houver partição é possível, voltar uma matriz vazia: [0..7], (4,4,5) -> [].

Você pode assumir que 1<=min<=pref<=max, e que a matriz passada para você é uma matriz não vazia de números inteiros. A matriz sempre será o primeiro argumento. Você pode aceitar min, max e pref em qualquer ordem e como uma tupla ou como argumentos separados.

Seu programa deve ser executado em alguns segundos. Basicamente, a iteração em todos os tamanhos de partições possíveis dentro dos limites não é permitida.

Casos de teste:

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

Este é um , então tente o mínimo de bytes possível no seu idioma favorito!

Nathan Merrill
fonte
A notação que você está usando [a..b]inclui ae exclui b, correto?
Alex A.
A inclusivo, B exclusivo.
Nathan Merrill
Note-se que a sua interpretação de um não é o mesmo que uma partição da teoria dos conjuntos ...
agtoever
Mas é efetivamente equivalente ao particionamento inteiro.
Nathan Merrill
E se não houver solução?
feersum

Respostas:

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]]

Em qualquer partição, se houver duas listas com comprimentos diferentes de duas ou mais, sempre será benéfico reduzir a lista maior e aumentar a lista menor. portanto, precisamos considerar apenas partições com apenas dois tamanhos de lista, o que simplifica o cálculo.

o programa é executado em todas as quantidades possíveis de listas na partição. dada a quantidade de listas na partição, a pontuação é determinada exclusivamente. o programa calcula uma partição apropriada e sua pontuação.

então ele encontra o mínimo geral e o devolve.

Uso: entrada como f [1,2,3,4,5] 1 3 4( fé a função que resolve o desafio)

Embora seja possível calcular a melhor opção completamente numericamente e somente depois particionar a lista de acordo, foram necessários muitos bytes. no entanto, minha última versão dessa abordagem é:

_%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]]
orgulhoso haskeller
fonte
1

CJam, 70

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

Experimente online

O código localiza uma sequência ideal de tamanhos de partição com base no tamanho da lista, usando programação dinâmica (via recursão memorizada), depois segue em frente e particiona a lista.

aditsu sair porque SE é MAU
fonte