Có thể giảm xuống còn bao nhiêu phần tử nữa mà vẫn lưu trữ đủ danh sách N số đã được sinh ngẫu nhiên

#1

Mình vô tình thấy câu đố này, mọi người cũng giải quyết cùng mình xem sao?

Cần sinh ngẫu nhiên N phần tử có giá trị từ 0 đến (N-1). Vấn đề là khi dùng hàm sinh ngẫu nhiên có thể sinh ra một số đã được sinh ở lần trước, khi đó lại gọi hàm ngẫu nhiên cho đến khi nào sinh được một phần tử không nằm trong danh sách đã sinh ra trước đó.
Vậy cần có một mảng lưu danh sách các phần tử đã được sinh, mảng này nếu khai báo thông thường thì phải chứa N phần tử.

Chẳng hạn cần sinh ngẫu nhiên 6 phần tử từ 0 đến 5; để biết đã sinh được bao nhiêu phần tử thì ta cần một mảng có 6 phần tử. Lý do dùng mảng chứ không dùng danh sách liên kết vì tốc độ truy cập của mảng nhanh chóng hơn DSLK nhiều.

Câu hỏi, mảng này có thể giảm xuống còn bao nhiêu phần tử nữa mà vẫn lưu trữ đủ danh sách N số đã được sinh ngẫu nhiên.

2 Likes
#2

Hi BK Anonymous.
Theo mình câu trả lời trong câu hỏi của bạn rồi. “bao nhiêu phần tử nữa mà vẫn lưu trữ đủ danh sách N số”. Còn bài toán sinh ngẫu nhiên N phần tử có giá trị từ 0 đến N-1 thì chỉ cần gọi N-1 lần.

5 Likes
#3

Như kiểu chia bài (Tây) cho các người chơi?

4 Likes
#4

Đố vui thì phải có thưởng. Không biết Nobita có quà gì không. :smiling_imp:

6 Likes
#5

Chỉ còn 1 phần tử.

Một tập N số từ 0 đến một sẽ bao gồm X hoán vị từ (0, 1, 2, …, N-1) đến (N-1, N-2, …, 1, 0). Mỗi hoán vị được đánh dấu bằng 1 index.

Vậy khi biết index, ta sẽ biết được đầy đủ cấu hình hoán vị.
Dạng đầy đủ, mảng sẽ gồm 3 phần tử: [min, max, index]

5 Likes
#6

O(1) mem đây :V
https://preshing.com/20121224/how-to-generate-a-sequence-of-unique-random-integers/
tuy nhiên đây là cho N = 2^32

nếu N ~ 2^64 thì xài 1 cái block cipher nào đó, vd Blowfish với i là số 64-bit, id(i) = encrypt(key, i) cũng sẽ cho ra 1 số 64-bit, và 2 số này có mối quan hệ 1-1 (vì decrypt(id(i)) = i), nghĩa là 2^64 số input sẽ cho ra 2^64 số output khác nhau đôi một => với mỗi key khác nhau sẽ cho ra permutation khác nhau…

N~ 32-bit cũng có thể xài Skip32 block “cipher” để tạo số ngẫu nhiên ko trùng lặp: https://wiki.postgresql.org/wiki/Skip32_(crypt_32_bits)

It may be used to generate series of unique values that look random, or to obfuscate a SERIAL primary key without loosing its unicity property.

N~16 bit thì trong link của preshing.com ở trên có đề cập tới implementation của OpenBSD: http://static.usenix.org/event/usenix99/full_papers/deraadt/deraadt_html/node17.html, (có lẽ dùng để tạo ngẫu nhiên process id là 1 số 16 bit???)

N ~ 128-bit thì xài AES :V :V

với N bất kì :V :V thì theo link này có thể tạo 1 Feistel cipher với số bit nhỏ nhất lớn hơn N, ví dụ N=8 thì xài 3-bit, N=9 thì xài 4-bit, rồi bỏ những giá trị lớn hơn N là được (xài cycle walking như trong cái link format preserving encryption)



ví dụ 1 áp dụng :V

edit: chả liên quan gì tới C/C++ :V :V :V

6 Likes
#7

=)), nghèo lắm, lướt mạng nên thấy tò mò thui mà

1 Like
#8

Mình chưa đọc hết các link bạn gửi, nó liên quan đến C/C++ ở đây, theo mình hiểu là vấn để tạo mạng hoặc cấp phát bộ nhớ như thế nào thôi.

Và đây là đáp án sơ bộ mà mình thấy người ta ghi ra.

Mình vẫn chưa giải thích được cái đáp án này:

image

Mình thấy mấy cái link bạn gửi thì phần lớn là can thiệp vào “thuật toán sinh ngâu nhiên nhiều hơn”

3 Likes
#9

vậy với 1 hoán vị 1 2 3, 1 3 2 thì ý nghĩa của nó là gì?

Mình thấy nếu chuyển từ “index” sang binary thì sẽ rõ ý tưởng của bạn hơn.

Chẳng hạn với n = 3 (phần từ 0 1 2)

