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.

[flashdev]

Kod

var uniqNum = 20;
var times = 15;

var res = [];

var shuffle = function(arr){
  return arr.sort(function(){
    return Math.random()*2&1;
  });
};

for (var i = 0; i < uniqNum; ++i) {
  var j = times;
  do {
    res.push(i);
  } while (--j);
}

res = shuffle(res);
console.log(res.join(','));

Kod

10,19,19,0,19,0,19,0,0,19,0,19,0,19,19,1,1,1,19,1,18,18,1,18,18,1,1,1,1,18,18,2,
18,2,18,18,17,17,2,17,17,2,17,2,2,17,16,16,3,3,16,16,16,3,16,3,16,16,16,16,4,4,4
,
15,4,15,15,15,4,4,4,15,15,4,4,5,15,5,15,14,5,14,5,5,5,14,5,5,5,14,14,14,6,14,6,6
,
6,13,13,13,6,6,6,13,13,7,7,13,13,7,13,12,12,12,12,7,12,7,12,7,8,12,11,11,8,11,8,
8
,8,11,8,11,8,11,8,11,11,10,9,10,10,10,9,9,9,9,14,9,9,9,0,10,10,0,10,9,10,19,0,10
,
9,0,19,10,10,11,18,18,18,1,11,11,1,11,1,2,8,8,8,8,2,12,7,12,7,7,17,12,12,17,12,2
,
17,12,7,13,2,17,3,13,13,3,13,7,16,16,6,13,3,3,3,6,6,3,6,5,3,14,5,4,14,5,14,9,4,5
,
4,15,15,2,0,0,0,19,4,0,15,0,1,9,11,8,16,8,11,6,8,6,18,7,6,7,3,17,13,13,17,17,18,
4
,15,7,10,15,10,9,19,4,12,2,6,16,2,14,11,14,1,18,14,17,3,3,15,3,19,1,16,12,19,10,
2
,9,17,5,7,2,15,9,5,14

Ten post edytował flashdev 19.09.2013, 17:07:58

[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