Algorytmy i Struktury Danych - Generowanie liczb pseudolosowych

Zadanie mieszania, tasowania (ang. shuffle, hashing) zawartości tablicy sprowadza się do wykonywania w pętli zamiany miejscami dwóch elementów tablicy o wylosowanych indeksach. Pętla musi być wykonana tyle razy, aby tasowanie objęło wszystkie elementy – w praktyce wystarcza ilość wykonań równa 3n, gdzie n jest ilością elementów.

Algorytm mieszania pseudolosowego

Wejście:

n : liczba elementów w tablicy, n ∈ N.
Z : tablica elementów, indeksy rozpoczynają się od 0.

Wyjście:

Tablica Z z potasowaną zawartością.

Elementy pomocnicze:

i : licznik obiegów pętli. i ∈ N.
x : przechowuje element tablicy Z przy zamianie zawartości. Typ ten sam, co elementy tablicy Z.
losowa(x) : funkcja zwracająca liczbę pseudolosową z zakresu od 0 do x - 1.

Lista kroków:

K01: Dla i = 1, 2, …, 3n: ; tasowanie wykonujemy w pętli
     wykonuj kroki K02…K07
K02:   i₁ ← losowa(n) ; losujemy pierwszy indeks
K03:   i₂ ← losowa(n) ; losujemy drugi indeks
K04:   x ← Z[i₁] ; zamieniamy miejscami Z[i₁] i Z[i₂]
K05:   Z[i₁] ← Z[i₂]
K06:   Z[i₂] ← x
K07: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program tasuje tablicę 10 elementów całkowitych o kolejnych wartościach od 0 do 9. Tablica jest najpierw wyświetlana przed tasowaniem, a następnie po tasowaniu.

Pascal

// Pseudolosowe tasowanie
// Data:   20.04.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

var Z : array [0..9] of integer = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
    i1, i2, i, x : integer;

begin
  randomize;
  for i := 0 to 9 do
    write(Z[i], ' ');
  writeln;
  for i := 1 to 30 do
  begin
    i1 := random(10);
    i2 := random(10);
    x  := Z[i1]; Z[i1] := Z[i2]; Z[i2] := x;
  end;
  for i := 0 to 9 do
    write(Z[i], ' ');
  writeln;
end.

C++

// Pseudolosowe tasowanie
// Data:   20.04.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
  int Z[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  int i1, i2, i, x;

  srand ((unsigned) time(NULL));
  for(i = 0; i < 10; i++)
    cout << Z[i] << " ";
  cout << endl;
  for(i = 1; i <= 30; i++)
  {
    i1 = rand() % 10;
    i2 = rand() % 10;
    x  = Z[i1]; Z[i1] = Z[i2]; Z[i2] = x;
  }
  for(i = 0; i < 10; i++)
    cout << Z[i] << " ";
  cout << endl;
  return 0;
}

Basic

' Pseudolosowe tasowanie
' Data:   20.04.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Dim Z (9) As Integer => {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Dim As Integer i1, i2, i

Randomize Timer
For i = 0 To 9
  Print Z(i);
Next
Print
For i = 1 To 30
  i1 = Int(Rnd*10)
  i2 = Int(Rnd*10)
  Swap Z(i1), Z(i2)
Next
For i = 0 To 9
  Print Z(i);
Next
Print
End

Python (dodatek)

# Pseudolosowe tasowanie
# Data:   17.02.2024
# (C)2020 mgr Jerzy Wałaszek
# ---------------------------

import random

z = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in range(10):
    print(z[i], end=" ")
print()
for i in range(30):
    i1 = random.randrange(0, 10)
    i2 = random.randrange(0, 10)
    z[i1], z[i2] = z[i2], z[i1]
for i in range(10):
    print(z[i], end=" ")
print()

Wynik:

0 1 2 3 4 5 6 7 8 9
7 2 3 1 6 4 0 9 5 8

do podrozdziału do strony

Zadanie losowania bez powtórzeń można rozwiązać na kilka różnych sposobów. Jeśli przedział <a, b> jest mały (np. zawiera 80 kolejnych liczb Multi-Lotka), to możemy go odwzorować w tablicy, następnie zawartość tej tablicy potasować poprzednio podanym algorytmem i jako wynik zwrócić pierwsze n elementów. Tasowanie nie dubluje elementów tablicy, zatem otrzymamy n liczb bez powtórzeń. Taki algorytm posiada klasę złożoności obliczeniowej O(n).

Jeśli przedział <a, b> jest bardzo duży, a n stosunkowo małe, to postępujemy w sposób następujący. Przygotowujemy pustą tablicę o n elementach. Losujemy liczbę pseudolosową. Jeśli wylosowana liczba jest już w tablicy, to losujemy ponownie dotąd, aż wylosowanej liczby nie będzie w tablicy. Liczbę dopisujemy do tablicy. Jeśli tablica jest zapełniona, kończymy. W przeciwnym razie powtarzamy losowanie. Algorytm w takiej postaci posiada optymistyczną klasę złożoności obliczeniowej O(n²).

