массив чисел от 1 до ? в случайном порядке

Тема в разделе "WASM.BEGINNERS", создана пользователем cornolio, 10 дек 2009.

  1. gEnIuS_99

    gEnIuS_99 New Member

    Публикаций:
    0
    Регистрация:
    3 дек 2009
    Сообщения:
    28
    А как насчет маленьких комментариев, что это за циферки такие? А так имхо ваш код никто не прочитает, разве что какой-нибудь безумец скопирует его себе к остальным макросам и запустит.
     
  2. Ustus

    Ustus New Member

    Публикаций:
    0
    Регистрация:
    8 авг 2005
    Сообщения:
    834
    Адрес:
    Харьков
    gEnIuS_99
    В принципе, да, но есть сомнения в равномерности распределения... хотя по идее должно быть равномерно... надо теорию думать, а мне сейчас лень, да и некогда, может через несколько дней посмотрю.
    Вообще истинно правоверный матановский способ - сгенерить число в диапазоне [0, N!-1] и сконструировать соответствующую перестановку. Для N <= 12 расчеты элементарные, дальше надо оптимизить.

    MEPOX
    Ну это нормальный рефлекс минимально опытного человека на слово сортировка :)
    Кстати это среднее значение, может быть и значительно хуже.
     
  3. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    Ustus
    Вообще сложность была упомянута в контексте задачи, а не алгоритма. Если в качестве алгоритма брать всякий ширпотреб, то ясно дело, что можно и в среднем кубическую, например, сложность сбацать.
     
  4. gEnIuS_99

    gEnIuS_99 New Member

    Публикаций:
    0
    Регистрация:
    3 дек 2009
    Сообщения:
    28
    А что, уже быстрее придумали?
     
  5. Ustus

    Ustus New Member

    Публикаций:
    0
    Регистрация:
    8 авг 2005
    Сообщения:
    834
    Адрес:
    Харьков
    gEnIuS_99
    Не в том смысле, что придумали, а в том смысле, что алгоритм сортировки (при благоприятном расположении звезд, то бишь элементов в массиве) может отработать и быстрее. А может и медленнее. O(N*Log(N)) - это средняя температура по больнице. Однозначно можно сказать, что быстрее O(N) оно точно не будет. :)
     
  6. litrovith

    litrovith Member

    Публикаций:
    0
    Регистрация:
    20 июн 2007
    Сообщения:
    509
    gEnIuS_99,

    random_seed = 0
    macro random_byte
    { if random_seed ; Если random_seed сгенерен, то ессно генерить его не нуна
    else
    random_seed=%t ; Иначе получаем 'типа' 'timestamp_id'
    end if
    ; Эти циферки - 'Минимальный генератор Парка-Миллера'
    random_seed=(random_seed-random_seed/1F31Dh*1F31Dh)*41A7h-random_seed/1F31Dh*0B14h
    _random_byte=(random_seed-random_seed/186A0h*186A0h) and 0FFh }


    Стараюсь изо всех сил ;) !
     
  7. luckysundog

    luckysundog New Member

    Публикаций:
    0
    Регистрация:
    28 окт 2008
    Сообщения:
    106
    так-то оно всё правильно, но когда период маленький - как ни крути, числа в итоге получаются не очень качественные... закономерность прослеживается. числа будут с разницей < m. вот почему у стандартного rand() период аж 2^32 (в нем кстати тоже LCG). а когда число, полученное таким генератором, взять еще по маленькому модулю m, получается та самая желаемая псевдослучайность :)

    поэтому надо LCG с периодом значительно больше m, плюс надо как-то контролировать его поведение, чтобы числа были уникальные. я пока не знаю как это сделать. как придумаю - расскажу :)
     
  8. luckysundog

    luckysundog New Member

    Публикаций:
    0
    Регистрация:
    28 окт 2008
    Сообщения:
    106
    cornolio
    т.е. тебе надо способ именно с привлечением теории чисел? а то тут и так неплохие линейные способы были представлены.
     
  9. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    933
    Вот еще один способ - RSA featured. Основано на f(x)=(x*x*x) mod n,
    где n=p*q, p,q - простые.

    При прохождении X периода (те n) функция дает неповторяющиеся числа в интервале [0,n-1], например для n=3*5:

    При заданном числе N видимо придется искать ближайшее n>=N которое есть произведение простых (а может и не простых тоже?) и при вычислениях фильтровать на f(x)<N.
     
  10. cornolio

    cornolio New Member

    Публикаций:
    0
    Регистрация:
    16 апр 2009
    Сообщения:
    50
    хм, что то не получается, вот если взять 3 и 7 то числа повторяются, если 3 и 5 то нормально



    Код (Text):
    1. #include "stdafx.h"
    2. #include <stdio.h>
    3. #include <stdlib.h>
    4. #include <iostream>
    5. #include <time.h>
    6. int main()
    7. {
    8.     unsigned int i,x,b,n,m;
    9.     srand(time(NULL));
    10.  
    11.     n =  3 * 7 ;
    12.     for(b=0; b<10; b++)
    13.       {
    14.          x = rand()%n ; // seed
    15.          for(i=0; i<n ;i++)
    16.           {
    17.             m = (x*x*x) % n;
    18.             x++;
    19.             printf("%d;", m);
    20.           }
    21.          printf("\n");
    22.      }
    23.   std::cin>>m;
    24.   return 0;
    25. }
     
  11. FLASH300

    FLASH300 New Member

    Публикаций:
    0
    Регистрация:
    30 окт 2008
    Сообщения:
    72
    мде опять не догнал дак еще и количество элементов в массиве должно быть переменным ? Если при m = 4,8,16,32... не очень качественная последовательность, не напрягает может тогда так попробовать.

    Код (Text):
    1. #define Yi 64
    2. #define Yc 1
    3.  
    4. int main()
    5. {
    6.     unsigned int a,m,c;
    7.     unsigned int i,x;
    8.     unsigned int schet;
    9.     char mas[Yi+Yc+2];
    10.     srand(time(NULL));
    11.     schet =0;
    12. for(int z=0;z<10000;z++)
    13. {
    14.     m = (rand() %Yi)+Yc;
    15.     a = ((rand()%Yi)+Yc)*m;
    16.     a++;
    17.     c = 1013904223; //большое простое число
    18.  
    19.     x = rand(); // seed :)
    20.     if (z>9900)
    21.     printf("    %d=x %d=a %d=m %d=c\n",x,a,m,c);
    22.  
    23.     for(i=0;i<m;i++)
    24.     mas[i]=-1;
    25.     for(i=0;i<m;i++)
    26.     {
    27.     x = (a*x + c) % m;
    28.     mas[x]=0;
    29.  
    30.     if (z>9900)
    31.     printf("%d ",x+1);
    32.     }
    33.     for(i=0;i<m;i++){
    34.         if (mas[i]!=0){
    35.         schet++;//error
    36.         break;
    37.         }
    38.     }
    39.    
    40. if (z>9900)
    41. printf("\n-----------------------------------------------\n");
    42. }
    43. printf("\n error = %d\n",schet);//распечатать число ошибок
    44. system("PAUSE");
    45.     return 0;
    46. }
    PS:сам знаю что быдлокод учу С++ по маленьку :)
     
  12. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    933
    cornolio

    Это потому, что:

    ModVal equ 3*11 ; n=p*q, exp and phi=(p-1)*(q-1) share no divisors - (3-1)*(7-1)=2*6 and 3 do share!
    ; but for p=3 and q=11 phi=(3-1)*(11-1)=2*10 - no common divisors

    Вроде бы нету поффторений:
     
  13. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    933
    ++ Кстати, метод описанный gEnIuS_99, напоминаед RC4, только тама перемешивание неравномерное (поффторяюсь).