Rozmieszczenie liczb w tablicy dające równomierny rozkład sum

Temat brzmi kiepsko, ale lepszego nie wymyśliłem. Dana jest n-elementowa tablica liczb t. Liczby należy tak poprzestawiać by zbiór sum k-elementowych spójnych podciągów miał minimalne odchylenie standardowe. Sumujemy "w kółko", np. dla n=8 i k=3 interesują nas sumy<tt>
t[0]+t[1]+t[2]
...
t[6]+t[7]+t[0]
t[7]+t[0]+t[1]</tt>
Interesuje mnie też taka wersja problemu: k nie jest ustalone, ustalone jest maksymalne dopuszczalne odchylenie standardowe. Należy wyznaczyć najmniejsze k przy jakim da się poprzestawiać.

Pomyślę nad tym jeszcze później, ale tak na pierwszy rzut oka to mi to wygląda na problem przynajmniej PSPACE ;) Szczególnie że algorytm naiwny to jest O(n*n!) (testujemy wszystkie permutacje dla każdego możliwego k). Mam wątpliwości czy da się to zrobić "szybko". Bo wygląda to jak mocno utrudniona wersja Subset Sum.

Może bez brute force da się znaleźć mniej ambitne rozwiązanie, tzn. takie które daje najmniejszą różnicę między skrajnymi wartościami sumy.

Na pierwszy rzut oka - potrzebujesz stożek.

1. Sortujesz t
2. Przepisujesz w kolejności: t[0],t[2],t[4],t[6],t[7],t[5],t[3],t[1]

@_13th_Dragon - niestety (albo na szczęście, wygląda ciekawie), to zadanie nie jest takie proste:

# t = [0, 1, 2, 3, 4, 5, 6, 7]
>>> solve.best([0, 1, 2, 3, 4, 5, 6, 7])
(10.0, (0, 4, 5, 1, 6, 2, 3, 7))  # brute force do testów
>>> solve.evaluate([0, 2, 4, 6, 7, 5, 3, 1])
242.0   # wynik stożka - 240
>>> solve.evaluate([0, 4, 5, 1, 6, 2, 3, 7])
10.0    # najlepszy wynik - 10
# `wynik` to w sumie nie odchylenie standardowe a wariancja * n, co przy szukaniu minimum nie ma znaczenia

edit: huh. Ale trzeba przyznać że znalazłeś przy okazji sposób na znalezienie najgorszego rozwiązania:

>>> solve.worst([0, 1, 2, 3, 4, 5, 6, 7])
(242.0, (7, 6, 4, 2, 0, 1, 3, 5))

Ew. źle interpretuję polecenie, ale miała być minimalizacja.

Rozwiązanie @_13th_Dragon wydaje się dość ciekawe :) Ale to nie jest takie proste ;) Bo przecież dla:
111222333 chcielibyśmy dostać
123123123 i k=3
Ale sama idea wydaje się dość sensowna -> chcemy żeby elementy większe znosiły się z mniejszymi, ale ja bym je łączył na zasadzie łączenia końca z początkiem.
Tzn dla k=2 dałbym coś w stylu
t[0],t[n],t[1],t[n-1]...
A w ogólności dla zadanego k brałbym sobie z ciągu elementy 0, 1*n/k, 2*n/k, ... ,n, potem nastepna grupka to to samo ale przesunięte o 1
Tylko że takie rozwiązanie dąży do ustalenia minimalnego odchylenia, a nie koniecznie minimalnego k ;]

edit:

from builtins import sorted, range, len, sum, min, int
from math import sqrt


def get_sigma(input, k):
    n = len(input)
    solutions = get_solutions(input, k)
    sums = [sum(solution)for solution in solutions]
    avg = sum(sums)/n
    return sqrt(sum([(nth_sum - avg)*(nth_sum - avg) for nth_sum in sums])/n)


def get_solutions(input, k):
    n = len(input)
    return [[input[i+j*int(n/k)-n] for j in range(k)] for i in range(n)]


def solve(input, border_sigma):
    ordered = sorted(input)
    n = len(ordered)
    sigmas = [(k, get_sigma(ordered, k)) for k in range(1, n)]
    print(sigmas)
    in_range = [(k, sigma) for (k, sigma) in sigmas if sigma <= border_sigma]
    if in_range:
        return min(in_range, key=lambda k_sigma: k_sigma[0])
    else:
        return -1, -1


def main():
    input = [1, 1, 1, 2, 2, 2, 3, 3, 3]
    # input = [0, 1, 2, 3, 4, 5, 6, 7]
    
    border_sigma = 0.0
    k, sigma = solve(input, border_sigma)
    print(k, sigma)
    print(get_solutions(sorted(input), k))
main()

Działa to nawet. Zwraca minimalne k (i liste rozwiazań) dla rozwiązania które ma sigmę mieszczącą się w podanym zakresie.
Wydaje mi się że moze to być nawet poporawne. Na logikę takie składanie rozwiązań powinno dać nam zawsze minimalne odchylenie dla każdego k.

Ten kod raczej nie działa, dla wejścia [0,1,2,3,4,5,6,7] proponuje k=4. Dla k=2 minimalne odchylenie standardowe wynosi (zdaniem programu) 2.23606797749979. Łatwo sprawdzić, że dla uporządkowania [0,7,1,6,2,5,3,4] i k = 2 odchylenie standardowe jest mniejsze niż 1.3.

Faktycznie, ale idea wydaje mi się nadal poprawna, tzn żeby sortować i łączyć liczby tak żeby uśrednić wartość. Ale to trochę bardziej skomplikowane.
Widać na przykład że dla k=2 optymalny podział to sortowanie a potem branie t[0], t[n], t[1], t[n-1]..., t[n/2-1], t[n/2]. ;]