С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.73/15: Рейтинг темы: голосов - 15, средняя оценка - 4.73
15 / 15 / 4
Регистрация: 17.06.2012
Сообщений: 274
1

Применить генератор к shuffle

12.06.2015, 17:53. Показов 3117. Ответов 12
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Всем привет.

Нужно перемешать массив, как можно с меньшей вероятностью повторения одной и тойже последовательности элементов после перемешиванья.

Нашел на просторах хороший генератор, вот его реализация:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* Minimal portable random generator by Park and Miller */
 
#define IA 16807
#define IM 2147483647
#define AM (1./IM)
#define IQ 12773
#define IR 2836
#define MASK 123456789
 
static long dummy;
 
void Seed(long dum) {dummy = dum;}
 
float unirand0() 
{
    long k;
    float ans;
    dummy ^= MASK;  
    k = dummy/IQ;
    if((dummy = IA * (dummy-k*IQ)-IR*k) < 0) 
        dummy += IM;
    
    ans = AM * dummy;
    dummy ^= MASK;
    
    return (ans);
}
Однако я настолько дубень, что даже имея хороших генератор, не понимаю, как его впихнуть в метод std::shuffle, чтобы он работал. Тоесть банально не понимаю, что имеено мне вписать после GrCards.end(), в строке кода
C++
1
std::shuffle(GrCards.begin(), GrCards.end(), );
Подскажите люди добрые
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.06.2015, 17:53
Ответы с готовыми решениями:

Функция Shuffle
Добрый день. Мне дана задача рандомально перемешать двухмерный массив. Порывшись в интернете...

Неправильно работает функция random shuffle
#include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;algorithm&gt; #include &lt;cstdlib&gt; #include...

Shuffle, как перемешать массив?
Как массив то перемешать? всю жизнь работало а тут на тебе... var_dump ($list);...

Китайская копия ipod shuffle
Ради эксперимента купил китайскую поделку под ipod shuffle-просто понравилось что &quot;фиолетовый и...

12
196 / 197 / 120
Регистрация: 27.05.2011
Сообщений: 545
12.06.2015, 19:17 2
Третий аргумент функции std::shuffle должен удолетворять требованиям UniformRandomNumberGenerator. Следовательно ваш генератор следует переписать в виде функтора:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <algorithm>
#include <ctime>
#include <iostream>
#include <iterator>
#include <vector>
 
#define IA 16807
#define IM 2147483647
#define AM (1./IM)
#define IQ 12773
#define IR 2836
#define MASK 123456789
 
class unirand0 {
    long dummy;
public:
 
    // Требуется для обобщённых алгоритмов
    typedef long result_type;
 
    // Инициализация, то, что делала ваша функция Seed
    explicit unirand0(long dum) :
        dummy(dum) { }
 
    // Вместо MAX вставьте наибольшее число, которое может возвращать
    // ваш генератор. Мне не удалось его рассчитать
    static long max() { return MAX; }
 
    // Аналогично вместо MIN вставьте наименьшее число
    static long min() { return MIN; }
 
    // В соответствии с требованиями, эта функция должна возвращать
    // число из отрезка [min(), max()]. Тут ваш код из функции unirand0.
    // Особого смысла в float не вижу,
    // т.к. std::shuffle нужны будут целые значения
    long operator() () {
        long k;
        float ans;
        dummy ^= MASK;  
        k = dummy/IQ;
        if((dummy = IA * (dummy-k*IQ)-IR*k) < 0) 
            dummy += IM;
 
        ans = AM * dummy;
        dummy ^= MASK;
 
        return ans * max();
    }
};
 
