Перемешать массив чисел с определенным коэффициентом

@Exception · Регистрация: 16.10.2012

Студворк — интернет-сервис помощи студентам

Сразу к делу.
Пусть на входе имеется массив чисел. Размером он может быть как и очень большим, так и совсем маленьким, числа в нем могут повторяться, могут и быть все различны. Массив состоит из целых чисел.
На выходе необходимо получать массивы с определенным коэффициентом перемешивания, т.е. если абстрагироваться, то нужно иметь на выходе массив с 0-100% перемешанности, где 0% будет соответствовать отсортированному массиву, а 100% полностью перемешанному.
Каким образом можно реализовать подобного рода перемешивание? В какую сторону стоит прежде всего смотреть?

@titavich · 16.02.2014, 02:24

Exception, полностью перемешанный - это массив, у которого каждая тройка соседних элементов неупорядочена? (2 5 1, например)
каким Вы образом хотите этот процент вычислять?
и если не секрет, для чего это понадобилось?

@ViterAlex · 16.02.2014, 02:28

Я так понял, что полностью перемешанный массив - это массив, в котором элементы занимают иные позиции, чем в исходном. А если элементы могут повторяться, то определить это будет невозможно.

@Exception · 16.02.2014, 02:29 **[ТС]**

titavich, понадобилось это для того, чтобы написать программу для формирования различных наборов чисел, которые впоследствии будут применяться для тестирования алгоритмов сортировки. Да, есть еще множество параметров, по которым можно сформировать данные для тестов, но ко мне в руки еще попали файлы, числа в которых как раз-таки неким магическим образом перемешаны на 25, 50, 75 и 100%. Чем ближе к 100%, тем элементы перемешаны (относительно отсортированной последовательности) в большей степени.
Каким образом это было сделано и хотелось бы узнать, поэтому первые ваши два вопроса оставляю без ответа)

@titavich · 16.02.2014, 02:35

Сообщение от ViterAlex

Я так понял, что полностью перемешанный массив - это массив, в котором элементы занимают иные позиции, чем в исходном

Сообщение от Exception

где 0% будет соответствовать отсортированному массиву, а 100% полностью перемешанному

проще узнать алгоритм вычисления этого самого процента по заданным исходному и конечному массивам и уже начинать отсюда думать алгоритм такого преобразования

Добавлено через 2 минуты

Сообщение от Exception

понадобилось это для того, чтобы написать программу для формирования различных наборов чисел, которые впоследствии будут применяться для тестирования алгоритмов сортировки. Да, есть еще множество параметров, по которым можно сформировать данные для тестов, но ко мне в руки еще попали файлы, числа в которых как раз-таки неким магическим образом перемешаны на 25, 50, 75 и 100%. Чем ближе к 100%, тем элементы перемешаны (относительно отсортированной последовательности) в большей степени.
Каким образом это было сделано и хотелось бы узнать, поэтому первые ваши два вопроса оставляю без ответа)

по хорошему хотелось бы посмотреть на примеры таких наборов(само собой всю связку: 0, 25, 50, 75 и 100), т.к. идеи есть, но это лишь предположения, которые могут в корне отличаться от идеи этих файлов

З.Ы. желательно массивы размером 9-20 элементов, чтобы проще было искать подобие закономерности. но если более крупные, всё равно присылайте - завтра утром подумаю, либо предложу свой вариант

@Exception · 16.02.2014, 02:43 **[ТС]**

У меня на руках есть только файлы, отсортированные с упомянутым процентным соотношением, а над алгоритмом стоит подумать.

Перемешан на 0%

3 7 7 10 12 13 14 14 15 16 19 19 21 22 22 23 23 23 24 26 26 26 27 27 28 29 29 30 31 32 33 33 34 34 35 35 35 36 37 37 38 38 38 38 38 39 39 39 39 41 41 41 43 44 45 46 47 48 51 53 53 55 56 58

Перемешан на 25%

9 51 26 14 16 16 18 18 19 20 29 27 48 23 25 26 37 26 27 11 27 21 28 21 31 39 33 33 34 34 35 39 35 35 52 35 39 36 25 38 38 35 35 31 42 42 34 45 10 23 48 50 51 51 42 50 51 45 61 52 56 59 60 52

Перемешан на 50%

7 38 34 27 36 14 33 14 45 30 17 39 28 29 20 26 57 24 22 27 27 14 27 52 27 36 21 29 51 21 30 31 31 31 45 9 35 35 35 39 29 16 48 41 23 41 6 40 35 39 40 54 46 16 45 13 46 30 41 10 53 42 54 21

