[Algorytmy] Grupowanie średnich arytmetycznych.

[m72]

Niech moderator sam zdecyduje gdzie to wkleić bo ja nie wiem.
Problem wygląda tak. Jest określona ilość zaindeksowanych wartości np.

• w1=33.3

• w2=23.1

• w3=35.55

• .

• .

• .

• wn=28.8

Chcemy je pogrupować na N równych części tak żeby średnie arytmetyczne każdej z części były jak najbardziej zbliżone do siebie.
Jako wynik chciałbym dostać indeksy wartości których nalezy uzyć.

Np: GRUPA1
w1,w4,w76,w44...

Np: GRUPA2
w2,w54,w5,w8...

Np: GRUPA3
w17,w9,w6,w8...

Zastosowanie:
Konkretnie to chodzi o segregację ogniw litowo jonowych do budowy pakietów.
Mam pomierzone oporności wewnętrzne w miliomach i muszę je pogrupować w pakiety tak żeby średnia tych oporów w każdym pakiecie była zbliżona.

Jakby co trochę ogarniam matlaba więc może być jakieś rozwiązanie bazujące na macierzach.

[Gosda]

Jak duży jest zestaw danych? Jeśli nie za duży, możesz spróbować po prostu algorytmu losowego Pisane na kolanie (na Macu, więc nie mam pod ręką komendy shuf):

Kod: Zaznacz cały

 ~ $ values=($(for i in {1..100}; do echo "$((RANDOM % 1000))"; done))

 ~ $ echo ${values[@]}
29 480 88 935 374 642 525 685 957 273 973 990 900 758 111 844 978 408 847 799 412 955 220 554 981 348 218 895 125 645 262 731 27 273 261 18 786 838 955 993 980 606 341 141 890 659 406 151 135 974 505 812 320 142 19 142 187 8 886 596 818 484 852 97 974 649 466 688 523 413 800 923 648 519 594 93 91 793 129 798 598 734 23 728 36 183 628 403 130 389 923 493 357 934 955 231 655 408 110 720

 ~ $ difference=1000000; while true; do shuffled_values="$(echo "${values[@]}" | tr ' ' '\n' | shuf)"; new_difference="$(awk 'BEGIN {minimum = 1000000; maximum = 0; total = 0;} {total += $1; if (NR % 10 == 0) {if (total > maximum) {maximum = total}; if (total < minimum) {minimum = total}; total = 0;}} END {print maximum-minimum}' <<< "${shuffled_values}")"; if ((difference > new_difference)); then echo "Found better order: ${shuffled_values} with difference ${new_difference} between largest and smallest group" | paste -d ' ' -s -; difference="${new_difference}"; fi; done
Found better order: 786 142 923 955 273 648 838 183 348 606 484 273 728 659 799 125 993 758 403 505 800 973 688 8 220 466 519 955 594 412 554 852 798 135 890 480 408 23 655 980 818 187 341 955 731 413 97 389 720 523 93 261 320 129 934 27 130 406 935 262 642 895 793 847 812 596 598 141 91 19 525 29 374 900 408 111 978 981 974 142 734 231 886 844 110 990 628 649 36 88 923 18 974 218 685 957 357 493 645 151 with difference 2278 between largest and smallest group
Found better order: 606 734 341 320 408 389 493 886 111 659 993 798 93 981 923 786 273 957 187 141 18 800 231 838 935 688 974 554 8 728 793 923 758 980 142 523 273 642 129 97 412 466 23 628 218 978 596 649 262 990 36 799 88 812 973 685 130 91 110 818 648 220 844 731 374 525 261 847 519 27 955 955 505 29 974 19 151 183 645 598 852 594 413 484 135 934 357 480 406 720 408 900 125 348 955 890 403 895 142 655 with difference 1590 between largest and smallest group
Found better order: 129 786 993 642 273 413 8 734 519 36 799 389 957 890 408 606 973 135 466 97 231 628 923 649 142 812 151 645 598 981 886 141 659 493 18 685 374 320 262 594 974 218 935 758 793 91 341 412 505 655 23 183 852 955 357 484 731 955 847 130 261 728 110 187 978 688 523 29 974 408 720 955 88 27 273 480 818 125 648 990 838 844 800 93 525 111 934 19 798 900 406 596 980 348 895 554 923 142 220 403 with difference 1430 between largest and smallest group
Found better order: 29 341 720 838 413 973 406 273 554 183 23 798 598 649 596 525 978 348 895 97 466 403 18 731 505 389 844 799 19 847 519 408 955 818 852 374 886 273 142 130 262 955 141 688 142 655 484 890 8 981 980 812 125 659 793 135 357 261 151 957 594 36 728 220 408 648 955 974 734 523 800 187 88 93 231 628 990 923 934 993 923 935 111 642 480 412 900 129 110 320 91 27 606 758 786 218 974 493 645 685 with difference 1137 between largest and smallest group
Found better order: 97 130 320 262 606 990 412 955 955 273 649 895 348 798 847 374 23 231 793 408 955 111 594 151 484 628 973 110 523 844 525 923 554 890 129 27 800 818 357 29 403 135 993 974 981 389 659 93 19 598 648 596 934 36 183 505 728 734 688 480 720 8 91 838 980 18 799 413 852 187 935 406 341 220 974 493 141 642 786 273 645 758 218 125 923 466 88 978 900 685 655 142 408 812 886 142 261 731 957 519 with difference 880 between largest and smallest group
Found better order: 91 978 844 852 594 151 27 273 900 628 642 135 793 955 786 466 341 231 523 130 606 957 187 890 554 493 596 218 389 408 659 125 655 142 955 812 649 29 923 408 935 480 734 23 413 88 220 974 525 847 934 374 955 111 800 973 895 8 36 731 981 412 142 645 484 818 110 648 18 923 403 183 93 993 129 598 97 838 758 990 798 685 505 273 261 799 720 348 320 406 980 19 141 262 357 519 886 688 974 728 with difference 815 between largest and smallest group
(...)

 ~ $ type shuf
shuf is a function
shuf () 
{ 
    perl -MList::Util=shuffle -e 'print shuffle(<>);' "$@"
}

Idea za tym stojąca jest taka. Mamy sto wartości i chcemy je pogrupować po dziesięć. Ustawiamy w losowej kolejności i liczymy, jaka jest suma kolejnych dziesiątek. Liczymy różnicę między największą sumą i najmniejszą. Jeśli jest lepsza niż poprzedni rekord, wypisujemy wszystkie wartości.