"Взбивание" массива - Форум на исходниках

WWW.ИСХОДНИКИ.РУ cpp.sources.ru

java.sources.ru web.sources.ru soft.sources.ru

jdbc.sources.ru asp.sources.ru api.sources.ru

  Форум на исходниках
  C / C++ / Visual C++
  "Взбивание" массива
СПРОСИТЬ  ОТВЕТИТЬ
профайл | регистрация | faq

Автор Тема:   "Взбивание" массива

Sila опубликован 11-02-2002 15:12 MSK
Есть массив из N элементов.
Нужно: перемешать (взбить) его случайным образом (как колоду карт)
DEiL опубликован 11-02-2002 15:21 MSK
неужто так сложно? :)
Sila опубликован 11-02-2002 15:22 MSK
не сложно, лениво
BeeHolder опубликован 11-02-2002 15:32 MSK
Если массив не большой:
Пусть N - кол-во элементов массива
Возьмем K: НОД(N,K) = 1. Т.е. они взаимнопросты
Создаем второй массив, равный по размеру первому
int k = 1;
for(j=0;j<N;j++)
{
arr2[j] = arr1[k];
k = (k * K)%N;
}
delete[]arr1;
the_moon опубликован 11-02-2002 15:39 MSK
меняешь два елемента местами по случайным индексам до одурения, вот и все. Где одурение >= длиннa массива.
Drugan опубликован 11-02-2002 15:40 MSK
Ну нельзя же такие вопросы задавать. Кто думать будет?
Тривиальное решение, оно должно первым на ум приходить...
N - размер массива
randomcount - сколько перемешивать
array - массив
for(int i = 0; i < randomcount; i++)
{
int x = random(N);
int y = random(N);
int tmp = array[y];
array[y] = array[x];
array[x] = tmp;
}
Я вот только с ходу не припомню синтаксис функции случайного равномерного распределения (Гауса).
;(onflict
Drugan опубликован 11-02-2002 15:41 MSK
2 the_moon: Хорошая идея приходит всем одноврименно :)
;(onflict
BeeHolder опубликован 11-02-2002 15:46 MSK
До одурения каждый может :)))
Берем генератор случайных чисел, который выдает все числа от 0 (или 1 - пофиг) до N-1(N).
Потом меняем местами:
k1 = (k * K)%N;
k = k1
k2 = (k * K)%N;
k = k2;
swap(arr[k1],arr[k2])
имеем - кол-во циклов для полного перемешивания = N / 2
Sila опубликован 11-02-2002 15:46 MSK
Объясни - НОД(N,K) pls.
Sila опубликован 11-02-2002 15:47 MSK
!!!!!!!!!!!!!! THANKS !!!!!!!!!!!!!!
BeeHolder опубликован 11-02-2002 15:50 MSK
НОД(K,N) - значит наименьший общий делитель. Т.е. при разложении чисел на простые множители у К и N одинаковых не будет:
пример: НОД(6, 12) = 2
6 = 2 * 3
12 = 3 * 2 * 2
НОД(10, 9) = 1
10 = 5 *2
9 = 3 * 3
Т.е. 10 и 9 взаимнопросты.
Зачем нам это нужно?
В генераторе вида k[i] = a * k[i-1] mod N
чтобы получить все числа от 1 до N-1 по разу до тех пор, пока не встретится k[0] должно выполняться условие НОД(a,N) = 1
Sila опубликован 11-02-2002 16:05 MSK
А как програмно определить К: НОД(K,N)=10 ?
Для случайного размера массива.
BeeHolder опубликован 11-02-2002 16:13 MSK
Тебе нужно найти такое K, что НОД(K, N) = 1.
Как?
Раскладываешь N на простые множители.
Потом берешь те простые числа, которые не попали в разложение N.
Произвольно их комбинируешь при помощи умножения.
Т.е. p[i] принадлежит множеству простых чисел - разложение N. p[i] < N.
K = p[1]^r1 * p[2]^r2 ... * p[m]^rm
причем K < N.
r[i] - случайное число от 0 и выше. есесно целое.
Другой вариант - выбираешь случайное K и проверяешь, что НОД(K,N) = 1. Но это долго и гемморно без гарантии результата.
BeeHolder опубликован 11-02-2002 16:15 MSK
уточню:
Т.е. p[i] принадлежит множеству простых чисел - разложение N. p[i] < N.
следует читать ".... простых чисел минус разложение ..."
Sila опубликован 11-02-2002 16:16 MSK
По моему у ;(onflict вариант попроще будет,
проверял - работает. Но все равно thanks.
BeeHolder опубликован 11-02-2002 16:21 MSK
Проще не значит лучше.
Если у тебя массив оч. большой, скажем несколько мегов, то чтобы его гарантированно перемешать нужно затратить кучу времени. На вскидку итераций 15*N.
Sila опубликован 11-02-2002 16:25 MSK
Многомегабайтный массив полюбому долго взбивать :)
BeeHolder опубликован 11-02-2002 16:30 MSK
Ну, одно дело крутить цикл 10 миллионов раз,
а другое дело 100 миллионов раз.
Кста, вместо подбора К с хитрым НОДом можно просто взять К = простое число меньше N. Простое число намного проще подобрать ;)
Sila опубликован 11-02-2002 16:31 MSK
Согласен
Valery опубликован 12-02-2002 10:00 MSK
из STL посмотри random_shuffle, есть версия с предикатом.
Flex Ferrum опубликован 13-02-2002 05:31 MSK
Позволю себе немного модифицировать идею BeeHoldera:
Создаешь второй массив равный по размеру первому, забиваешь его случайными числами, после чего сортируешь второй массив любым доступным/известным методом, одновременно (синхронно в процессе сортировки) перемещая элементы в первом массиве. В итоге - второй массив отсортирован, а первый - перемешан.
Valery опубликован 13-02-2002 08:08 MSK
ну зачем так жестоко?
это за один проход по массиву делается, не поленитесь, посмотрите исходник random_suffle.
хотя проще всего просто этот алгоритм к своему массиву и применить.
СПРОСИТЬ  ОТВЕТИТЬ
Перейти:

