Положите товары в определенном порядке и дайте каждому номер. Ведите счетчик для пользователя, который начинается с нуля. Создайте случайный (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-битный блок, что даст отличную рандомизацию. Но неясно, что вы могли бы адаптировать это к меньшим размерам.
У меня будет кое-что, чтобы посмотреть, могу ли я придумать универсальную функцию. Это проблема, с которой я столкнулся сам, и было бы здорово наконец получить хороший ответ. Я отредактирую этот ответ, если найду что-нибудь.
EDIT: Хорошо, мы идем! Я получил ключевые идеи от a thread i started on sci.crypt, и, в частности, от одного Пола Рубина, который является универсальным героем Usenet.
Незначительное изменение стратегии. Поместите свои элементы в список, чтобы к ним можно было получить доступ по индексу. Выберем число B, такое, что 2^B> = N - любое значение будет делать, но вы действительно хотите наименьший (то есть потолок логарифма базы-2 N-1). Затем мы ссылаемся на 2^B как M. Установите счетчик, который будет работать от 0 до M-1, и ключ для каждого пользователя, который может быть произвольной байтовой строкой - случайное целое, вероятно, является самым простым. Настройте Волшебную функцию, которая представляет собой биекцию, а также перестановку, на набор целых чисел 0 ... M-1 (см. Ниже!). Когда вы хотите элемент, возьмите значение счетчика, увеличьте счетчик, затем поместите исходное значение через функцию Magic, чтобы получить индекс; если индекс больше N-1, затем выбросьте его и повторите процесс. Повторяйте, пока не получите индекс, который меньше N. Иногда вам нужно пройти один или несколько бесполезных индексов, прежде чем вы получите хороший, но в среднем, это потребует попыток M/N, что не так уж плохо (это меньше 2, если вы выбрали наименьшее возможное значение B).
Кстати, вычисление потолка базы 2 логарифма числа легко:
int lb(int x) {
int lb = 0;
while (x > 0) {
++lb;
x >>= 1;
}
return lb;
}
Итак, Волшебная функция, которая отображает число от 0 ... М-1 к другому такому количеству , Я упомянул блок-шифры выше, и это то, что мы будем использовать. За исключением того, что наш блок имеет длину B бит, который является переменным и меньше, чем обычные 64 или 128 бит. Поэтому нам нужен шифр, который работает на небольших блоках с переменным размером. Таким образом, мы собираемся написать наш собственный - переменный размер слегка несбалансированный Feistel cipher. Легко!
Для шифра Фейстеля, вам необходимо:
- Числа 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 бит с одного конца (неважно, какой) в качестве нашего вывода.
Feistel шифра работает следующим образом:
- Возьмите B-битную входное слово
- Ибо я от 0 до C-1:
- Разделить слово в левый и правый субблоков L и R с битами B_L и B_R соответственно
- Поместите R и K_i через круглую функцию F, чтобы получить значение шифрования X
- Добавить X в L, отбрасывая любые бит переноса, который перетекает из верхней бит
- Сборку L и R. навыворот, с R на левой и L справа, чтобы сформировать новое значение B
Конечное значение для B является зашифрованным значением и является результатом шифрования. Расшифровать его довольно просто - сделайте выше в обратном порядке, но поскольку нам не нужно расшифровывать, не беспокойтесь об этом.
Итак, вы идете. Ведите счетчик (и ключ и значение M), зашифруйте его значение с помощью крошечного шифра и используйте результат как индекс. Учитывая, что шифр является перестановкой, легко показать, что это никогда не повторится, что должно держать ваших клиентов счастливыми. Еще лучше, учитывая криптографические свойства шифрования, вы также можете утверждать, что ученики не смогут предсказать, какой вопрос будет дальше (что, вероятно, не важно, но звучит круто).
Все это немного сложнее, чем просто увеличивать счетчик и давать им предметы по порядку, но это не так сложно. Вы можете сделать это в сотне строк java. Хорошо, i can do it in a hundred lines of java - я не знаю о вас! :)
Кстати, это будет работать с растущим пулом предметов, при условии, что вы всегда добавляете предметы в конце, хотя никогда не будет выбирать предметы с номерами выше M. Во многих случаях, однако, это даст вам немного место для роста.
Оглядываясь назад на этот вопрос, который я задал четыре года назад, я не думаю, что нужно было беспокоиться о необходимости повторить попытку в случае столкновения в ID, хотя некоторые из респондентов предложили способы обойти это. –