random — Pseudorandom Number Generators (Part II)

Purpose: Implement một vài hàm sinh số ngẫu nhiên

Avalable In: Python 1.4 trở lên

Module random cung cấp một bộ sinh số ngẫu nhiên (PRNG - pseudorandom number generator) dựa vào giải thuật Mersenne Twister. Ban đầu được phát triển để sinh ra input cho các mô phỏng Monte Carlo, Mersenne Twister sinh số theo phân phối gần đều (nearly uniform distribution) với period lớn (nếu muốn biết period là gì thì các bạn có thể search Google với từ khóa "The period of a PRNG" nhé ).

Các bạn có thể tham khảo phần I của bài biết về module random ở đây (random — Pseudorandom Number Generators (Part I))

6. Permutations

Mô phỏng game chơi bài cần tráo đều bộ bài, sau đó sẽ chia cho người chơi. Tất nhiên là không sử dụng một con bài nhiều hơn một lần. Nếu sử dụng hàm choice() thì có thể dẫn tới việc một con bài sẽ được chia hai lần. Vậy nên, thay vào đó, ta có thể tráo bộ bài với hàm shuffle() và sau đó loại bỏ các con bài ngay sau khi chúng được chia.

import random
import itertools

def new_deck():
    return list(itertools.product(
        itertools.chain(
            xrange(2, 11), ("J", "Q", "K", "A")
        ),
        ("H", "D", "C", "S"))
    )

def show_deck(deck):
    while deck:
        for j in deck[:13]:
            print "%2s%s" % j,
        print
        deck = deck[13:]

# Get a new deck, with the cards in order
deck = new_deck()
print "Initial deck:"
show_deck(deck)

# Shuffle the deck to randomize the order
random.shuffle(deck)
print "\nShuffled deck:"
show_deck(deck)

# Deal 4 hands of 5 cards each

hands = [[], [], [], []]
for i in xrange(5):
    for h in hands:
        h.append(deck.pop())

# Show the hands
print "\nHands:"
for n, h in enumerate(hands):
    print "%d:" % (n+1),
    for c in h:
        print "%2s%s" % c,
    print

# Show the remaining deck
print "\nRemaining deck:"
show_deck(deck)

Các quân bài được biểu diễn bởi các tuple gồm:

• Diện giá (face value) có các giá trị là 2, 3, 4, 5, 6, 7, 8, 9, 10, "J", "Q", "K", "A"
• Chất (suit) có các giá trị là "H" (Hearts), "D" (Diamonds), "C" (Clubs), "S" (Spades).

$ python random_shuffle.py

Initial deck:
 2H  2D  2C  2S  3H  3D  3C  3S  4H  4D  4C  4S  5H
 5D  5C  5S  6H  6D  6C  6S  7H  7D  7C  7S  8H  8D
 8C  8S  9H  9D  9C  9S 10H 10D 10C 10S  JH  JD  JC
 JS  QH  QD  QC  QS  KH  KD  KC  KS  AH  AD  AC  AS

Shuffled deck:
 4C  5D  JD  2D  4S  QD  3D  KS  5S  3H  QC  7H  KC
 6D  6C  QH  7S  9H 10S  AC  6S 10H  8D  JC  6H  KD
10C  7C  3S  7D  5H  5C  9C  4H  9S  JH  KH  8S  9D
 2C  3C 10D  QS  AD  AH  8H  JS  4D  AS  2S  8C  2H

Hands:
1:  2H  4D  AD  2C  JH
2:  8C  JS  QS  9D  9S
3:  2S  8H 10D  8S  4H
4:  AS  AH  3C  KH  9C

Remaining deck:
 4C  5D  JD  2D  4S  QD  3D  KS  5S  3H  QC  7H  KC
 6D  6C  QH  7S  9H 10S  AC  6S 10H  8D  JC  6H  KD
10C  7C  3S  7D  5H  5C

Có rất nhiều mô phỏng cần lấy mẫu ngẫu nhiên từ tập các giá trị đầu vào. Hàm sample() sinh ra mẫu mà không lặp lại các giá trị và không thay đổi đầu vào. Ví dụ này sẽ in ra một mẫu ngẫu nhiên các từ lấy ra từ một tập từ cho trước.

import random

words = ["A", "An", "And", "B", "Be", "Bed", "C", "Cab", "Cabbage", "D", "Do", "Done", "F", "F*ck", "F*cking"]