E-mail | WWW.ИСХОДНИКИ.RU

Powered by: Ultimate Bulletin Board, Freeware Version 5.10a
Purchase our Licensed Version- which adds many more features!
© Infopop Corporation (formerly Madrona Park, Inc.), 1998 - 2000.

Автор	Тема: "Взбивание" массива
Sila	опубликован 11-02-2002 15:12 MSK Есть массив из N элементов. Нужно: перемешать (взбить) его случайным образом (как колоду карт)
DEiL	опубликован 11-02-2002 15:21 MSK неужто так сложно? :)
Sila	опубликован 11-02-2002 15:22 MSK не сложно, лениво
BeeHolder	опубликован 11-02-2002 15:32 MSK Если массив не большой: Пусть N - кол-во элементов массива Возьмем K: НОД(N,K) = 1. Т.е. они взаимнопросты Создаем второй массив, равный по размеру первому int k = 1; for(j=0;j<N;j++) { arr2[j] = arr1[k]; k = (k * K)%N; } delete[]arr1;
the_moon	опубликован 11-02-2002 15:39 MSK меняешь два елемента местами по случайным индексам до одурения, вот и все. Где одурение >= длиннa массива.
Drugan	опубликован 11-02-2002 15:40 MSK Ну нельзя же такие вопросы задавать. Кто думать будет? Тривиальное решение, оно должно первым на ум приходить... N - размер массива randomcount - сколько перемешивать array - массив for(int i = 0; i < randomcount; i++) { int x = random(N); int y = random(N); int tmp = array[y]; array[y] = array[x]; array[x] = tmp; } Я вот только с ходу не припомню синтаксис функции случайного равномерного распределения (Гауса). ;(onflict
Drugan	опубликован 11-02-2002 15:41 MSK 2 the_moon: Хорошая идея приходит всем одноврименно :) ;(onflict
BeeHolder	опубликован 11-02-2002 15:46 MSK До одурения каждый может :))) Берем генератор случайных чисел, который выдает все числа от 0 (или 1 - пофиг) до N-1(N). Потом меняем местами: k1 = (k * K)%N; k = k1 k2 = (k * K)%N; k = k2; swap(arr[k1],arr[k2]) имеем - кол-во циклов для полного перемешивания = N / 2
Sila	опубликован 11-02-2002 15:46 MSK Объясни - НОД(N,K) pls.
Sila	опубликован 11-02-2002 15:47 MSK !!!!!!!!!!!!!! THANKS !!!!!!!!!!!!!!
BeeHolder	опубликован 11-02-2002 15:50 MSK НОД(K,N) - значит наименьший общий делитель. Т.е. при разложении чисел на простые множители у К и N одинаковых не будет: пример: НОД(6, 12) = 2 6 = 2 * 3 12 = 3 * 2 * 2 НОД(10, 9) = 1 10 = 5 2 9 = 3 3 Т.е. 10 и 9 взаимнопросты. Зачем нам это нужно? В генераторе вида k[i] = a * k[i-1] mod N чтобы получить все числа от 1 до N-1 по разу до тех пор, пока не встретится k[0] должно выполняться условие НОД(a,N) = 1
Sila	опубликован 11-02-2002 16:05 MSK А как програмно определить К: НОД(K,N)=10 ? Для случайного размера массива.
BeeHolder	опубликован 11-02-2002 16:13 MSK Тебе нужно найти такое K, что НОД(K, N) = 1. Как? Раскладываешь N на простые множители. Потом берешь те простые числа, которые не попали в разложение N. Произвольно их комбинируешь при помощи умножения. Т.е. p[i] принадлежит множеству простых чисел - разложение N. p[i] < N. K = p[1]^r1 * p[2]^r2 ... * p[m]^rm причем K < N. r[i] - случайное число от 0 и выше. есесно целое. Другой вариант - выбираешь случайное K и проверяешь, что НОД(K,N) = 1. Но это долго и гемморно без гарантии результата.
BeeHolder	опубликован 11-02-2002 16:15 MSK уточню: Т.е. p[i] принадлежит множеству простых чисел - разложение N. p[i] < N. следует читать ".... простых чисел минус разложение ..."
Sila	опубликован 11-02-2002 16:16 MSK По моему у ;(onflict вариант попроще будет, проверял - работает. Но все равно thanks.
BeeHolder	опубликован 11-02-2002 16:21 MSK Проще не значит лучше. Если у тебя массив оч. большой, скажем несколько мегов, то чтобы его гарантированно перемешать нужно затратить кучу времени. На вскидку итераций 15*N.
Sila	опубликован 11-02-2002 16:25 MSK Многомегабайтный массив полюбому долго взбивать :)
BeeHolder	опубликован 11-02-2002 16:30 MSK Ну, одно дело крутить цикл 10 миллионов раз, а другое дело 100 миллионов раз. Кста, вместо подбора К с хитрым НОДом можно просто взять К = простое число меньше N. Простое число намного проще подобрать ;)
Sila	опубликован 11-02-2002 16:31 MSK Согласен
Valery	опубликован 12-02-2002 10:00 MSK из STL посмотри random_shuffle, есть версия с предикатом.
Flex Ferrum	опубликован 13-02-2002 05:31 MSK Позволю себе немного модифицировать идею BeeHoldera: Создаешь второй массив равный по размеру первому, забиваешь его случайными числами, после чего сортируешь второй массив любым доступным/известным методом, одновременно (синхронно в процессе сортировки) перемещая элементы в первом массиве. В итоге - второй массив отсортирован, а первый - перемешан.
Valery	опубликован 13-02-2002 08:08 MSK ну зачем так жестоко? это за один проход по массиву делается, не поленитесь, посмотрите исходник random_suffle. хотя проще всего просто этот алгоритм к своему массиву и применить.