Перебрать все сочетания из N по 2

Без выделения памяти минимум на N(N-1)/2 бит не придумывается.

Твоя задача эквивалентна генерации случайной перестановки 1...N^2 без дополнительной памяти. Если ты хочешь сэмплить равномерно из всего пространства перестановок, то это невозможно сделать с памятью меньше чем O(N^2). Однако, если честность рандома не очень важна, то ты можешь без проблем сэмплить из подмножества. Например, шагая по i+2 (mod N), если N четно. Но я бы не советовал заниматься таким.

В случайном порядке, без повторений

Не совсем понял, но помоему невозможно, и это очевидно. Если ты перебираешь в случайном порядке, то как убедится, что нет повторения? Как ты себе это представляешь?

for i in 1..N
  for j in i..N
    return (i, j)

молниеносный фикс

Оставь любые два пункта

• в случайном порядке
• без повторений
• не выделяя память

Это возможно?

Да. Пусть k — наименьшее натуральное число, такое что 2^k >= N*N. Имея на руках псевдослучайную перестановку k-битных чисел E_k(x), можно сделать цикл от 0 до 2^k - 1, вычисляя y = E_k(x). Частным и остатком вычисляем два числа из y, неподходящие пары отбрасываем.

Повторяться же будут.

x * d + y и y * d + x А чтобы отсечь, нужно запоминать.

Имея на руках псевдослучайную перестановку k-битных чисел E_k(x)

откуда же мы её возмём, если она длиннее чем N*(N-1)/2 ?

если ты вот это имеешь в виду:
http://en.wikipedia.org/wiki/Linear_congruential_generator

то мне непонятно, как программно генерировать a, c для нужного m

Да, можно.

Поскольку результат работы генератора псевдослучайных чисел детерминирован при известном seed, то для каждой пары элементов мы можем в цикле проверять все предыдущие. Нам понадобится только переменная для seed и номера очередной пары.

А чтобы отсечь

Можно затребовать x < y

откуда же мы её возмём, если она длиннее чем N*(N-1)/2 ?

Любой блочный шифр — суть псевдослучайная перестановка. Например AES-128 переводит одно 128-битное число в другое 128-битное. Никаких повторений. Вот уже E_128(x) есть. Нужно просто поднапрячь мозг и выдумать псевдослучайную перестановку для чисел нужной битности.

Если ты перебираешь в случайном порядке, то как убедится, что нет повторения

В псевдосучайном порядке некоторые генерторы случайных гоарнтируют уникальность и полное прохождение всех числе в диапазоне.

Вот уже E_128(x) есть.

мне это много, у меня N ~= 10^10, будет много промахов

значит надо подбирать M, a и c ближе к ~2^64, причем я до запуска не знаю - сколько.

выдумать псевдослучайную перестановку для чисел нужной битности

надо это делать автоматизированно, компьютером, а не мозгом

значит надо подбирать M

Подбери.

причем я до запуска не знаю - сколько.

Подбери несколько функций, по функции на каждое число бит. Это не так много.

надо это делать автоматизированно, компьютером, а не мозгом

Делай это автоматизированно, компьютером, а не мозгом.

Делай это автоматизированно

если делать автоматизированно, то биты уже не при чем.

Берем число S = N*(N-1)/2, ищем M - например следующее простое, большее S. Потом придумываем случайно a и c - они под теорему в любом случае подойдут, если M простое.

проблема в том, что я не знаю, как искать следующее простое, если оно большое. Если M не брать простым, то будут проблемы с выбором a и с

фанатский способ поиска - спрашивать через wget:
http://www.wolframalpha.com/input/?i=next prime 10^20
100000000000000000039

http://stackoverflow.com/questions/10054732/create-a-random-permutation-of-1-...

irreducible polynomial

я не понимаю, как создавать неприводимые многочлены

Я свой нагуглил.