VPF::Как перемешать по рандому кучу чисел?

Chaos A.D.

Дата 12.6.2005, 20:39 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 172
Регистрация: 16.1.2005
Где: 09 RUS

Репутация: 6
Всего: 7

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

--------------------

Надо смеяться над тем, что тебя мучит, иначе не сохранишь равновесия, иначе мир сведет тебя с ума...Ken Kesey - One Flew Over The Cocoo's Nest

Mayk

Дата 12.6.2005, 20:57 (ссылка)

(нет голосов)

Загрузка ...

^аВаТаР^ сообщение>>

Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: 45
Всего: 134

Решение в лоб - использовать простой массив и 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]      
    }

Это сообщение отредактировал(а) Mayk - 12.6.2005, 20:59

--------------------

Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.

Void

Дата 12.6.2005, 21:31 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 40
Всего: 173

Код


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

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

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

Chaos A.D.

Дата 14.6.2005, 20:57 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 172
Регистрация: 16.1.2005
Где: 09 RUS

Репутация: 6
Всего: 7

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

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »