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

#c #алгоритм

Имеется два числа задающих диапазон, нужно в цикле что-то сделать с каждым числом
но не по порядку циклом, а в случайном порядке.
Диапазоны заведомо не известны и являются большими поэтому сложность и потребление
памяти нужны O(1).
Какие алгоритмы/паттерны для этого можно использовать?
    

Ответы

Ответ 1

Набросал код, беглые тесты показывают, что он вроде решает Вашу задачу.
код написан на с99 (то есть, используется объявление переменных не в начале блока),
поэтому в gcc нужно компилировать с -std=c99, студия 2013 может не скомпилировать,
а 2015 скорее всего справиться. Но переписать код не проблема, что бы он работал даже
с древними компиляторами.

Потребление памяти тут точно O(1), так как память выделяется только под всякие локальные
переменные, никаких массивов и скрытых рекурсий.

Самая сложная часть - это поиск шага. Данный алгоритм пытается найти минимальный
шаг. Но в теории там сложность O(n). Данный алгоритм в лоб ищет первое нечетное взаимопростое
с длинной число. Данную часть можно дорабатывать до получения нужных значений.

Если посмотреть визуализацию заполнения, то это будет выглядеть так. Весь диапазон
будет поделен на группы по step и step-1 элементов и вначале будет заполнен каждый
первый элемент в группах, потом каждый второй и так далее. То есть, порядок не случайный,
но достаточно размазаный. Если же хочется немного большей случайности, то следует посмотреть
на Линейный конгруэнтный метод глубже и научиться генерировать для него коэффициенты.

#include 

/* нод, взято с википедии */

int gcd(int a, int b)
{
    while (b != 0)
    {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

/* что то сделать с i */
void doit(int i)
{
    printf("do with %i\n", i);
}

/* включая a и не включая b, то есть [a,b) */
void processrange(int a, int b)
{
    int len = b - a;
    if (len <= 0) {
        return; /* диапазон вырожден*/
    }
    /* поищем хороший шаг */
  /* если такое случиться, что шаг не будет найден, то будет 1 */
    int step = 1;
    for (int i = 3; i < len/2; i+=2) {
        if (gcd(i, len) == 1) {
            step = i;
            break;
        }
    }
  /* собственно цикл */
    int ind = 0;
    for (int i = 0; i < len; i++) {
        doit(a + ind);
        ind = (ind + step) % len;
    }
}

int main(void) {
    processrange(100,200);
    return 0;
}