Расставьте предметы по порядку и дайте каждому номер. Поддерживать счетчик для пользователя, который начинается с нуля. Создать случайный (ish) ключ для каждого пользователя. Выберите функцию, которая отображает комбинацию целого числа в диапазоне 0 ... N и ключа в другое целое число в диапазоне 0 ... N, так что для любого значения вне ключа отображение между целыми числами является биективным. Когда вам нужен элемент, возьмите значение счетчика, пропустите его через функцию вместе с ключом и используйте это число для индексации в списке элементов. Увеличить счетчик.
Все, что вам нужно хранить для каждого пользователя, это ключ и счетчик, и у вас есть гарантия, что ни один элемент не повторится. Это в основном способ построения огромной перестановки на лету.
Проблема, конечно, в выборе функции!
Простым будет f(counter, key) = (counter + key) mod N, и, хотя это сработает, он не будет случайным образом выбирать элементы, поэтому каждый получит элементы в одинаковом порядке, начиная только в разных местах. Если N + 1 простое, вы можете использовать F (счетчик, ключ) = (((счетчик + 1) * (ключ + 1)) mod (N + 1)) - 1, что будет работать довольно хорошо. Если бы диапазон был 0 ... 2 ^ 64, вы могли бы использовать любой блочный шифр, который имеет 64-битный блок, который дал бы отличную рандомизацию. Но не ясно, что вы могли бы адаптировать это к меньшим размерам.
Мне нужно немного покопаться, чтобы посмотреть, смогу ли я придумать универсально применимую функцию. Это проблема, с которой я столкнулся, и было бы здорово, наконец, получить хороший ответ. Я отредактирую этот ответ, если найду что-нибудь.
РЕДАКТИРОВАТЬ: Хорошо, здесь мы идем! Я получил ключевые идеи из нити, которую я начал с sci.crypt , и в частности от одного Пола Рубина, который является универсальным героем Usenet.
Незначительное изменение стратегии. Поместите свои элементы в список, чтобы они могли быть доступны по индексу. Выберите число B, такое, что 2 ^ B> = N - подойдет любое значение, но вы действительно хотите наименьшее (т. Е. Потолок логарифма основания-2 для N-1). Затем мы обозначаем 2 ^ B как M. Установите счетчик, который будет работать от 0 до M-1, и ключ для каждого пользователя, который может быть произвольной строкой байтов - случайное целое число, вероятно, является самым простым. Установите магическую функцию, которая является биекцией, или перестановкой, на множестве целых чисел 0 ... M-1 (см. Ниже!). Когда вы хотите получить элемент, возьмите значение счетчика, увеличьте его, затем введите оригинальное значение через магическую функцию, чтобы получить индекс; если индекс больше, чем N-1, выбросьте его и повторите процесс. Повторяйте до тех пор, пока вы не получите индекс, который меньше, чем N. Иногда вам нужно будет пройти один или несколько бесполезных индексов, прежде чем вы получите хороший, но в среднем это займет M / N попыток, что не так уж плохо (это меньше 2, если вы выбрали наименьший возможный B).
Кстати, вычислить потолок по основанию 2 логарифму числа просто:
int lb(int x) {
int lb = 0;
while (x > 0) {
++lb;
x >>= 1;
}
return lb;
}
Итак, магическая функция, которая отображает число от 0 ... M-1 до другого такого числа. Я упомянул блочные шифры выше, и это то, что мы собираемся использовать. За исключением того, что наш блок имеет длину B бит, которая является переменной и меньше, чем обычные 64 или 128 бит. Поэтому нам нужен шифр, который работает с небольшими блоками переменного размера. Итак, мы собираемся написать наш собственный - слегка несбалансированный шифр Фейстеля переменного размера. Легко!
Чтобы сделать шифр Фейстеля, вам нужно:
- Числа B_L и B_R такие, что B_L + B_R = B. В сбалансированном шифре Фейстеля B_L = B_R, так что B должен быть четным; мы будем использовать B_L = B / 2 и B_R = B - B_L, то есть аналогично сбалансированной сети, но с немного большим B_R, когда B нечетно.
- Количество раундов, называемых C; мы будем считать раунды с i, которые пойдут от 0 до C-1. Мне сказали, что 4 и 10 - абсолютные минимумы, поэтому давайте перейдем к 12, чтобы быть в безопасности.
- Расписание ключей, которое является просто ключом для каждого раунда, каждый из которых называется K_i, и все это происходит от основного ключа, который я упомянул выше. Вы можете просто использовать один и тот же ключ для каждого раунда; правильные шифры имеют некоторый способ генерации подразделов из мастер-ключа. Я бы посоветовал просто соединить число округлений с главным ключом.
- Функция округления, называемая F, которая принимает субблок B_R-бита и ключ округления и создает субблок B_L-бита; в рамках этих ограничений это может быть абсолютно все. Это сердце шифра Фейстеля. Для нас лучший вариант - просто использовать уже существующую криптографическую хеш-функцию, поскольку это просто и надежно. SHA-1 является текущим фаворитом. Мы передадим ему круглую клавишу, затем субблок ввода, вычислим хеш, а затем возьмем биты B_L с одного конца (неважно, какой) в качестве нашего вывода.
Шифр Фейстеля работает так:
- Взять B-битное входное слово
- Для i от 0 до C-1:
- Разделить слово на левый и правый субблоки L и R с битами B_L и B_R соответственно
- Вставьте R и K_i через функцию округления F, чтобы получить значение шифрования X
- Добавить X к L, отбрасывая любой бит переноса, который переполняется из верхнего бита
- Соберите L и R в неправильном направлении, с R слева и L справа, чтобы сформировать новое значение для B
Конечное значение для B является зашифрованным значением и является выводом из шифра. Расшифровать это довольно просто - сделайте вышеописанное в обратном порядке - но так как нам не нужно расшифровывать, не беспокойтесь об этом.
Итак, поехали. Сохраняйте счетчик (и ключ, и значение M), шифруйте его значение с помощью крошечного шифра и используйте результат в качестве индекса. Учитывая, что шифр является перестановкой, легко показать, что это никогда не повторится, что должно радовать ваших клиентов. Еще лучше, учитывая криптографические свойства шифра, вы также можете утверждать, что студенты не смогут предсказать, какой вопрос будет следующим (что, вероятно, не важно, но звучит круто).
Все это немного сложнее, чем просто увеличивать счетчик и приводить в порядок предметы, но это не так сложно. Вы можете сделать это в сотне строк Java. Ну, я могу сделать это в сотне строк Java - я не знаю о вас! :)
Кстати, это будет работать с растущим пулом предметов, при условии, что вы всегда добавляете предметы в конце, хотя он никогда не будет выбирать предметы с номерами выше М. Во многих случаях, тем не менее, это даст вам возможность для роста .