Równomierny rozkład wylosowanych wartości Opcje

[belwarg]

Witam!
Mam pewien problem i utknąłem w jednym punkcie.

Mam 20 unikalnych wartości (np. id obiektu), każdą z tych wartości muszę wybrać dokładnie 15 razy. Daje mi to 300 elementów do przydzielenia do 60 "kontenerów" (liczba kontenerów jest ustalona z góry).

Każdy kontener ma 8 miejsc, z czego tylko jedno musi być wypełnione, pozostałe miejsca będą wypełniane według podanych parametrów (np. 4 kontenery z 1 elementem, 5 kontenerów z 2 elementami, 7 kontenerów z 3 elementami etc.)

Problem pojawia się w tym punkcie - muszę zadbać o to by rozłożenie elementów do kontenerów było w miarę unikalne tzn. żeby nie było takiej sytuacji że elementy o id=1 oraz id=2, trafią 12 razy do wspólnego kontenera itp.

Wszelkie pomysły jak to rozwiązać mile widziane.

[timon27]

"rozłożenie elementów do kontenerów było w miarę unikalne"

co oznacza 'w miarę'?

jeśli chcesz je losowo rozmieścić w swoich kontenerach:
najpierw mieszamy tablicę:

[PHP] pobierz, plaintext 
for($i=0;$i<60;$i++){
   $losowe[$i]=losuj();
}
$już_wykorzystane[-1]=True;
function losuj(){
   global $już_wykorzystane;
   $los=-1;
   while($już_wykorzystane[$new]){
    $los=mt_rand(0,59)
  }
   $już_wykorzystane[$los]=True;
   return $los;
}
[PHP] pobierz, plaintext 

a potem wrtzucasz w pętlach do kontenerków:

[PHP] pobierz, plaintext 
$licznik=0;
$wielkości_kontenerów=Array(1,1,1,1,2,2,2,2,2,3,3,3,3,3,3,3,.....);
for($i=0;$i<60;$i++){
   for($j=0;$j<$wielkości_kontenerów[$i];$j++){
     $kontener[$i][$j]=$losowe[$licznik];
      $licznik++;
   }
}
[PHP] pobierz, plaintext 

pisałem z ręki więc mogą być błędy, ale idea dobra.

[belwarg]

"rozłożenie elementów do kontenerów było w miarę unikalne"

co oznacza 'w miarę'?

jeśli chcesz je losowo rozmieścić w swoich kontenerach:

Ok, może to troche pomoże - pomyśl o kontenerach jak o zdaniach. Budujemy 60 zdań z 20 słów, każde słowo używamy dokładnie 15 razy, zdanie może mieć od 1 do 8 wyrazów. Ilość zdań o poszczególnej liczbie wyrazów jest znana. Chodzi o to by zdania te nie były do siebie podobne - tzn. chcę uniknąć sytuacji w której stworzy się 15 zdań ze słowami "mały", "kotek" - zamiast tego wolę np. 6 zdań z "mały", "kotek", 4 z "mały", "piesek" i 5 z "mały", "domek".

Umieszczając elementy w kontenerach całkowicie losowo mogę trafić na powtarzające się układy - dlatego muszę jakoś kontrolować ilość powtórzeń wystąpień danych słów z pozostałymi słowami - i to jest główny problem.

Edit:
Wpadłem na taki pomysł:
- na początek w każdym kontenerze umieszczam po jednym elemencie
- tworzę tabelę z trzema kolumnami id1, id2, liczba_powtorzen w której będę zapisywał powtórzenia wystąpień danych elementów w parach (tzn. jeśli elementy o id=1 oraz id=3 są umieszczone razem w konterach 4 i 5 to w tabeli mam 1,3,2)
- zaczynam uzupełnianie kontenerów od tych z największą ilością wolnych miejsc (więcej miejsc - więcej szans na powtórzenia dlatego nimi chcę się zająć w pierwszej kolejności)
- przy uzupełnianiu sprawdzam czy wartość powtórzeń dla wstawianego elementu oraz wszystkich wstawionych już wcześniej elementów w danym kontenerze jest na niskim poziomie (np. nie przekracza wartości 3; jeśli mam kontener z 8 miejscami i 7 z nich jest już zajętych to przy wstawianiu ostatniego elementu wykonuję 7 sprawdzeń).

Zastanawiam się tylko czy to ma prawo zadziałać - czy też przypadkiem nie dojdzie do takiej sytuacji że wstawiając ostatnie elementy z tych 300 dostępnych nie dojdzie do sytuacji w której nie uniknę zwiększenia liczy powtórzeń ponad założony limit. I jeszcze jedna ważna kwestia - jak ustawić limit by był realny.

Ten post edytował belwarg 20.09.2013, 08:28:36