Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / C++ Новый топик    Ответить
 перемешать массив  [new]
nauseous
Member

Откуда: Жемчужина у Моря
Сообщений: 638
Здравствуйте! Подскажите каким образом можно перемешать массив (произвольно)
есть int массив:
// длина массива
int size = 75;

// выделяем память..
int * array = new array[size];

// заполняем его int(ом)
for(int i = 0; i < size; i++) {
        array[i] = i;
}

/*
на выходе
array[0] = 0;
array[1] = 1;
array[2] = 2;
array[3] = 3;
array[4] = 4;
array[5] = 5;
array[6] = 6;
...
*/

как теперь его перемешать (произвольно)? Спасибо!
12 янв 11, 16:05    [10060687]     Ответить | Цитировать Сообщить модератору
 Re: перемешать массив  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6610
for (size_t i = 0; i < size; i ++) {
  std::swap(array[i], array[rand() % size]);
}
12 янв 11, 16:28    [10060904]     Ответить | Цитировать Сообщить модератору
 Re: перемешать массив  [new]
nauseous
Member

Откуда: Жемчужина у Моря
Сообщений: 638
Anatoly Moskovsky - ой! а можно без std::..
12 янв 11, 16:35    [10060962]     Ответить | Цитировать Сообщить модератору
 Re: перемешать массив  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6610
nauseous
Anatoly Moskovsky - ой! а можно без std::..

Можно. Но для этого надо уметь программировать, а не по форумам побираться.
12 янв 11, 16:39    [10061006]     Ответить | Цитировать Сообщить модератору
 Re: перемешать массив  [new]
nauseous
Member

Откуда: Жемчужина у Моря
Сообщений: 638
Anatoly Moskovsky - по вашему все должны юзать std?
12 янв 11, 16:42    [10061028]     Ответить | Цитировать Сообщить модератору
 Re: перемешать массив  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6610
nauseous
Anatoly Moskovsky - по вашему все должны юзать std?

Нет. Я всего лишь сказал, что для того чтобы написать тот код без std::swap нужно всего лишь иметь уметь программировать (заменить на свою функцию, делающую тоже самое - две строчки всего)
12 янв 11, 16:46    [10061071]     Ответить | Цитировать Сообщить модератору
 Re: перемешать массив  [new]
Сыроежка
Member [заблокирован]

Откуда:
Сообщений: 399
nauseous
Anatoly Moskovsky - по вашему все должны юзать std?


Нет, вам нет нужды юзать std, но в таком случае вам самому придется написать функцию swap (если следовать приведенному примеру) для объектов типа int.

Простейший способ написания ее будет таким

void swap( int &left, int &right )
{
int tmp = left;
left = right;
right = left;
}
12 янв 11, 16:49    [10061106]     Ответить | Цитировать Сообщить модератору
 Re: перемешать массив  [new]
Mozok
Member

Откуда: Киев
Сообщений: 1041
Anatoly Moskovsky
Можно. Но для этого надо уметь программировать, а не по форумам побираться.

+1. И вообще, это однострочник:
std::random_shuffle(array, array + size);
nauseous
Anatoly Moskovsky - по вашему все должны юзать std?

Позволю себе комментарий: не все, а только те счастливчики, у которых он есть.
12 янв 11, 16:50    [10061110]     Ответить | Цитировать Сообщить модератору
 Re: перемешать массив  [new]
Сыроежка
Member [заблокирован]

Откуда:
Сообщений: 399
Сыроежка,

Только в спешке я сделал опечатку. Последнее предложение в функции должно выглядеть как

right = tmp;
12 янв 11, 16:51    [10061119]     Ответить | Цитировать Сообщить модератору
 Re: перемешать массив  [new]
Сыроежка
Member [заблокирован]

Откуда:
Сообщений: 399
Mozok
Anatoly Moskovsky
Можно. Но для этого надо уметь программировать, а не по форумам побираться.

+1. И вообще, это однострочник:
std::random_shuffle(array, array + size);
nauseous
Anatoly Moskovsky - по вашему все должны юзать std?

Позволю себе комментарий: не все, а только те счастливчики, у которых он есть.


Вы усложняете проблему! Раз для автора вопроса использование std:: вызывает вопросы, то стандартные алгоритмы тем более вызовут поток вопросов!
12 янв 11, 16:52    [10061134]     Ответить | Цитировать Сообщить модератору
 Re: перемешать массив  [new]
nauseous
Member

Откуда: Жемчужина у Моря
Сообщений: 638
По идее как-то так, но почему то рекурсия не работает, возвращает одинаковые значения..
посмотрите где я допустил ошибку:

int * mixed(int size, int * array = NULL) {
	array = new int[size];

	for(int i = 0; i < size; i++) {
        	int random = rand() % size;

                if(array[i] == random) {
                	mixed(i, array);
                }

                array[i] = random;
        }

	return array;
}

Спасибо!
12 янв 11, 18:01    [10061689]     Ответить | Цитировать Сообщить модератору
 Re: перемешать массив  [new]
Сыроежка
Member [заблокирован]

Откуда:
Сообщений: 399
nauseous
По идее как-то так, но почему то рекурсия не работает, возвращает одинаковые значения..
посмотрите где я допустил ошибку:

int * mixed(int size, int * array = NULL) {
	array = new int[size];

	for(int i = 0; i < size; i++) {
        	int random = rand() % size;

                if(array[i] == random) {
                	mixed(i, array);
                }

                array[i] = random;
        }

	return array;
}

Спасибо!


Да у вас просто ужас какой-то написан! Вы так можете очень быстро получить переполнение памяти!

