AbstractionТак. Обещанное решение за линейное время.
1. Формулировка задачи.
Поскольку исходная задача особой ясностью не отличилась, я буду иметь наглость додумать детали удобным мне образом. Итак, пусть требуется создать 500 000 (N) разных нумерованных лотерейных билетов. Каждый билет - это шесть (k) неповторяющихся чисел от 1 до 90 (m). Билеты, отличающиеся только порядком чисел, разными не считаются. Требуется, чтобы нельзя было угадать числа на билете, зная его номер и vice versa. Требуется, чтобы для любого билета любые две возможные комбинации номеров встречались с примерно равной вероятностью; желательно, чтобы это не менялось в результате знакомства с любыми иными билетами.
2. Анализ билетов. Сжатие содержания билета до одного числа.
Сколько всего может быть разных билетов? Очевидно, столько, сколько существует способов неупорядоченным образом выбрать k чисел из m без возвращения (т.е. каждое число выбирается не более одного раза):
Таким образом, 500 000 билетов мы наберём без проблем. Теперь вопрос: какова вероятность, что конкретное число (скажем, m) окажется на конкретном билете P(m)? Это отношение числа билетов, на которых оно есть, к числу всех билетов. Но если про билет известно только, что он содержит m, таких билетов столько, сколько было бы билетов с k-1 числом от 1 до m-1; а если билет не содержит m - это то же самое, как если бы мы с самого начала выбирали только числа от 1 до m-1:
Что подводит нас к методу "сжатия" билета до одного числа. Пусть у нас есть одно случайное натуральное число, равномерно распределённое от 1 до
C m k . Если оно не больше
C m-1 k-1 , добавим к билету m и для последующих расчётов уменьшим k на 1; иначе же уменьшим само число на количество "несбывшихся" вариантов
C m-1 k-1 и получим число, равномерно распределённое уже от 1 до
C m-1 k . Код:+
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
static class Combination {
private static uint[,] m_C;
static Combination() {
m_C = new uint[Program.MaxValue+1, Program.NumValues+1];
m_C[0, 0] = 1;
for (int i = 1; i <= Program.NumValues; ++i) m_C[0, i] = 0;
for (int n = 1; n <= Program.MaxValue; ++n) {
m_C[n, 0] = 1;
for (int k = 1; k <= Program.NumValues; ++k) {
m_C[n, k] = m_C[n - 1, k - 1] + m_C[n - 1, k];
}
}
}
public static List<int> GetList(uint seed) {
List<int> ret = new List<int>();
for(int remained = Program.NumValues, current = Program.MaxValue; remained>0; --current) {
if (seed < m_C[current - 1, remained - 1]) {
ret.Add(current);
--remained;
} else {
seed -= m_C[current - 1, remained - 1];
}
}
return ret;
}
public static uint C(int n, int k) { return m_C[n, k]; }
}
3. Обеспечение уникальности и случайности.
Очевидно, различным числам GetList сопоставит различные билеты, но работу мы себе не слишком упростили: теперь надо быть уверенным, что числа будут уникальными. Проще всего, конечно, использовать в качестве числа номер билета, но тогда мы не удовлетворим условиям из пункта 1. Можно начать со случайного 32-разрядного числа seed, в цикле прибавлять к нему некоторое другое случайное
нечётное число и генерировать билет, только если seed меньше
C m k . Несложно доказать, что при этом seed повторит своё значение только через 2
32 итераций, сгенерировав в процессе все возможные билеты. Также, любой один конкретный билет при этом будет совершенно случайным... но уже три билета подряд по-прежнему будут находится в чёткой зависимости.
Симметричный шифр переводит открытый текст (набор байт) в шифртекст такого же размера, причём это преобразование обратимо. То есть, если мы будем шифровать seed некоторым симметричным шифром (со случайным ключом), разным значениям seed всегда будут соответствовать разные результаты шифрования - и, по цепочке, разные билеты. Достаточно хороший шифр также гарантирует практический "разрыв" видимой зависимости между выходным значением и любыми косвенными данными о входном значении. Вот пример шифра, "достаточно хорошего" для этого примера (но не для реальной лотереи!):+
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
class Encryptor {
private UInt64 m_key;
private const int NumRounds = 32;
public Encryptor(UInt64 key) {
m_key = key;
}
private UInt16 KeyPart(int i) {
return (UInt16)((m_key >> ((17*i)%48)) & 0xFFFF);
}
private static UInt16[] permutation1 = { 2, 12, 7, 5, 11, 1, 10, 15, 0, 13, 14, 9, 4, 6, 3, 8 };
private static UInt16[] permutation2 = { 9, 3, 0, 4, 12, 13, 15, 11, 6, 5, 7, 14, 8, 10, 2, 1 };
private UInt16 EncryptionBlock(UInt16 left, UInt16 keyPart) {
UInt16 l = (UInt16)(((left & 0xFF00) + 0x7500) + (keyPart & 0xFF00));
UInt16 r = (UInt16)(((permutation1[(left&0x01E0)>>5]) ^ left) & 0xFF);
l ^= (UInt16)((r<<8)^permutation2[(l&0x3C00)>>10]);
r += (UInt16)(keyPart & 0xFF);
return (UInt16)((l>>8) ^ (r<<8));
}
public UInt32 Encrypt(UInt32 message) {
UInt16 left, right;
left = (UInt16)((message & 0xFFFF0000) >> 16);
right = (UInt16)(message & 0xFFFF);
left ^= KeyPart(0);
right ^= KeyPart(1);
for (int i = 2; i < (NumRounds+2); ++i) {
right ^= EncryptionBlock(left, KeyPart(i));
right ^= left; left ^= right; right ^= left;
}
right ^= left; left ^= right; right ^= left;
left ^= KeyPart(NumRounds+2);
right ^= KeyPart(NumRounds+3);
return ((UInt32)(left) << 16) ^ right;
}
}
4. Складывая всё вместе.
Окончательно, пишем саму программу. Чисто косметическая добавка: поскольку список чисел билета у нас строится от больших к меньшим, его можно бы развернуть перед выводом на печать. Код:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
class Program {
public const int NumValues = 6;
public const int MaxValue = 90;
private const int NumOfTickets = 500000;
static void Main(string[] args) {
int number=1;
Random r = new Random();
Encryptor e = new Encryptor(((ulong)(r.Next())<<32)^((ulong)(r.Next())));
uint seedLimit = Combination.C(MaxValue, NumValues);
for (uint seed = (uint)r.Next(), step = (uint)(r.Next()|1); number <= NumOfTickets; seed += step) {
uint rSeed = e.Encrypt(seed);
if (rSeed >= seedLimit) continue;
List<int> values = Combination.GetList(rSeed);
values.Reverse();
Console.WriteLine(number.ToString("D6") + " - ( "
+ values.Aggregate(string.Empty, (s, i) => s += i.ToString() + " " ) + ")");
++number;
}
}
}
Спасибо за исчерпывающий ответ, НО, у вас написано
1.
Билеты, отличающиеся только порядком чисел, разными не считаются.
А у меня ситуация наоборот, ОНИ БУДУТ считаться РАВНЫМИ
