1. Если вы только начинаете программировать на ассемблере и не знаете с чего начать, тогда попробуйте среду разработки ASM Visual IDE
    (c) на правах рекламы
    Скрыть объявление

перебрать элементы массивы случайным образом

Тема в разделе "WASM.A&O", создана пользователем cupuyc, 4 дек 2010.

  1. cupuyc

    cupuyc New Member

    Публикаций:
    0
    Регистрация:
    2 апр 2009
    Сообщения:
    763
    Есть некоторый массив длины N. Нужно обработать все элементы этого массива в случайном порядке.
    Первое, что приходит в голову - завести массив индексов и случайным образом перемешать его элементы:

    Код (Text):
    1. indexes = [0, 1, 2, .. N - 1];
    2.  
    3. for (uint i = 0; i < rand() % N; ++ i)
    4. {
    5.   uint e1 = rand() % N, e2 = rand() % N;
    6.   uint val;
    7.  
    8.   val = indexes[e1];
    9.   indexes[e1] = indexes[e2];
    10.   indexes[e2] = val;
    11. }
    12.  
    13. ..
    14.  
    15. for (uint i =0; i < N; ++ i)
    16. {
    17.   process(arr[indexes[i]]);
    18. }
    Можно перемешать элементы исходного массива, но не оптимально. Какие ещё есть решения?
     
  2. max7C4

    max7C4 New Member

    Публикаций:
    0
    Регистрация:
    17 мар 2008
    Сообщения:
    1.203
    cupuyc
    Завести массив для хранения флага о просмотренных элементах, если при генерации очередного случайного числа получается индекс просмотренного элемента, то есть два пути:
    - ищем первый ближайший не просмотренный (следующий или предыдущий без разницы, но я бы искал ближайший)
    - генерируем новое случайное число до тех пор, пока не выпадет индекс не просмотренного (чревато)
     
  3. cupuyc

    cupuyc New Member

    Публикаций:
    0
    Регистрация:
    2 апр 2009
    Сообщения:
    763
    max7C4, будет более оптимально?
     
  4. sysexit

    sysexit New Member

    Публикаций:
    0
    Регистрация:
    27 авг 2010
    Сообщения:
    176
    Если массив каких то структур рациональнее ввести флаг обработки.

    Сначало проходимся от начала до конца в массиве, везде сбрасываем флаг.

    Потом обрабатываем до тех пор пока счетчик обработаных структур не будет равен их кол-ву.
     
  5. cupuyc

    cupuyc New Member

    Публикаций:
    0
    Регистрация:
    2 апр 2009
    Сообщения:
    763
    очень сомневаюсь, что с флагом будет оптимальнее. в случае с индексами - один раз прошёл по массиву, перемешал. а в случае с флагами бегать придётся довольно часто. выпал совпадающий индекс - снова генерируй значение или беги по массиву и ищи ближайшее. если значений порядка 1000, то в самом конце значения наверняка будут повторяться - придётся бегать по всем 1000 элементам или ~ 1000 раз генерировать случайные значений.
     
  6. sysexit

    sysexit New Member

    Публикаций:
    0
    Регистрация:
    27 авг 2010
    Сообщения:
    176
    Других вариантов я не вижу, кроме названых.
     
  7. reverser

    reverser New Member

    Публикаций:
    0
    Регистрация:
    27 янв 2004
    Сообщения:
    615
    Педивикия подсказывает:
    "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."
     
  8. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    использовать генераторы неповторяющихся последовательностей подходящей длины в качестве рандомайзера?
    // примеры не нужны

    сворачивать набор выбора, уменьшая диапазон случайности индексов?
    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];
    }

    насколько случайной должна быть очередная выборка?
     
  9. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    939
    В этом же разделе недавно обсуждалась тема генерации неповторяющейся случайной последовательности. Таким образом генерация последовательности для N заданных элементов или для некоторого N1<=N с последующей выборкой решает.

    Мой вариант был использовать реккурентные/другие зависимости имеющие "кольца", но также LFSR имеют это свойство и были еще предложения.

    В самом простом приближении случайно обработанный элемент просто замещается на последний, таким образом массив уменьшается и не нужно никаких флагов обработки.
     
  10. baldr

    baldr New Member

    Публикаций:
    0
    Регистрация:
    29 апр 2010
    Сообщения:
    327
    cupuyc,

    «Случайно», или всё-таки «псевдослучайно»?
     
  11. cupuyc

    cupuyc New Member

    Публикаций:
    0
    Регистрация:
    2 апр 2009
    Сообщения:
    763
    baldr, псевдослучайно.
     
  12. Intro

    Intro Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    166
    Усем прывэд-мидвэд ;)
    Есть идеальный алгоритм, придумал давно ещё когда программировал на бейсике Микрон.
    Берём массив последовательных чисел uk[1, 2, 3, 4, ... N]
    И выбирая из массива число меняем его на последний. Так в массиве будут указатели только не выбраных элементов.
    Например uk[4]<=uk[последний], понятно однопроходной алгорим и очень быстрый, быстрей не бывает.
    Если не поняли потом код могу дать. ;)
     
  13. Rockphorr

    Rockphorr Well-Known Member

    Публикаций:
    0
    Регистрация:
    9 июн 2004
    Сообщения:
    2.552
    Адрес:
    Russia
    Intro
    что означает последний ???
     
  14. Intro

    Intro Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    166
    Вот массив из 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 очень медленый), писал прогу для карточной игры какой то.
     
  15. 100gold

    100gold New Member

    Публикаций:
    0
    Регистрация:
    26 фев 2010
    Сообщения:
    165
    алгоритмы с O(n^2) не очень хорошая идея.
    Вот пришла идея такого алгоритма:
    Код (Text):
    1. void
    2. random_iterate(int l,int r)
    3. {
    4.  if(l>r)
    5.  {
    6.   return;
    7.  }
    8.  int m = random(l,r);
    9.  process(m);///  обрабатываем m-тый элемент массива
    10.  if(random(1,2)==1)
    11.  {
    12.   random_iterate(l,m-1);
    13.   random_iterate(m+1,r);
    14.  }
    15.  else
    16.  {
    17.   random_iterate(m+1,r);
    18.   random_iterate(l,m-1);
    19.  }
    20. }
    Время работы O(n) стек используется не более чем на n вызовов и то в невероятном случае )
     
  16. asd

    asd New Member

    Публикаций:
    0
    Регистрация:
    12 мар 2005
    Сообщения:
    952
    Адрес:
    Russia
    100gold
    А где тут O(n^2) ?

    А вот использовать рекурсию, для массивов неизвестной длинны - действительно плохая идея.
     
  17. baldr

    baldr New Member

    Публикаций:
    0
    Регистрация:
    29 апр 2010
    Сообщения:
    327
    Если я правильно помню книгу Гуго Штейнгауза «Задачи и размышления» (давно читал, даже в точности названия не был уверен, пришлось искать), там рассказано про интересную штуку.

    ω (золотое сечение, иногда φ) обладает занятным свойством: как и все иррациональные числа, будучи умноженным на целые числа, даёт уникальные дробные части произведения; если упорядочить множители по величине дробной части произведения, полученная таблица (называемая «железной») будет таковой, что на эту перестановку стоит посмотреть (к примеру, соседние числа всегда разделены приличным расстоянием; взяв элементы таблицы, принадлежащие отрезку оригинального множества множителей :derisive:, получим таблицу с такими же свойствами). Моя идея состоит в том, чтобы упорядочить индексы 0…N-1 в соответствии с естественным порядком дробных частей значений ω(seed+i), где seed — ненулевое [псевдо]случайное число, а i — индекс числа. Полученная последовательность и будет искомой.

    Таким же свойством обладает ω², кстати.