xáo trộn và bảo vệ ràng buộc NRooks

Question

Tôi đang triển khai trình tạo tia và tôi đang thực hiện việc lấy mẫu. Một sampler là một trình tạo các điểm ngẫu nhiên trên một hình vuông x = 0: 1, y = 0: 1. Mỗi mẫu thử chứa nhiều bộ mẫu "ngẫu nhiên" và mỗi bộ mẫu chứa một số mẫu nhất định.

Bây giờ, một trong những Samplers là NRooks. Nó chia bề mặt trong các khối n x n, chọn các khối dọc theo đường chéo, trong mỗi khối chéo chiết xuất một điểm ngẫu nhiên, và cuối cùng là xáo trộn trước hết các số x trong số đó, sau đó là y.

Tất cả đều đẹp và sạch sẽ. Tuy nhiên, khi đó là lúc để trích xuất các điểm, cuốn sách tôi đang đề xuất sau đây đề xuất các yêu cầu bổ sung này để phá vỡ mối tương quan giữa các pixel và mẫu thử tiếp theo. Yêu cầu đầu tiên là mỗi khi một tập hợp hết, một bộ mẫu mới được chọn ngẫu nhiên. Mã thực hiện để đạt được điều này là như sau:

Point2D Sampler::sample_unit_square(void) { 
    if (count % num_samples == 0) jump = (rand_int() % num_sets) * num_samples; 
    return (samples[jump + count++ % num_samples] 
} 

nơi samples là một vector của Point2D kích thước num_samples*num_sets (nó là tuyến tính). Mỗi khi một điểm ảnh được thực hiện (đếm là chia hết cho num_samples) một bước nhảy mới được trích xuất và được sử dụng để chỉ ra mảng tuyến tính cho sự bắt đầu của một tập mới.

Kể từ khi tôi đang sử dụng python, chiến lược của tôi tận dụng vòng lặp:

def __iter__(self): 

    while True: 
     for sample_set in random.choice(self._samples_sets): 
      for sample in sample_set: 
       yield sample 

Đây là tầm thường, và hoạt động ok.

Nhu cầu thứ hai là trộn các chỉ mục và đây là câu hỏi của tôi. Cuốn sách điều chỉnh lại đoạn code như sau

Point2D Sampler::sample_unit_square(void) { 
    if (count % num_samples == 0) jump = (rand_int() % num_sets) * num_samples; 
    return (samples[jump + shuffled_indices[ jump + count++ % num_samples]] 
} 

nơi chỉ số xáo trộn là một mảng tính như sau

void Sampler::setup_shuffled_indices(void) { 
    shuffled_indices.reserve(num_samples*num_sets); 
    vector<int> indices; 

    for (int j=0; j<num_samples; j++) indices.push_back(j); 

    for (int p=0; p<num_sets; p++) { 
      random_shuffle(indices.begin(), indices.end()); 
      for (int j=0; j<num_samples; j++) { 
       shuffled_indices.push_back(indices[j]); 
      } 
    } 
} 

mà là một rất C++ cách tham gia một danh sách các số từ 1 đến n và xáo trộn chúng. Tôi muốn triển khai mã sau đây trong python

def __iter__(self): 

    while True: 
     sample_set = random.choice(self._samples_sets): 
     shuffled_set = sample_set[:] 
     random.shuffle(shuffled_set) 
     for sample in shuffled_set: 
      yield sample 

Tôi cũng có thể thực hiện một trình lặp ngẫu nhiên lặp lại trên tập hợp, lưu bản sao danh sách, nhưng đây không phải là vấn đề. Câu hỏi của tôi phát sinh từ cụm từ sau trong cuốn sách:

... Một khả năng khác để loại bỏ mối tương quan là sử dụng lệnh ngẫu nhiên trên mỗi mẫu, nhưng điều này phá hủy điều kiện n-rooks [. ..]. Cách tốt nhất là trộn ngẫu nhiên các chỉ mục được sử dụng trong sample_unit_square, cho mỗi bộ, nhưng đảm bảo rằng tất cả các mẫu được sử dụng.

Điều tôi không hiểu là: tại sao nó nói rằng sự xáo trộn cuối cùng trên các mẫu của mỗi bộ vi phạm các n-rook? vấn đề là anh ta đang sử dụng lập chỉ mục gián tiếp vào mảng các điểm. Chỉ số gián tiếp này được tạo ra từ sự xáo trộn của tất cả các chỉ số từ 1 đến số bộ, nhưng điều này tương đương với sự trộn lẫn trên tất cả các mẫu trong mỗi bộ. Là IMHO tương đương, tôi không thấy lý do tại sao công thức đầu tiên nên phá vỡ n-rooks và tại sao thứ hai sẽ không.

Cuốn sách, để ghi lại, là "Ray truy tìm từ mặt đất lên", bởi Kevin Suffern.

Answer 1

Có vẻ với tôi như

... sử dụng một shuffle cuối cùng về các mẫu của mỗi bộ ..

là gợi ý để shuffle mỗi thiết lập một cách độc lập sau khi bộ đang xáo trộn.

def __iter__(self): 

    while True: 
     for sample_set in random.choice(self._samples_sets): 
      for sample in random.choice(sample_set): 
       yield sample 

Như vậy. Tôi không phải là một chuyên gia Python để tha thứ cho bất kỳ lỗi mã nào. Điều này sẽ phá vỡ n-rooks, mặc dù nó chỉ đơn giản là một ý tưởng tồi. Nó phụ thuộc vào những gì bạn đang đi.