int main() {
    using namespace std;
    vector<int> test = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    // В качестве третьего парметра передаём объект нашего генератора
    shuffle(test.begin(), test.end(), unirand0(time(NULL)));
    // используем массив ...
    copy(test.begin(), test.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
}
И да, вы уж сделайте константы не макросами, а статическими константными членами unirand0.
1
15 / 15 / 4
Регистрация: 17.06.2012
Сообщений: 274
12.06.2015, 19:44  [ТС] 3
mymedia, Спасибо огромное! А как я могу узнать наибольшее и наименьшее число, которое может вернуть этот генератор?
0
196 / 197 / 120
Регистрация: 27.05.2011
Сообщений: 545
12.06.2015, 20:10 4
А там, откуда вы брали, не было указаны его характеристики?
Ну, можно как-нибудь подобрать. Только главное не ошибиться, иначе std::shuffle будет обращаться по неверным индексам или не перемешает часть массива.
0
15 / 15 / 4
Регистрация: 17.06.2012
Сообщений: 274
12.06.2015, 20:14  [ТС] 5
mymedia, Не, на сайте указанно небыло. А какой примерно диапазон?
0
196 / 197 / 120
Регистрация: 27.05.2011
Сообщений: 545
12.06.2015, 20:20 6
Насколько я понимаю, исходный ваш генератор возвращает значения в диапозоне [0,1). Правда, я могу ошибаться.
Но если так, то замените MIN на 0, а MAX на какое-нибудь число. В моей версии я домножаю результат прежде чем вернуть его. Так что, думаю, всё будет работать нормально.

Добавлено через 2 минуты
Только не понятно, зачем там дважды XOR'ить dummy, ведь его можно было поXOR'ить один раз, перед инициализацией…
0
15 / 15 / 4
Регистрация: 17.06.2012
Сообщений: 274
12.06.2015, 20:28  [ТС] 7
mymedia, не, ерунда какая-то получается.

Добавлено через 1 минуту
Цитата Сообщение от mymedia Посмотреть сообщение
Только не понятно, зачем там дважды XOR'ить dummy, ведь его можно было поXOR'ить один раз, перед инициализацией…
Не знаю, я просто внаглую скопировал генератов отсюда http://algolist.ru/maths/generator/park_mil.php

Добавлено через 5 минут
mymedia, Пробывал еще такой вариант, взял с http://www.cplusplus.com/refer... m/shuffle/,
C++
1
2
3
4
5
6
7
8
9
10
11
#include <algorithm>      
#include <random>       
#include <chrono>      
 
int main () {
 
  unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
  shuffle (foo.begin(), foo.end(), std::default_random_engine(seed));
 
  return 0;
}
он давал лучший результат, из всего что я пробывал. Однако, на итераций 5-6 все равно приходился один и тотже shuffle
0
196 / 197 / 120
Регистрация: 27.05.2011
Сообщений: 545
12.06.2015, 20:38 8
Слушайте, а зачем вам вообще это генератор? Может стоит воспользоваться готовым вихрем Мейерсона?.
Вот тут есть пример использования. Попробуйте так, я думаю, вполне пойдёт для вашей задачи:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <random>
#include <iostream>
#include <iterator>
#include <vector>
int main()
{
    using namespace std;
    vector<int> test = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    random_device rd;
    mt19937 gen(rd());
    shuffle(test.begin(), test.end(), gen);
    copy(test.begin(), test.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
}
Добавлено через 53 секунды
Этот код за 20 запусков подряд не выдал мне одинакового результата

Добавлено через 2 минуты
Цитата Сообщение от Leonman Посмотреть сообщение
Пробывал еще такой вариант
Скажате, а вы генератор (engine) каждый раз заново создавали и инициализировали, или в при очередном тесте передавали уже использовавшийся? Собственно говоря, нужно было поступать по второму сченарию.

Добавлено через 2 минуты
Цитата Сообщение от Leonman Посмотреть сообщение
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
Ещё учтите, что если между запусками программы прошло менее секунды, то у seed будет одинаковое значение.
0
15 / 15 / 4
Регистрация: 17.06.2012
Сообщений: 274
12.06.2015, 20:50  [ТС] 9
mymedia, а vector string`ов мешается по такому же принципу. Потому что, если я беру vector int`ов, то там, вихрем Мейерсона, все прекрасно перемешивается. А если я беру vector string`ов, то там все перемешивается черт пойми как и очень плохо.

И опять же, пока что, самый лучший результат я получил, делав так:
C++
1
2
3
4
5
6
7
8
void shuffleCards(std::vector<std::string> &GrCards, std::vector<std::string> &YeCards, std::vector<std::string> &RedCards)
{
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
 
    std::shuffle(GrCards.begin(), GrCards.end(), std::default_random_engine(seed));
    std::shuffle(YeCards.begin(), YeCards.end(), std::default_random_engine(seed));
    std::shuffle(RedCards.begin(), RedCards.end(), std::default_random_engine(seed));
}
тоесть я вызываю этот метод в цикле, допустим раз 100, и у меня почти на кажую итерацию, получается новая перемешка.
0
Эксперт С++
1675 / 1047 / 174
Регистрация: 27.09.2009
Сообщений: 1,945
12.06.2015, 20:58 10

Не по теме:

Переименовать Мерсенна в Мейерсона - это таки бесценно! :D



А теперь немножечко по делу:
Цитата Сообщение от Leonman Посмотреть сообщение
Нужно перемешать массив, как можно с меньшей вероятностью повторения одной и тойже последовательности элементов после перемешиванья.
Вот тут интересное место. Нормальный shuffle обеспечивает "вероятность повторения одной и той же последовательности" равную вероятности появления любой другой последовательности. Возможно, при постановке задачи имелось в виду именно это. Однако же эта вероятность не является минимальной. Минимальная вероятность равна 0 (если, конечно, последовательность позволяет), её можно обеспечить ручным поиском и устранением повторов.
1
15 / 15 / 4
Регистрация: 17.06.2012
Сообщений: 274
12.06.2015, 21:09  [ТС] 11
Nick Alte,

Не по теме:

Да простит меня Мерсенн. Я просто никогда не слышал об этом человеке.

0
mymedia
12.06.2015, 21:11
  #12

Не по теме:

Цитата Сообщение от Nick Alte Посмотреть сообщение
Переименовать Мерсенна в Мейерсона - это таки бесценно!
Каюсь, моя ошибка…

0
15 / 15 / 4
Регистрация: 17.06.2012
Сообщений: 274
12.06.2015, 21:18  [ТС] 13
Ладно. Объявляю тему закрытой. Не скажу, что добился идеала, но спишем на то, что идеала не существует
0
12.06.2015, 21:18
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.06.2015, 21:18
Помогаю со студенческими работами здесь

Не перемешиваются буквы во всех словах. Shuffle
function shfl($phrase) { $words = explode(' ' , $phrase); foreach ($words as $word)...

Может ли получится список тождественный исходному при перемешивании методом random.shuffle()
Может ли при случайном перемешивании массива 1, 2, 3, 4, 5 при помощи метода random.shuffle()...

Как можно в textarea применить ::first-line, или как к первой строки применить стиль, внутри данного элемента
Да и вообще, для этого можно ли еще что-либо вложить в данный элемент, кроме как текста? ...

Генератор комплексных чисел. Генератор гауссовских целых чисел
rand(1,n) - генерирует случайные числа, нормально распределенные на . Есть ли аналогичный генератор...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru