Losowanie bez powtórzeń

Yures

Losowanie liczb w tablicy - Kilka prostych poleceń

W tym artykule postaram się przedstawić oraz w miarę możliwości wyjaśnić działanie poniższego kodu.

Zacznijmy od określenia bloku VAR:

var
Tab :Array [1..10] of Integer; 
Pom :Array [1..22] of Byte;  
Buff :Integer;

W tym miejscu warto objaśnić znaczenie zmiennych :

  • Tablica Tab - Określa ilość liczb które chcemy wylosować.
  • Tablica Pom - Będzie przyjmowała dwa stany 0 i 1 gdzie 0 będzie znaczyło że liczby jeszcze nie wylosowaliśmy, a 1 znaczy że liczbę już wcześniej wylosowaliśmy.
  • Zmienna Buff - Będzie się tam kryła wylosowana liczba.

A teraz przejdźmy do kodu:

Na samym początku musimy wyzerować tablice pom:

For i:=1 to 22 do
    begin
      Pom[i]:=0 ;
    end;

Następnie możemy już losować nasze liczby :

Randomize;  
  For i:=1 to 10 do 
    begin
      Repeat Buff:=Random(22)+1; until (pom[Buff]=0) ;
      Tab[i]:=Buff;          
      pom[buff]:=1 ;        
    end;

Zakres tablicy Pom musi odpowiadać ilości liczb które chcemy losować. Czyli jeżeli chcemy losować spośród 100 liczb tablica ta musi być w zakresie [1..100]

A teraz kilka słów objaśnienia:

Określamy ile liczb wylosujemy, służy do tego pętla for to do. Następnie losowana jest liczba która zostaje zapisana do 'Tymczasowej' zmiennej buff, liczba ta ma swoje miejsce w tablicy pom. Jeśli pom=0 wtedy przypisywana jest liczba w buff do tablicy Tab a tablicy pom o indeksie buff zostaje nadana wartość 1 - co oznacza ze taka liczba została wylosowana. Jeśli na samym początku pom o indeksie buff wynosi 1 wtedy następuje ponowne losowanie i tak do skutku.

W całości nasz program powinien wygladac tak:

program foo;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
Tab :Array [1..10] of Integer;
Pom :Array [1..22] of Integer;
Buff :Integer;
begin
  For i:=1 to 22 do
    begin
      Pom[i]:=0 ;
    end;
  Randomize;
   For i:=1 to 10 do 
    begin
      Repeat Buff:=Random(22)+1; until (pom[Buff]=0) ;
      Tab[i]:=Buff;          
      pom[buff]:=1 ;        
    end;
end.

5 komentarzy

A ja bym sobie wziął np parę kostek do gry i bym sobie porzucał jak się powtórzy to do kosza za karę i juz ...:) he he

Tragiczny artykuł. Żenada. Po co w ogóle pisać o czymś, o czym nie ma się zielonego pojęcia ?

Losowanie bez powtórzeń robi się kompletnie inaczej i wcale do tego nie trzeba tablicy dynamicznej (tzn. można, ale tablica statyczna też jest OK).

Mianowicie, należy za każdym razem zamieniać element już wylosowany z OSTATNIM elementem. Czyli np. jak była tablicy
1 2 3 4 5 6 i wylosowaliśmy trójkę to zamieniamy 1 2 6 4 5 3 i zmniejszamy liczbę n o 1. W ten sposób uzyskamy złożoność liniową, a nie nieskończoną w pesymistycznym przypadku.

Artykuł do poprawienia -.-

bardziej profesjonalne (i bardziej hc ;]) rozwiązania są tutaj: http://4programmers.net/Forum/498550

To jest raczej przykład, jak NIE NALEŻY robić losowania bez powtórzeń. Po pierwsze pesymistyczna złożoność algorytmu dąży do nieskończoności. Kolejne losowania trwają coraz dłużej, a w najgorszym przypadku algorytm wpadnie w nieskończoną pętlę.

Losowanie bez powtórzeń wykonuje się na tablicy dynamicznej, która jest skracana po każdym wylosowaniu.

a po co 2 tablice? Dziwna to metoda.