Вы рекурсивно вызываете свою функцию mixtd() и каждый раз заново выдяете память для массива, а предыдущий указатель на память затирается.
12 янв 11, 18:04    [10061708]     Ответить | Цитировать Сообщить модератору
 Re: перемешать массив  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6610
Сыроежка
Да у вас просто ужас какой-то написан! Вы так можете очень быстро получить переполнение памяти!

Вы рекурсивно вызываете свою функцию mixtd() и каждый раз заново выдяете память для массива, а предыдущий указатель на память затирается.

Ужас в том что человек не понимает, что стек имеет конечный и достаточно малый размер.
И поэтому рекурсия принципиально не подходит для работы с динамическими массивами.
12 янв 11, 18:17    [10061781]     Ответить | Цитировать Сообщить модератору
 Re: перемешать массив  [new]
Сыроежка
Member [заблокирован]

Откуда:
Сообщений: 399
Anatoly Moskovsky
Сыроежка
Да у вас просто ужас какой-то написан! Вы так можете очень быстро получить переполнение памяти!

Вы рекурсивно вызываете свою функцию mixtd() и каждый раз заново выдяете память для массива, а предыдущий указатель на память затирается.

Ужас в том что человек не понимает, что стек имеет конечный и достаточно малый размер.
И поэтому рекурсия принципиально не подходит для работы с динамическими массивами.


В данном случае массивы выделяются не в стеке, а в куче. Проблема в том, что у него на самом деле нет надежной проверки выхода из рекурсии.
12 янв 11, 18:20    [10061796]     Ответить | Цитировать Сообщить модератору
 Re: перемешать массив  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6610
Сыроежка
Anatoly Moskovsky
пропущено...

Ужас в том что человек не понимает, что стек имеет конечный и достаточно малый размер.
И поэтому рекурсия принципиально не подходит для работы с динамическими массивами.


В данном случае массивы выделяются не в стеке, а в куче.

Я как раз не про выделение памяти для массива. Вам ли как человеку, которому не нужен ассемблер, не знать о чем я
12 янв 11, 18:31    [10061859]     Ответить | Цитировать Сообщить модератору
 Re: перемешать массив  [new]
nauseous
Member

Откуда: Жемчужина у Моря
Сообщений: 638
Сыроежка - предложенный вами вариант также не работает:
void swap( int &left, int &right ) {
	int tmp = left;
	left = right;
	right = tmp;
}

int * mixed(int size) {
	int * array = new int[size];

	for(int i = 0; i < size; i++) {
                swap(array[i], array[rand() % size]);
        }

	return array;
}
12 янв 11, 18:59    [10062021]     Ответить | Цитировать Сообщить модератору
 Re: перемешать массив  [new]
Сыроежка
Member [заблокирован]

Откуда:
Сообщений: 399
nauseous
Сыроежка - предложенный вами вариант также не работает:
void swap( int &left, int &right ) {
	int tmp = left;
	left = right;
	right = tmp;
}

int * mixed(int size) {
	int * array = new int[size];

	for(int i = 0; i < size; i++) {
                swap(array[i], array[rand() % size]);
        }

	return array;
}


Во-первых, это не мой предложенный вариант. Я лишь привел код функции swap, так как вас смутило пространство имен std::.

Во-вторых, вы не присвоили начальных значений эелементам массива перед тем, как делать их смешивание.
У вас был вначале следующий код

for ( i = 0; i < size; ++i ) array[i] = i;

А уж после, то есть после того, как вы так проинициализировали массив, вам предложили алгоритм перемешивания значений элементов.:)
12 янв 11, 19:05    [10062058]     Ответить | Цитировать Сообщить модератору
 Re: перемешать массив  [new]
nauseous
Member

Откуда: Жемчужина у Моря
Сообщений: 638
Сыроежка - да! Вы правы, так работает
void swap(int &left, int &right) {
	int tmp = left;
	left = right;
	right = tmp;
}

int * mixed(int size) {
	int * array = new int[size];

	for(int i = 0; i < size; i++) {
        	array[i] = i;
        }

        for(int i = 0; i < size; i++) {
        	swap(array[i], array[rand() % size]);
        }

	return array;
}
а так нет:
void swap(int &left, int &right) {
	int tmp = left;
	left = right;
	right = tmp;
}

int * mixed(int size) {
	int * array = new int[size];

	for(int i = 0; i < size; i++) {
        	array[i] = i;
        	swap(array[i], array[rand() % size]);
        }

	return array;
}

помогите упростить в одну функцию..
12 янв 11, 19:23    [10062127]     Ответить | Цитировать Сообщить модератору
 Re: перемешать массив  [new]
Сыроежка
Member [заблокирован]

Откуда:
Сообщений: 399
nauseous,
Просто вставьте код функции swap() внутрь цикла, где используете перемешивание значений элементов массива.
Например


for(int i = 0; i < size; i++)
{
int j = rand() % size;
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
12 янв 11, 19:31    [10062153]     Ответить | Цитировать Сообщить модератору
 Re: перемешать массив  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6610
nauseous
помогите упростить в одну функцию..

Упрощают в другую сторону - разбивая на функции :)
12 янв 11, 19:34    [10062162]     Ответить | Цитировать Сообщить модератору
 Re: перемешать массив  [new]
nauseous
Member

Откуда: Жемчужина у Моря
Сообщений: 638
Сыроежка спасибо!
12 янв 11, 19:45    [10062199]     Ответить | Цитировать Сообщить модератору
Все форумы / C++ Ответить