Random в Qt

[splpwn]

Добрый вечер, друзья.
Подскажите. Как реализовать случайную выборку из фиксированного набора чисел без повторений?

[kambala]

qrand(), QSet или QHash. хотя не совсем понятно зачем тут использовать Qt - STL будет вполне достаточно.

[splpwn]

Непонятно, приведите пример с тремя числами без повторений пожалуйста.

[V1KT0P]

Непонятно, приведите пример с тремя числами без повторений пожалуйста.

Вот например банальный пример:

Код

C++ (Qt)
qsrand (QDateTime::currentMSecsSinceEpoch());
QList<int> numbers;
for (int i=0; i<4; ++i)
    numbers.append(i);
for (int i=0; i<3; ++i) {
    int num = qrand() % numbers.count();
    qDebug() << numbers.at(num);
    numbers.removeAt(num);
}

[Igors]

Код

C++ (Qt)
int RandIndex( int limit,  // число элементов в исходном массиве
               int numSel,  // число выбираемых
               int n )      // выбираемое
{
 int beg = n * limit / numSel;
 int end = (n + 1) * limit / numSel;
 return beg + (qrand() % (end - beg)); 
}
 

Вот например банальный пример:

Не много ли он жрет ресурсов?

[V1KT0P]

Вот например банальный пример:

Не много ли он жрет ресурсов?

Так написал-же банальный пример, а не высокопроизводительный идеальный =). Я даже мозг не включал, его жара плавит =(, хочу кондиционер...

Только я что-то не понял в твоем алгоритме:
Первым я выбрал количество чисел: 4, дальше указал число выбираемых чисел: 3, дальше указывал номер выбираемого числа, но что то в результате получил 0, 0, 1. С какого оно повторило 0, да в алгоритм не вникал, лениво =).

Код

C++ (Qt)
    qDebug() << RandIndex(4, 3, 0);
    qDebug() << RandIndex(4, 3, 1);
    qDebug() << RandIndex(4, 3, 2);

[kambala]

Непонятно, приведите пример с тремя числами без повторений пожалуйста.

Код

C++ (Qt)
qsrand (QDateTime::currentMSecsSinceEpoch());
QList<int> src; // исходный массив
QSet<int> dst; // наша выборка
int n; // количество элементов выборки
while (dst.size() < n)
    dst.insert(src.at(qrand() % src.size()));

пользуемся тем, что все элементы QSet уникальны. считаем, что src.size() > n, иначе в коде нет особого смысла. если использовать QHash вместо QSet, то можно ещё индекс сохранять.

Вот например банальный пример:

Не много ли он жрет ресурсов?

ну так попросили же пример на Qt

[V1KT0P]

Код

C++ (Qt)
qsrand (QDateTime::currentMSecsSinceEpoch());
QList<int> src;
QSet<int> dst;
int n;
while (dst.size() < n)
    dst.insert(src.at(qrand() % src.size()));

пользуемся тем, что все элементы QSet уникальны. считаем, что src.size() > n, иначе в коде нет особого смысла. если использовать QHash вместо QSet, то можно ещё индекс сохранять.

Ахаха, только что замерил производительность на 100000 значений при 99990. Мой банальный тупой алгоритм отработал за 1-2 секунды. А твой пришлось прибить после 15 секунд, лень дальше ждать =).

[Igors]

да в алгоритм не вникал, лениво =).

Там я сначала перепутал деление, должно быть * limit / numSel; (как сейчас)

пользуемся тем, что все элементы QSet уникальны. считаем, что src.size() > n,

И что будет для выборки 3 элементов из исходных (7,  7, 7, 1) ? Также никто не говорил что можно менять порядок следования

ну так попросили же пример на Qt

Стремление задействовать как можно больше "мощных тулзлов" и написать "как можно короче" выдает начинающего с головой  

Ладно, вот более интересная задачка на ту же тему. Все то же самое + доп условия

- исходный массив отсортирован (выборка тоже должна быть сортирована)
- разница между любыми 2 соседними значениями выборки не должна быть меньше заданного N

[Igors]

Мой банальный тупой алгоритм отработал за 1-2 секунды. А твой пришлось прибить после 15 секунд, лень дальше ждать =).

Вспомнился старый мультфильм в котором (кажется) мышонок на пне под гитару пел что-то типа

какой хороший Я
и песенка моя

[V1KT0P]

Вспомнился старый мультфильм в котором (кажется) мышонок на пне под гитару пел что-то типа

какой хороший Я
и песенка моя

Да ладно, что лулзы нельзя уже половить =). Я как увидел цикл с неопределенным количеством итераций, так не удержался.
Ты свой алгоритм тестировал? У меня тоже самое 0 0 1.

[Igors]

Ты свой алгоритм тестировал? У меня тоже самое 0 0 1.

То у Вас с copy/paste проблемы, у меня все норм (0, 1, 3) или (0, 1, 2)

[V1KT0P]

Ты свой алгоритм тестировал? У меня тоже самое 0 0 1.

То у Вас с copy/paste проблемы, у меня все норм (0, 1, 3) или (0, 1, 2)

Да действительно. Теперь другая проблема, нам нужны случайные числа, а в твоем алгоритме у меня постоянно первым 0 идет. Я что-то не догоняю смысла алгоритма.

[Igors]

Да действительно. Теперь другая проблема, нам нужны случайные числа, а в твоем алгоритме у меня постоянно первым 0 идет. Я что-то не догоняю смысла алгоритма.

Елы-палы, что ж тут "не догнать"? Делим на примерно равные интервалы, из каждого выбираем случайное число.

По поводу первого нуля. Во-первых взять число элементов побольше напр не 4 а 24. А во-вторых да, что-то у них с qrand - первое возвращаемое всегда маленькое если привести к [0..1]. Поэтому лучше использовать остаток от деления (исправил)

[V1KT0P]

Да действительно. Теперь другая проблема, нам нужны случайные числа, а в твоем алгоритме у меня постоянно первым 0 идет. Я что-то не догоняю смысла алгоритма.

Елы-палы, что ж тут "не догнать"? Делим на примерно равные интервалы, из каждого выбираем случайное число.

По поводу первого нуля. Во-первых взять число элементов побольше напр не 4 а 24. А во-вторых да, что-то у них с qrand - первое возвращаемое всегда маленькое если привести к [0..1]. Поэтому лучше использовать остаток от деления (исправил)

Это получается не очень и случайные числа. При 3 из 4 первым числом будет либо 1(1 вариант из RAND_MAX) либо 0. Ну явно не годится. Работать должно на любых числах. Я думаю ему в идеале нужны все числа из диапазона но в случайном порядке.