Интересная задачка

 

Предположим есть массив array(1, 1, 1, 1, 1, 2, 2, 2, 3, 3)

Задача написать такой алгоритм, чтобы он сортировал массив так, чтобы растояние между одинаковыми элементами было максимально.

К примеру одно из решений 1, 2, 1, 3, 2, 1, 2, 1, 3, 1

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

Может кто с мозгами, подскажет?

 
делаете N проходов по массиву и равномерно расставляете одинаковые элементы за каждый проход .

N = число разных элементов.

при первом расставим 1, при втором - 2, и т.д.

 
sergeev:
....равномерно расставляете одинаковые числа....
Как?
 
через шаг = ранг массива/число элементов для прохода
 
sergeev:
через шаг = ранг массива/число элементов для прохода

можете абстрактный код в пару строчек показать? мне кажется вы недооценили задачу.
 
sergeev:
делаете N проходов по массиву и равномерно расставляете одинаковые элементы за каждый проход .

N = число разных элементов.

при первом расставим 1, при втором - 2, и т.д.


Тоже сначала так подумал. Если все элемены массива будут уникальными (как самый наглядный пример), получится просто отсортиированный массив.

Еще такой вариант:

1. Отсортировать массив.

2. Разделить на пополам, и соединить половинки через один элемент, как колоду карт.

Например, имеем массив:

1 - сортируем его: 1, 1, 1, 1, 1, 2, 2, 2, 3, 3,

2 - делим его на пополам: 1, 1, 1, 1, 1 и 2, 2, 2, 3, 3,

3 - стусовываем: 1, 2, 1, 2, 1, 2, 1, 3, 1, 3

 
Integer:


Тоже сначала так подумал. Если все элемены массива будут уникальным (как самый наглядный пример), получится просто отсортиированный массив.

Еще такой вариант:

1. Отсортироват массив.

2. Разделить на пополам, и соединить половинки через один элемент, как колоду карт.

Например, имеем массив:

1 - сортируем его: 1, 1, 1, 1, 1, 2, 2, 2, 3, 3,

2 - делим его на пополам: 1, 1, 1, 1, 1 и 2, 2, 2, 3, 3,

3 - стусовываем: 1, 2, 1, 2, 1, 2, 1, 3, 1, 3


Самое оптимальное решение. Хотя ничем не отличается от предложенного мной вариант. Сумма разниц будет той же самой
 
Vinin:

Самое оптимальное решение. Хотя ничем не отличается от предложенного мной вариант. Сумма разниц будет той же самой

Виктор, покажите свой вариант, я его не видел, наверно пока писал он появился и исчез.
 

еще один вариант интересный представился.

работаем по делению отрезка пополам.

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

Начинаем с элементов, которых меньше всего. затем расставляем которых больше и т.д..

массив заполнится на максимальной энтропии., то что и надо

 
Integer:


Тоже сначала так подумал. Если все элемены массива будут уникальными (как самый наглядный пример), получится просто отсортиированный массив.

Еще такой вариант:

1. Отсортировать массив.

2. Разделить на пополам, и соединить половинки через один элемент, как колоду карт.

Например, имеем массив:

1 - сортируем его: 1, 1, 1, 1, 1, 2, 2, 2, 3, 3,

2 - делим его на пополам: 1, 1, 1, 1, 1 и 2, 2, 2, 3, 3,

3 - стусовываем: 1, 2, 1, 2, 1, 2, 1, 3, 1, 3


Что-то не очень =( а если массив побольше, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, | 1, 3, 1, 3, 1, 3, 1, 3, 1, 3 то наглядней будет выглядеть что в одной половине только двойки, а в другой только тройки. Нужно их тоже как бы перетусовать.
 

Действительно. Моего поста нету.

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

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

А пост на самом деле пропал куда-то.