index = 0, tương ứng 0 0 0, chưa có phần từ nào
index = 1, 0 0 1, phần tử có giá trị = 0 đã có
index = 2, 0 1 0, phần tử có giá trị = 1 đã có
index = 3, 0 1 1, phần tử có giá trị = 0 và 1 đã có
index = 4, 1 0 0, phần tử có giá trị = 2 đã có
index = 5, 1 0 1, phần tử có giá trị = 2 và 0 đã có
index = 6, 1 1 0, phần tử có giá trị = 2 và 1 đã có
index = 7, 1 1 1, phần tử có giá trị = 2 và 1 và 0 đã có

#10

thì tại lưu trữ N phần tử để tạo số ngẫu nhiên ko trùng nhau mà. Mà để tạo số ngẫu nhiên ko trùng nhau thì có thể ko cần cái mảng lưu trữ N phần tử kia, nên mảng đó có thể giảm xuống còn 0 luôn :V :V

mà N/10 N/64 là sao đây =] Số 10 ở đâu ra??? Số 64 ở đâu ra :V :V :V Có lẽ là muốn lưu về dạng bit field, mỗi phần tử chỉ còn 1 bit => thay vì lưu N số 64-bit thì lưu còn N bit ~ giảm 64 lần :V Mà N 64 bit thì mảng phải tới ~ 2^64 phần tử làm gì mảng nào chứa nổi :V Nên số 64 ở đây chắc bịa à :V

mà bit field thì cũng chả liên quan gì tới C/C++ @_@

4 Likes
#11

bài gốc nó ở đây here

#12

vậy là người đó tự chế đáp án à =]

N/10 với N/64 thì khác gì N mà giảm :V Thế ban đầu lưu N số 1000 bit thì lại giảm được còn N/1000 à =]

rất tiếc là chương trình của ta sử dụng rất nhiều bộ nhớ và khi mảng có từ 128 phần tử trở lên thì chương trình lăn đùng ra chết không hiểu tại sao

oát đờ heo =]]

5 Likes
#13

Nope!

Giả sử ta có 4 số 1, 2, 3, 4
các hoán vị bao gồm
0: 1234
1: 1243
2: 1324
3: 1342
4: 1423
5: 1432
6: 2134
…
22: 4312
23: 4321

Vậy ta có [1, 4, 5] = 1432

Edit:
Cách để xác định một hoán vị dựa theo index
Giả sử ta có các mảng [1, 5, 61]
Như vậy các thành phần cấu thành mảng là a = [1, 2, 3, 4, 5] và index = 61

Có 5 ký tự, vậy sẽ có 1x2x3x4 = 24 hoán vị bắt đầu bằng 1, 24 bắt đầu bằng 2, 24 bắt đầu bằng 3…
61/24 = 2 => ký tự đầu tiên là a[2] = 3;

61%24 = 13
Còn lại 4 ký tự là b = [1, 2, 4, 5] và index = 13

Có 6 hoán vị bắt đầu bằng 1, 6 hoán vị bắt đầu bằng 2…
13/6 = 2 => ký tự thứ 2 là b[2] = 4
13%6 = 1

1/2 = 0 => ký tự thứ 3 là c[0] = 1
1%2 = 1

1/1 = 1 => ký tự thứ 4 là d[1] = 5
ký tự thứ 5 là 2

Vậy [1, 5, 61] = 34152

4 Likes
#14

làm vậy với n lớn thì có n! index, lưu số bự cỡ n! cũng đâu thể tính là lưu 1 số :V Ăn gian :V

4 Likes
#15

Bổ sung cách tính đó, chứ đâu có điên lưu hết n! cấu hình :joy:

3 Likes
#16

Lí do vì sao lại hỏi số phần tử :smiley:

#17

vậy ví dụ N=100, muốn random ra cấu hình 99, 98, 97, …, 3, 2, 1, 0 thì lưu index mấy? :V Có phải là index 100! - 1 ko? Làm sao lưu được số này :V

6 Likes
#18

Ừ nhể, quên vụ đó. Cơ mà cái vụ N/64 ấy, tức là dùng kiểu dữ liệu khác lớn hơn để lưu lại thành mảng ít phần tử hơn. Thế thì cũng chả ra làm sao cả, dùng luôn cái mảng 1 phần tử (json string) lưu lại luôn, chẳng qua 1 phần tử nó hơi to :smile:

Còn nếu mà bắt buộc là int thì mình nghĩ cách của mình là ổn, cũng chỉ là “có thể giảm” chứ không “chắc chắn giảm” =]]

4 Likes
#19

thì vậy, nghe chém N/64 ko biết tác giả đào số 64 ở đâu ra :V :V

nếu xét về lý thuyết thì chém gió giảm còn 1 phần tử cũng được mà =]]

4 Likes
#20

chắc tác giả mới vọc hay sao ấy :V Ko hỏi kích cỡ bộ nhớ mà chỉ hỏi số phần tử thì chém gió 1 phần tử index của N! cũng đc kìa =]]

5 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?