перетасовка и сохранение ограничений NRooks

Я реализую трассировщик лучей, и я нахожусь в процессе реализации сэмплеров. Сэмплер - это генератор случайных точек над квадратом x = 0: 1, y = 0: 1. Каждый сэмплер содержит несколько наборов «случайных» сэмплов, и каждый набор содержит заданное количество сэмплов.

Теперь один из сэмплеров - это NRooks. Он делит поверхность на nxn блоков, выбирает блоки по диагонали, в каждом диагональном блоке извлекает случайную точку и, наконец, перемешивает сначала x между собой, затем y .

Это все красиво и чисто. Однако, когда пришло время выделить точки, книга, за которой я следую, предлагает эти дополнительные требования для устранения корреляций между последующими пикселями и выборками. Первое требование состоит в том, что каждый раз, когда набор исчерпан, случайным образом выбирается новый набор образцов. Для этого реализован следующий код:

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

где samples - это вектор Point2D размером num_samples * num_sets (он линеаризован). Каждый раз, когда создается один пиксель (количество делится на num_samples), извлекается новый переход, который используется для обозначения линейного массива для начала нового набора.

Поскольку я использую python, моя стратегия использует итераторы:

def __iter__(self):

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

Это тривиально и работает нормально.

Вторая необходимость - перетасовать индексы, и вот где мой вопрос. Книга изменяет код следующим образом

 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]]
 }

, где перетасованные индексы - это массив, вычисляемый следующим образом

 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]);
          }
     }
 }

, который является очень похожим на C ++ способом взять список чисел от 1 до n и перемешать их. Я хотел реализовать следующий код в 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

. Я также мог реализовать случайный итератор, который выполняет итерацию по набору, сохраняя копию списка, но дело не в этом. Мой вопрос возникает из следующей фразы в книге:

... Другая возможность [удалить корреляцию] - это использовать финальную тасование образцов каждого набора, но это нарушает условие n-ладей [...] . Лучший способ - это случайным образом перемешать индексы, используемые в sample_unit_square , для каждого набора, но гарантировать, что используются все образцы.

Я не понимаю: почему он говорит, что последний перемешивается на пробах каждого сета ломает n ладей? Дело в том, что он использует косвенную индексацию в массив точек. Этот косвенный индекс создается путем перемешивания всех индексов от 1 до количества наборов, но это эквивалентно перемешиванию всех выборок в каждом наборе. ИМХО эквивалентно, я не понимаю, почему первая формулировка должна сломать n-ладей, а вторая - нет.

Книга, для протокола, - «Трассировка лучей с нуля» Кевина Сафферна. .