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

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

Форум программистов > C/C++: Общие вопросы > Как перемешать по рандому кучу чисел?

Автор: Chaos A.D. 12.6.2005, 20:39

Здравствуйте. Передо мной встала такая задача - есть у меня куча unsigned int-ов. И нужно мне все их перемешать по рандому. Как это эффективнее всего реализовать? На ум приходит одно - скрестить связанный список с обыкновенным массивом, что я почти сделал. Но может есть уже готовый велосипед? Есть ли такая структура данных, для которой доступ по индексу и удаление были бы сравнительно производительны? Поделитесь своими соображениями!

Автор: Mayk 12.6.2005, 20:57

Решение в лоб - использовать простой массив и xor.

Код


    int arr[5]={1,2,3,4,5}; //исходный массив
    int a,b; //будем менять два случайных элемента
    const int MAX=50; //MAX кол-во раз

    for(int i = 0; i != MAX; ++i){
        //получаем случайные элементы
        a = rand()%sizeof(arr);
        b = rand()%sizeof(arr);
        //меняем
        arr[a] ^= arr[b];
        arr[b] ^= arr[a];
        arr[a] ^= arr[b]      
    }

Автор: Void 12.6.2005, 21:31

Код


#include <algorithm>
...
int arr[N};
...
std::random_shuffle(arr, arr + N);

Гарантированная сложность O(N).

Автор: Chaos A.D. 14.6.2005, 20:57

Спасибо большое.