ngẫu nhiên lấy mẫu tập con độc đáo của một mảng

Question

Nếu tôi có một mảng:

a = [1,2,3] 

Làm thế nào để chọn ngẫu nhiên các tập con của mảng, như vậy mà các phần tử của mỗi tập hợp con là duy nhất? Đó là, cho a các tập con có thể sẽ là:

[] 
[1] 
[2] 
[3] 
[1,2] 
[2,3] 
[1,2,3] 

Tôi không thể tạo ra tất cả các tập con có thể là kích thước thực sự của một là rất lớn vì vậy có rất nhiều, nhiều tập con. Hiện tại, tôi đang sử dụng ý tưởng 'đi bộ ngẫu nhiên' - cho mỗi yếu tố của một, tôi 'lật một đồng xu' và bao gồm nó nếu đồng tiền xuất hiện - nhưng tôi không chắc liệu điều này có thực sự lấy mẫu không gian một cách đồng nhất hay không. Nó cảm thấy như nó thiên vị về phía giữa, nhưng điều này có thể chỉ là tâm trí của tôi làm phù hợp với mô hình, vì sẽ có nhiều khả năng kích thước trung bình.

Tôi có đang sử dụng đúng cách hay không hoặc tôi nên lấy mẫu ngẫu nhiên như thế nào?

(Tôi biết rằng đây là chi tiết của một ngôn ngữ thuyết bất khả tri và 'mathsy' câu hỏi, nhưng tôi cảm thấy nó không thực sự Mathoverflow liệu -. Tôi chỉ cần một câu trả lời thực tế)

Answer 1

Bạn có thể tạo ra các số ngẫu nhiên , chuyển đổi chúng sang nhị phân và chọn các yếu tố từ mảng ban đầu của bạn, nơi các bit là 1. đây là một thực hiện điều này như một con khỉ-vá cho lớp Array:

class Array 
    def random_subset(n=1) 
    raise ArgumentError, "negative argument" if n < 0 
    (1..n).map do 
     r = rand(2**self.size) 
     self.select.with_index { |el, i| r[i] == 1 } 
    end 
    end 
end 

Cách sử dụng:

a.random_subset(3) 
#=> [[3, 6, 9], [4, 5, 7, 8, 10], [1, 2, 3, 4, 6, 9]] 

Nói chung điều này không hoạt động quá tệ, đó là O (n * m) trong đó n là số tập con bạn muốn và m là độ dài của mảng.

Answer 2

a.select {|element| rand(2) == 0 } 

Đối với mỗi phần tử, đồng xu bị lật. Nếu đầu (== 0), thì nó được chọn.

Answer 3

Tôi nghĩ rằng đồng xu lật là tốt.

ar = ('a'..'j').to_a 
p ar.select{ rand(2) == 0 } 

Một mảng có 10 phần tử có 2 ** 10 kết hợp có thể (bao gồm [] và tất cả 10 phần tử) không có gì nhiều hơn 10 lần (1 hoặc 0). Nó tạo ra nhiều mảng hơn bốn, năm và sáu phần tử, bởi vì có rất nhiều phần tử trong phần tử này.

Answer 4

Chỉ cần tiếp tục với ý tưởng "đồng xu lật" ban đầu của bạn. Nó thống nhất lấy mẫu không gian của khả năng.

Nó cảm thấy bạn thích nó thiên vị đối với "trung", nhưng đó là bởi vì số lượng khả năng lớn nhất trong "trung". Hãy suy nghĩ về nó: chỉ có 1 khả năng không có yếu tố, và chỉ có 1 với tất cả các yếu tố. Có N khả năng với 1 phần tử, và N khả năng với các phần tử (N-1). Khi số lượng các phần tử được chọn gần hơn với (N/2), số lượng khả năng phát triển rất nhanh.

Answer 5

Một cách để chọn một yếu tố ngẫu nhiên từ tập điện như sau:

my_array = ('a'..'z').to_a 
power_set_size = 2 ** my_array.length 
random_subset = rand(power_set_size) 
subset = [] 
random_subset.to_i(2).chars.each_with_index do |bit, corresponding_element| 
    subset << my_array[corresponding_element] if bit == "1" 
end 

này sử dụng các chuỗi chức năng thay vì hơn làm việc với "bit" thực sự và hoạt động Bitwise chỉ để thuận tiện cho tôi. Bạn có thể biến nó thành một thuật toán nhanh hơn (tôi đoán) bằng cách sử dụng các bit thực.

Điều đó có nghĩa là mã hóa số mũ array làm số nguyên giữa 0 và 2 ** array.length và sau đó chọn một trong số các số nguyên đó ngẫu nhiên (ngẫu nhiên thống nhất, thực sự). Sau đó, nó giải mã trở lại số nguyên thành một tập hợp con cụ thể của array bằng cách sử dụng bitmask (1 = phần tử nằm trong tập hợp con, 0 = nó không phải là).

Bằng cách này, bạn có bản phân phối đồng đều trên bộ nguồn của mảng.