@Antohsa

Здравствуйте.

Имеется обычный ряд чисел.
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Необходимо равномерно и как можно максимально отдалить соседей друг от друга...
Перебором на бумажке у меня получается так:
[1, 4, 7, 2, 5, 8, 3, 6, 9]

то есть в среднем разница между соседями составляет 3. Есть проблемы:

1. Нет алгоритма. Реально цифр может быть и больше и меньше.
2. Не уверен, что это самый лучший вариант.

Пожалуйста, помогите...

0

@ProgJ

9,5,1,6,2,7,3,8

0

@Antohsa

ProgJ, спасибо.

У Вас получилось лучше вроде бы. Между цифрами в среднем 4, и, кстати, 4 пропущено, но можно последней записать.

А есть какая то математика в этой задачи, или Вы тоже просто перебором?

Хотя не совсем лучше. У меня между цифрами 1, 2, 3, 4, 5, 6, 7 по две цифры... У Вас одна....

0

@ProgJ

Для четных n:
n/2+1, 1, n/2+2, 2, ...
Разница равна n/2

0

@Antohsa

У меня распределение все таки лучше, по задаче надо как можно дальше отделить соседей....

0

@ProgJ

Тогда, сначала пишите все нечетные, потом все четные числа

0

@Antohsa

ProgJ, спасибо. А можно чуть-чуть подробнее, не совсем понимаю, что надо сделать...

0

@ProgJ

1,3,5,7,9,2,4,6,8

0

@Antohsa

Мне кажется, мое распределение более равномерно. В моем случае между соседними членами исходного ряда 2 цифры, а разница между соседями полученного ряда = 3 и нет такой провала между 9 и 2 (разница 7).... нужно равномерно и максимально....

0

@Shamil1

Об этом нельзя судить до тех пор, пока Вы не задали чёткие критерии "равномерности".

Задачу нахождения минимума нельзя решить, пока не известно, что именно нужно минимизировать.

0

@Antohsa

Я не знаю, как описать...

Давайте я тогда проще расскажу, что мне надо. Мне надо перемещать колоду карт как можно качественнее. Как это сделать? И как оценить качество. Наверное, хочется, чтобы карты одного достоинства лежали как можно дальше друг от друга, также хотелось бы, чтобы соседние карты (например, для вальта это дама и 10) были также как можно дальше друг от друга в колоде, и при всем при этом масти не должны совпадать, то есть желательно, чтобы двух подряд одинаковых мастей не было. Самый лучший расклад будет один, вернее скорее всего три, так как противоположный мастей нет, другими словами черви обратны бубнам, крестям и пикам.

В моей примере я просто хочу наиболее качественнее перемещать карты одной масти.
1 - это 6, 2 - это 7, 3-8, 4-9, 5-10, 6-J, 7-Q, 8-K, 9-А.

В моей раздаче получается:
6, 9, Q, 7, 10 K, 8, J, А

У ProgJ:
6, 8, 10, Q, А, 7, 9, J, K

Видно, что 6,8,10,Q, тем более подряд распределение намного хуже, чем 6, 9, Q, 7.

Я просто никак не могу найти нужную мне математику и алгоритм...

0

@VTsaregorodtsev

Сортировка, разбиение отсортированного списка пополам, и последовательное перечисление-чередование элементов из обоих половин (первый из первой, первый из второй, второй из первой, второй из второй, третий из первой, третий из второй,..).
Равномерность результата будет зависеть только лишь от равномерности распределения исходных чисел. Т.е. если из некоторых рамок [min,max] числа берутся не все и/или разное число раз - то вышеописанный способ равномерности не даст / не гарантирует.

0

@gazlan

Fisher–Yates shuffle с хорошим PRNG.

0

@Antohsa

gazlan, этот метод точно не подходит, так как никакого рендома быть не должно. Самая лучшая комбинация явно должна быть лишь одна (в задаче с картами одной масти), то что Вы предлагаете по сути делает Collections.shuffle() в Java.

VTsaregorodtsev , попробовал Ваш алгоритм:
[1, 5, 2, 6, 3, 7, 4, 8, 9] .

1,2,3,4 - через цифру.... 8, 9 - подряд.
Мой вариант опять же лучше..... =((((((

0

@gazlan

Гм. Все, что вам доступно - это парные перестановки. Условно - Unsort(). Можно предположить, что если Sort() уникальна, то двойственная ей Unsort() тоже уникальна (Unsort = Sort^-1). Если это так, вы должны предоставить Fitness-функцию, которая позволит оптимизировать перебор. Для (очень) ограниченного набора такую метрику можно построить и вычислить. Но будет ли она унимодальной...

0

@Antohsa

gazlan, мне бы по рабоче крестьянски как нибудь объяснить... я не все слова в Вашем посте понимаю.. =((

Боюсь,что unsort делает тоже самое, что shuffle...

0

@gazlan

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

Иными словами, ваша задача разделяется на две:

• Убедиться что функция качества расстановки имеет единственный максимум (Я, напротив, уверен, что это не так - у вас комбинаторная задача и число "лучших" расстановок будет экспоненциально расти с увеличением размера набора)
• Построить метрику оценки качества расстановки (на это уже указывал Shamil1).

Имея метрику (при условии единственного максимума), вы сможете

• Оценить качество предложенной (например, случайной) расстановки
• Использовать оптимизационный алгоритм (например, генетический) для улучшения этой оценки

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

0

@Antohsa

Да, наверное, Вы правы. Будут существовать симметричные расстановки, либо даже закольцованные.

Вроде бы получилось сформулировать оценку качества.

1. Необходимо между цифрами начальной последовательности разместить как можно больше других цифр.
2. Разность между соседними цифрами новой последовательности должна стремиться к максимальному.

С девятью числами максимальное и равномерное число цифр, которое можно вставить между соседями = 3. Не знаю как это доказать.
Получается вот так: [1] [ ] [ ] [ ] [2] [ ] [ ] [ ] [3].

Разности между числами получаются: 8,7,6,5,4,3,2,1. В среднем получим 4.5, думаю, что это теоретический максимум. То есть средняя разность между соседними цифрами в пункте 2 должна стремится к 4.5.

Вроде так...

Добавлено через 15 минут
Понимаю, что основная проблема в том, что я не могу четко сформулировать задачу...

0

@gazlan

Для 9 чисел доказать, наверное, можно и перебором. Заодно, найдете и группу симметрий. Возможно, разность лучше оценивать среднеквадратичным отклонением от среднего.

0

@Shamil1

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

Признаки того, что колода перемешана отвратительно:
1. За валетом не может идти дама
2. Если давно не было червей, то вероятность выпадения червы резко повышается

p.s. Конечно, это относится только к случаям, когда колода тасуется для игры (а не для любования и т.п.)

0