Перемешан на 75%

39 29 4 17 12 33 13 29 36 40 35 10 13 26 41 27 44 34 45 29 31 25 24 38 14 54 34 36 28 52 34 27 27 40 31 50 33 59 26 31 40 37 45 32 38 15 46 31 39 2 19 30 44 18 24 9 23 20 35 20 51 31 36 32

Перемешан на 100%

52 28 35 26 21 4 40 29 36 19 23 26 35 34 34 19 26 31 33 27 47 42 43 19 14 31 39 36 41 8 23 34 24 18 19 39 32 41 37 27 21 37 39 41 44 40 48 9 10 44 55 41 48 28 33 22 37 5 36 31 33 18 19 0

К сожалению, как можно заметить, числа в каждом файле разные, т.е. последовательности были отсортированы разные.
Также, на мой поверхностный взгляд, похоже, что процент перемешивания вычисляется на основании количества перестановок, т.к. при 25% от 64 элементов имеем 16 произвольных перестановок двух элементов. Но в таком случае этот процент нельзя считать чем-то точным, а стоит лишь говорить, что каждый последующий вариант (25, 50, 75, 100) перемешан в большей степени, чем предыдущий.

@rRczZZ · 16.02.2014, 02:43

Предположим, что все элементы отсортированы по неубыванию (можно сразу отсортировать входные данные). Также предположим, что элементы попарно различны (можно к правым прибавлять бесконечно малое). Меняя пару чисел местами увеличиваем коэффициент перемешанности на 1/n. Общий коэффициент это k/n где k - минимальное число перестановок двух элементов приводящее к упорядоченному виду.

Тогда задача сведется к генерации перестановок с нужным числом транспозиций, как минимум ее можно так свести биекцией. Проблема в том, что можно сортировать как по возрастанию так и по убыванию..

@Exception · 16.02.2014, 14:08 **[ТС]**

rRczZZ, я понимаю ваш подход примерно так:
для примера имеем последовательность 12345, если, например, 1 перемещать последовательно на одну позицию вправо, то получим последовательность 23451, и как ни странно, чтобы вернуть ее к отсортированному виду (используя лишь перестановки) в идеальном случае потребуется n-1 перестановок (где n кол-во элементов). Мне не очень верится, но почему-то очень похоже что перемешанная таким образом последовательность для алгоритмов сортировки будет самой сложной?)
Также возможен подход, где меняем элементы через 1, и плюс конечную пару.
Пример:
1234
3214
3412
3421
В таком случае также в идеально случае потребуется (n-1) перестановок, но не уверен, что подобного рода перестановки продуктивны для исследования впоследствии алгоритмов сортировки.

Новые блоги и статьи Все статьи Все блоги /
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .

@Exception What? Where? Why? 106 / 106 / 32 Регистрация: 16.10.2012 Сообщений: 459

	Перемешать массив чисел с определенным коэффициентом 16.02.2014, 01:31. Показов 1896. Ответов 7 Метки нет (Все метки) Сразу к делу. Пусть на входе имеется массив чисел. Размером он может быть как и очень большим, так и совсем маленьким, числа в нем могут повторяться, могут и быть все различны. Массив состоит из целых чисел. На выходе необходимо получать массивы с определенным коэффициентом перемешивания, т.е. если абстрагироваться, то нужно иметь на выходе массив с 0-100% перемешанности, где 0% будет соответствовать отсортированному массиву, а 100% полностью перемешанному. Каким образом можно реализовать подобного рода перемешивание? В какую сторону стоит прежде всего смотреть? 0

@titavich 71 / 70 / 21 Регистрация: 04.04.2012 Сообщений: 351
	16.02.2014, 02:24
	Exception, полностью перемешанный - это массив, у которого каждая тройка соседних элементов неупорядочена? (2 5 1, например) каким Вы образом хотите этот процент вычислять? и если не секрет, для чего это понадобилось? 0

@ViterAlex 8951 / 4863 / 1886 Регистрация: 11.02.2013 Сообщений: 10,246
	16.02.2014, 02:28
	Я так понял, что полностью перемешанный массив - это массив, в котором элементы занимают иные позиции, чем в исходном. А если элементы могут повторяться, то определить это будет невозможно. 0