Algorytm losowania bez powtórzeń

Wejście:

n : liczba określająca, ile liczb pseudolosowych bez powtórzeń należy wylosować, n ∈ N.
a, b : liczby określające całkowity przedział losowania, b-a ≥ n, a, b ∈ C.

Wyjście:

n różnych od siebie liczb pseudolosowych z przedziału <a, b>

Elementy pomocnicze:

T : tablica przechowująca wylosowane liczby pseudolosowe. Indeksy od 0 do n-1.
i : licznik wylosowanych liczb pseudolosowych. i ∈ N.
j : wykorzystywane do przeszukiwania tablicy T. j ∈ N.
x : wylosowana liczba pseudolosowa.
losowa(x) : funkcja zwracająca liczbę pseudolosową z zakresu od 0 do x-1.

Lista kroków:

K01: Dla i = 0, 1, …, n-1:
     wykonuj kroki K02…K06
K02:   x ← a+losowa(b-a+1) ; losujemy liczbę pseudolosową
K03:   Dla j = 0, 1, …, i-1: ; sprawdzamy, czy wylosowana
       wykonuj krok K04 ; liczba jest w T
K04:     Jeśli T[j] = x, ; jeśli tak, powtarzamy losowanie
         to idź do kroku K02
K05:   T[i] ← x ; jeśli nie, zapamiętujemy w T wylosowaną liczbę
K06:   Wyprowadź x ; wyprowadzamy liczbę na wyjście
K07: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

W pierwszym wierszu program odczytuje trzy liczby: a, b – krańce przedziału, n – ilość liczb pseudolosowych do wylosowania. Jeśli długość przedziału <a, b> pozwala na wygenerowanie zadanej ilości różnych liczb pseudolosowych, to program je generuje i wyświetla w następnym wierszu. W przeciwnym razie wypisuje odpowiedni komunikat.

Pascal

// Losowanie bez powtórzeń
// Data:   20.04.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

type Tintarray = array of integer;

var a, b, i, j, n, x : integer;
    T    : Tintarray;
    test : boolean;
begin
  randomize;
  readln(a, b, n);
  if n <= b-a+1 then
  begin
    setlength(T, n);
    for i := 0 to n-1 do
    begin
      repeat
        test := true;
        x := a+random(b-a+1);
        for j := 0 to i-1 do
          if T[j] = x then
          begin
            test := false;
            break;
          end;
      until test;
      T[i] := x;
      write(x, ' ');
    end;
  end
  else
    writeln('n jest za duze!');
  writeln;
end.

C++

// Losowanie bez powtórzeń
// Data:   20.04.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
  int a, b, i, j, n, x, *T;
  bool test;

  srand(time(NULL));
  cin >> a >> b >> n;
  if(n <= b-a+1)
  {
    T = new int[n];
    for(i = 0; i < n; i++)
    {
      do
      {
        test = true;
        x = a+rand()%(b-a+1);
        for(j = 0; j < i; j++)
          if(T[j] == x)
          {
            test = false;
            break;
          }
      } while(!test);
      T[i] = x;
      cout << x << " ";
    }
    delete [] T;
  }
  else
    cout << "n jest za duze!\n";
  cout << endl;
  return 0;
}

Basic

' Losowanie bez powtórzeń
' Data:   20.04.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Dim As Integer a, b, i, j, n, x, test

Randomize Timer
Input a, b, n
If n <= b-a+1 Then
  Dim T(n-1) As Integer
  For i = 0 To n-1
    Do
      test = 1
      x = a+Int(Rnd*(b-a+1))
      For j = 0 To i-1
        If T(j) = x Then
          test = 0
          Exit For
        End If
      Next
    Loop Until test = 1
    T(i) = x
    Print x;
  Next
Else
  Print "n jest za duze!"
End If
Print
End

Python (dodatek)

# Losowanie bez powtórzeń
# Data:   17.02.2024
# (C)2024 mgr Jerzy Wałaszek
# ---------------------------

import random

arr = input().split()
a = int(arr[0])
b = int(arr[1])
n = int(arr[2])
if n <= b-a+1:
    t = []
    for i in range(n):
        while True:
            test = True
            x = random.randrange(a, b+1)
            for j in range(i):
                if t[j] == x:
                    test = False
                    break
            if test: break
        t.append(x)
        print(x, end=" ")
else:
    print("n jest za duże!")
print()

Wynik:

1 80 20
39 79 12 38 80 3 11 33 9 76 19 21 8 14 37 29 24 71 50 1

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Generowanie liczb pseudolosowych

Problem

Mieszanie pseudolosowe

Algorytm mieszania pseudolosowego

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Problem

Losowanie bez powtórzeń

Algorytm losowania bez powtórzeń

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy