Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > random по равномерному закону

Автор: iPlay 4.7.2011, 19:21

Народ подскажите как сгенерировать числа по равномерному закону распределения в диапазоне, но так чтобы числа не повторялись??

Автор: volatile 4.7.2011, 23:37

А диапазон большой?
Если отбросить варианты с запоминанием уже выпавших, то мне пришло щас в голову следующее.
берем числовую последовательность 0,1,2,3,4
шифруем ее, на выходе получаем псевдо-случайную последовательность, без повторений.
равномерность распределения, зависит от качества шифра.

Автор: afiskon 5.7.2011, 06:52

Если числа не повторяются, они не случайные.

Я так понимаю, вы эти числа потом все равно собираетесь где-то использовать, так? Сгенерируйте массив чисел [N, N+1, N+2, ..., M] и перемешайте его. Алгоритм перемешивания такой:

Код


для i = 0 .. N
  j = rand(N)
  Arr[i] <-> Arr[j]

Автор: borisbn 5.7.2011, 08:52

вот алгоритм afiskon на Си++

Код


#include <stdlib.h>
#include <iostream>

const int COUNT = 10;

int main()
{
    int array[ COUNT ];
    for ( int i = 0; i < COUNT; i++ ) {
       array[ i ] = i;
    }
    for ( int i = 0; i < COUNT; i++ ) {
       int idx = (int)( rand() / (double)RAND_MAX * COUNT );
       if ( i != idx ) {
           int tmp = array[ i ];
           array[ i ] = array[ idx ];
           array[ idx ] = tmp;
       } 
    }       

    for ( int i = 0; i < COUNT; i++ ) {
       std::cout << array[ i ] << " ";
    }
    std::cout << std::endl;
}

http://liveworkspace.org/code/7da6462caf45b00f9a6ec1a6d7cd8ff5

Автор: afiskon 5.7.2011, 09:01

Главное - не забыть про srand.

Автор: borisbn 5.7.2011, 09:03

Цитата(afiskon @ 5.7.2011, 09:01

)

Главное - не забыть про srand.

на этапе отладки лучше либо не вызывать вообще, либо вызывать, но не со временем, как обычно, а с константой. Для повторяемости. А когда отладился - ага, нужно вызывать.

Автор: voral 5.7.2011, 10:07

Цитата(borisbn @ 5.7.2011, 09:03

)

Почему?

Автор: borisbn 5.7.2011, 10:20

Цитата(voral @ 5.7.2011, 10:07

)

Почему?

Если вся задача и состоит в генерации - то нет никакой разницы, если же эти данные потом используются в сложном алгоритме, то представь, что программа на каких-то данных падает - ну, ошибка в ней. Чтобы повторить падение и найти ошибку тебе нужны те же (не такие же, а те же) данные, потому, что на других данных программа может не падать, и ты не найдёшь ошибку.

Автор: Qu1nt 5.7.2011, 20:48

Как вариант:

Код


#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

int main()
{
    srand(time(0));
    const unsigned int size = 10;

    vector<int> data;
    data.reserve(size);
    for (unsigned int i = 0; i < size; ++i)
        data.push_back(i);      
    random_shuffle(data.begin(), data.end());
    copy(data.begin(), data.end(), ostream_iterator<int>(cout, " "));
}

http://liveworkspace.org/code/2209546cde5bee01eb0b60db81e55cfa

Автор: volatile 6.7.2011, 00:43

Да с перемешиванием неплохо, но только если диапазон небольшой.
Поэтому я и спросил у ТС про диапазон.
А если диапазон 3 миллиарда? это-ж сколько памяти надо будет вбухать на какой-то гсч smile

Автор: afiskon 6.7.2011, 08:09

Цитата(volatile @ 6.7.2011, 00:43)

Вы не забывайте, что у нас помимо ОЗУ есть и ПЗУ. Для нашего удобства в современных ОС есть mapping файлов в память.

Автор: volatile 6.7.2011, 13:36

Цитата(afiskon @ 6.7.2011, 08:09

)

в современных ОС есть mapping файлов

Ну даже на диске 12 гигабайт (3 миилиарда * 4 байта), это имхо, слишком для ГСЧ. А время .... ?
Да и на 32 разрядных осях вообще с такими массивами очень не сладко придется. Это нужно 64 разрядную ось... ну и т.д.

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

Автор: Alca 7.7.2011, 18:42

http://www.richelbilderbeek.nl/CppRandomNumber.htm