Równomierny rozkład liczb ze zbioru w mniejsze zestawy.

[warchlak13]

Witam,

postaram się przedstawić swój problem jak najdokładniej będę w stanie.
Z góry chciałbym jednak zaznaczyć, że owe zagadnienie łączy ze sobą zarówno kombinatorykę, prawdopodobieństwo i statystykę. Wybrałęm po środku - kombinatorykę, bo jest jej tu najwięcej (jeśli źle trafiłem, spróbuję przenieść temat).

Do rzeczy:
Posiadamy zbiór liczb. Jest ich dajmy na to: pięć (1,2,3,4,5). Chcemy teraz rozpisać je w zestawy po trzy w jednym. Z dwumianu Newtona wiemy, że takich kombinacji jest dokładnie 10. Tutaj zaczynają się schody.

Ja potrzebuję rozpisać je nie w dziesięciu, lecz w (dla przykładu) 5 zestawach po 3 liczby tak, by prawdopodobieństwo wystąpienia każdej z każdą było jak największe. W tym wypadku będzą to takie zestawy:

Kod: Zaznacz cały

123,  125,  145,  234,  345

Jak widzimy:
-jedynka z dwójką występuje: 2 razy,
-jedynka z rójką: raz,
-jedynka z czwórką: raz,
-jedynka z piątką: 2 razy,
-dwójka z trójką: 2 razy,
-dwójka z czwórką: raz,
-dwójka z piątką: raz,
-trójka z czwórką: 2 razy,
-trójka z piątką: raz;
-czwórka z piątką: 2 razy,

W najlepszym wypadku liczby wypadały po 2x, nigdy więcej; w najgorszym tylko raz w parze.

No i moje pytanie, które nawet jak teraz się zastanowić zakrawa pod algorytmikę:
-Jak, posiadając: zbiór liczb, ilość liczb w pojednyczym zestawie i ilość wszystkich zestawów, rozpisać / poznać najlepszy ich układ tak, by pary wypadały w podobnych ilościach.

Jeśli ktoś z Was miałby trochę czasu do poświęcenia, proszę o pomoc...

[xiikzodz]

To jest zadanie z teorii grafów.

Budujesz graf, którego wierzchołkami są wszystkie możliwe trójki. Wierzchołki łączysz krawędzią wtedy i tylko wtedy, gdy mają dwie wspólne liczby. Wychodzi graf silnie związany (o ile nie izomorficzny, co sobie zaraz sprawdzę - wsiadam na 3-4 godzinki na rower - i po powrocie do domu napiszę) z grafem ścian jakiegoś sympleksu.

Teraz musimy się zdecydować na jakiś precyzyjny opis co to znaczy, że układ jest optymalny. Rozumiem, że chodzi o to, żeby zbiory miały jak najwięcej wspólnego i jednocześnie odchylenie standardowe było małe. Niekoniecznie jest możliwe, a prawdopodobnie w ogóle niemożliwe, zoptymalizowanie obu parametrów, średniej i odchylenia jednocześnie. Musisz więc sprecyzować, co rozumiesz pod pojęciem optymalnego układu.