@Exception What? Where? Why? 106 / 106 / 32 Регистрация: 16.10.2012 Сообщений: 459
	16.02.2014, 02:29 [ТС]
	titavich, понадобилось это для того, чтобы написать программу для формирования различных наборов чисел, которые впоследствии будут применяться для тестирования алгоритмов сортировки. Да, есть еще множество параметров, по которым можно сформировать данные для тестов, но ко мне в руки еще попали файлы, числа в которых как раз-таки неким магическим образом перемешаны на 25, 50, 75 и 100%. Чем ближе к 100%, тем элементы перемешаны (относительно отсортированной последовательности) в большей степени. Каким образом это было сделано и хотелось бы узнать, поэтому первые ваши два вопроса оставляю без ответа) 0

@Exception What? Where? Why? 106 / 106 / 32 Регистрация: 16.10.2012 Сообщений: 459
	16.02.2014, 02:43 [ТС]
	У меня на руках есть только файлы, отсортированные с упомянутым процентным соотношением, а над алгоритмом стоит подумать. Перемешан на 0% 3 7 7 10 12 13 14 14 15 16 19 19 21 22 22 23 23 23 24 26 26 26 27 27 28 29 29 30 31 32 33 33 34 34 35 35 35 36 37 37 38 38 38 38 38 39 39 39 39 41 41 41 43 44 45 46 47 48 51 53 53 55 56 58 Перемешан на 25% 9 51 26 14 16 16 18 18 19 20 29 27 48 23 25 26 37 26 27 11 27 21 28 21 31 39 33 33 34 34 35 39 35 35 52 35 39 36 25 38 38 35 35 31 42 42 34 45 10 23 48 50 51 51 42 50 51 45 61 52 56 59 60 52 Перемешан на 50% 7 38 34 27 36 14 33 14 45 30 17 39 28 29 20 26 57 24 22 27 27 14 27 52 27 36 21 29 51 21 30 31 31 31 45 9 35 35 35 39 29 16 48 41 23 41 6 40 35 39 40 54 46 16 45 13 46 30 41 10 53 42 54 21 Перемешан на 75% 39 29 4 17 12 33 13 29 36 40 35 10 13 26 41 27 44 34 45 29 31 25 24 38 14 54 34 36 28 52 34 27 27 40 31 50 33 59 26 31 40 37 45 32 38 15 46 31 39 2 19 30 44 18 24 9 23 20 35 20 51 31 36 32 Перемешан на 100% 52 28 35 26 21 4 40 29 36 19 23 26 35 34 34 19 26 31 33 27 47 42 43 19 14 31 39 36 41 8 23 34 24 18 19 39 32 41 37 27 21 37 39 41 44 40 48 9 10 44 55 41 48 28 33 22 37 5 36 31 33 18 19 0 К сожалению, как можно заметить, числа в каждом файле разные, т.е. последовательности были отсортированы разные. Также, на мой поверхностный взгляд, похоже, что процент перемешивания вычисляется на основании количества перестановок, т.к. при 25% от 64 элементов имеем 16 произвольных перестановок двух элементов. Но в таком случае этот процент нельзя считать чем-то точным, а стоит лишь говорить, что каждый последующий вариант (25, 50, 75, 100) перемешан в большей степени, чем предыдущий. 0

@rRczZZ 814 / 422 / 169 Регистрация: 08.02.2013 Сообщений: 711
	16.02.2014, 02:43
	Предположим, что все элементы отсортированы по неубыванию (можно сразу отсортировать входные данные). Также предположим, что элементы попарно различны (можно к правым прибавлять бесконечно малое). Меняя пару чисел местами увеличиваем коэффициент перемешанности на 1/n. Общий коэффициент это k/n где k - минимальное число перестановок двух элементов приводящее к упорядоченному виду. Тогда задача сведется к генерации перестановок с нужным числом транспозиций, как минимум ее можно так свести биекцией. Проблема в том, что можно сортировать как по возрастанию так и по убыванию.. 0

@Exception What? Where? Why? 106 / 106 / 32 Регистрация: 16.10.2012 Сообщений: 459
	16.02.2014, 14:08 [ТС]
	rRczZZ, я понимаю ваш подход примерно так: для примера имеем последовательность 12345, если, например, 1 перемещать последовательно на одну позицию вправо, то получим последовательность 23451, и как ни странно, чтобы вернуть ее к отсортированному виду (используя лишь перестановки) в идеальном случае потребуется n-1 перестановок (где n кол-во элементов). Мне не очень верится, но почему-то очень похоже что перемешанная таким образом последовательность для алгоритмов сортировки будет самой сложной?) Также возможен подход, где меняем элементы через 1, и плюс конечную пару. Пример: 1234 3214 3412 3421 В таком случае также в идеально случае потребуется (n-1) перестановок, но не уверен, что подобного рода перестановки продуктивны для исследования впоследствии алгоритмов сортировки. 0