Есть некоторый массив длины N. Нужно обработать все элементы этого массива в случайном порядке. Первое, что приходит в голову - завести массив индексов и случайным образом перемешать его элементы: Код (Text): indexes = [0, 1, 2, .. N - 1]; for (uint i = 0; i < rand() % N; ++ i) { uint e1 = rand() % N, e2 = rand() % N; uint val; val = indexes[e1]; indexes[e1] = indexes[e2]; indexes[e2] = val; } .. for (uint i =0; i < N; ++ i) { process(arr[indexes[i]]); } Можно перемешать элементы исходного массива, но не оптимально. Какие ещё есть решения?
cupuyc Завести массив для хранения флага о просмотренных элементах, если при генерации очередного случайного числа получается индекс просмотренного элемента, то есть два пути: - ищем первый ближайший не просмотренный (следующий или предыдущий без разницы, но я бы искал ближайший) - генерируем новое случайное число до тех пор, пока не выпадет индекс не просмотренного (чревато)
Если массив каких то структур рациональнее ввести флаг обработки. Сначало проходимся от начала до конца в массиве, везде сбрасываем флаг. Потом обрабатываем до тех пор пока счетчик обработаных структур не будет равен их кол-ву.
очень сомневаюсь, что с флагом будет оптимальнее. в случае с индексами - один раз прошёл по массиву, перемешал. а в случае с флагами бегать придётся довольно часто. выпал совпадающий индекс - снова генерируй значение или беги по массиву и ищи ближайшее. если значений порядка 1000, то в самом конце значения наверняка будут повторяться - придётся бегать по всем 1000 элементам или ~ 1000 раз генерировать случайные значений.
Педивикия подсказывает: "A simple algorithm to generate a permutation of n items uniformly at random without retries, known as the Knuth shuffle, is to start with the identity permutation or any other permutation, and then go through the positions 1 through n−1, and for each position i swap the element currently there with an arbitrarily chosen element from positions i through n, inclusive. It's easy to verify that any permutation of n elements will be produced by this algorithm with probability exactly 1/n!, thus yielding a uniform distribution over all such permutations."
использовать генераторы неповторяющихся последовательностей подходящей длины в качестве рандомайзера? // примеры не нужны сворачивать набор выбора, уменьшая диапазон случайности индексов? int n = N; float m[N] = .... /* заполняем */; for(; n > 0{ rnd_i = rand() % n; // 0 .. (n-1) out << m[rnd_i]; // выводим n--; m[rnd_i] = m[n]; } насколько случайной должна быть очередная выборка?
В этом же разделе недавно обсуждалась тема генерации неповторяющейся случайной последовательности. Таким образом генерация последовательности для N заданных элементов или для некоторого N1<=N с последующей выборкой решает. Мой вариант был использовать реккурентные/другие зависимости имеющие "кольца", но также LFSR имеют это свойство и были еще предложения. В самом простом приближении случайно обработанный элемент просто замещается на последний, таким образом массив уменьшается и не нужно никаких флагов обработки.
Усем прывэд-мидвэд Есть идеальный алгоритм, придумал давно ещё когда программировал на бейсике Микрон. Берём массив последовательных чисел uk[1, 2, 3, 4, ... N] И выбирая из массива число меняем его на последний. Так в массиве будут указатели только не выбраных элементов. Например uk[4]<=uk[последний], понятно однопроходной алгорим и очень быстрый, быстрей не бывает. Если не поняли потом код могу дать.
Вот массив из 5 элементов 1 2 3 4 5 рнд(5)=3 а1=3 1 2 5 4 5 рнд(4)=2 а2=2 1 4 5 4 5 рнд(3)=1 а3=1 5 4 5 4 5 рнд(2)=2 а4=4 5 4 5 4 5 рнд(1)=1 а5=5 Короче в массиве ук находятся указатели на ещё не выбраные элементы, когда выбираем элемент то меняем его на последний. Сама прога на бейсике где то валяется на бумаге, написал алг лет 12 назад. Сначало я смещал весь массив на потом придумал менять последний указатель на выбраный, так быстрей было (бейсик Микрон на партнер 0101 очень медленый), писал прогу для карточной игры какой то.
алгоритмы с O(n^2) не очень хорошая идея. Вот пришла идея такого алгоритма: Код (Text): void random_iterate(int l,int r) { if(l>r) { return; } int m = random(l,r); process(m);/// обрабатываем m-тый элемент массива if(random(1,2)==1) { random_iterate(l,m-1); random_iterate(m+1,r); } else { random_iterate(m+1,r); random_iterate(l,m-1); } } Время работы O(n) стек используется не более чем на n вызовов и то в невероятном случае )
100gold А где тут O(n^2) ? А вот использовать рекурсию, для массивов неизвестной длинны - действительно плохая идея.
Если я правильно помню книгу Гуго Штейнгауза «Задачи и размышления» (давно читал, даже в точности названия не был уверен, пришлось искать), там рассказано про интересную штуку. ω (золотое сечение, иногда φ) обладает занятным свойством: как и все иррациональные числа, будучи умноженным на целые числа, даёт уникальные дробные части произведения; если упорядочить множители по величине дробной части произведения, полученная таблица (называемая «железной») будет таковой, что на эту перестановку стоит посмотреть (к примеру, соседние числа всегда разделены приличным расстоянием; взяв элементы таблицы, принадлежащие отрезку оригинального множества множителей , получим таблицу с такими же свойствами). Моя идея состоит в том, чтобы упорядочить индексы 0…N-1 в соответствии с естественным порядком дробных частей значений ω(seed+i), где seed — ненулевое [псевдо]случайное число, а i — индекс числа. Полученная последовательность и будет искомой. Таким же свойством обладает ω², кстати.