for w in random.sample(words, 5):
    print w

Chạy thử chương trình:

$ python random_sample.py

And
Do
F*cking
A
Bed

$ python random_sample.py

Do
Bed
Be
Done
And

7. Multiple Simultaneous Generators

Ngoài các hàm ở cấp độ module (module-level function), random còn cung cấp một class, tên là Random, dùng để quản lý trạng thái nội tại cho nhiều bộ sinh số ngẫu nhiên. Tất cả các hàm đã được đề cập từ đầu đến giờ đều tồn tại dưới dạng phương thức (method) của các instance Random. Và mỗi instance có thể được khởi tạo và sử dụng riêng biệt, không gây nhiễu tới các instance khác.

import random
import time

print "Default initialisation:\n"

r1 = random.Random()
r2 = random.Random()

for i in xrange(3):
    print "%04.3f %04.3f" % (r1.random(), r2.random())

print "\nSame seed:\n"

seed = time.time()
r1 = random.Random(seed)
r2 = random.Random(seed)

for j in xrange(3):
    print "%04.3f %04.3f" % (r1.random(), r2.random())

Chạy thử:

$ python random_random_class.py

Default initializiation:

0.300 0.447
0.632 0.405
0.857 0.053

Same seed:

0.307 0.307
0.452 0.452
0.624 0.624

8. Non-uniform Distributions

Mặc định, hàm random() tuân theo phân phối đều (uniform distribution). Ngoài ra, module random cũng cung cấp các hàm sinh số ngẫu nhiên tuân theo các luật phân phối khác.

Chuẩn (Normmal)

Phân phối chuẩn được sử dụng phổ biến đối với các giá trị liên tục không đều (non-uniform continuous) như là điểm (grade), chiều cao (height), cân nặng (weight),.. Đồ thị hàm mật độ xác suất của phân phối này có hình thù đặc biệt, trông giống như một cái chuông (bell). random có hai hàm để sinh số tuân theo phân phối chuẩn, normalvariate() và gauss() (phân phối chuẩn còn được gọi là phân phối Gauusian).

Một hàm khác là lognorvariate(). Hàm này sinh các giá trị giả ngẫu nhiên mà ở đó, logarit (logarithm) của chúng có phân phối chuẩn. Người ta gọi các giá trị này là tuân theo phân phối loga chuẩn (log-normal distribution).

Tam giác (Triangular)

Phân phối tam giác (triangular distribution) được sử dụng như là một phân phối xác suất xấp xỉ (approximate distribution) khi kích thước mẫu (sample size) nhỏ. Đồ thị hàm mật độ xác suất của phân phối tam giác đạt cực tiểu (low point) tại các giá trị nhỏ nhất và lớn nhất của miền giá trị, đạt cực đại (high point) tại giá trị mode. Chú ý là các giá trị này đều do chúng ta ước lượng và là ba tham số đầu vào của hàm triangular().

Mũ (Exponential)

Hàm expovariate() sinh ra các giá trị tuân theo phân phối mũ (exponential distribution) hữu ích cho việc mô phỏng khoảng thời gian diễn ra giữa hai sự kiện liên tiếp (interarrival time) trong các quá trình Poisson thuần nhất (homogenerous Poisson process). Ví dụ như mô phỏng tốc độ phân rã ánh xạ hay mô phỏng số request gửi tới một web server.

von Mises (The von Mises)

Hàm vonmisesvariate() dùng để sinh ra các giá trị tuân theo luật phân phối von Mises (von Mises distribution). Phân phối này được dùng để tính toán xác suất của các giá trị có tính tuần hoàn như góc (angle), ngày (calendar day) và giờ (time).

Beta (Beta)

Hàm betavariate() sinh ra các giá trị với phân phối Beta (Beta distribution). Phân phối này được sử dụng phổ biến trong thống kê Bayes (Bayesian statistics).

Gamma (Gamma)

Phân phối Gamma (Gamma distribution) được dùng để mô phỏng ước lượng thời gian chờ (waiting time), lượng mưa (rainfall), sai số tính toán (computational error). Phần phối này được dùng bởi hàm gammavariate().

Weibull (Weibull)

Phần phối Weibull (Weibull distribution) được sử dụng trong phân tích lỗi (failure analysis), tính toán độ tin cậy (reliability engineering) và dự báo thời tiết (weather forcasting). Nó là luật phân phối mà hàm weibullvariate() tuân theo.