в продолжение Оптимальный алгоритм сортировки массива
.
Посидел тут надысь, вроде нарисовал алгоритм.
Получился рекурсивный, для перестановок достаточно 1 буферной ячейки.
Тут все понятно стало, если переставляется/сортируется _весь_ ряд/массив - то все ок, достаточно буфера из 1 ячейки.
.

Кнута на тебя нет..
Зы))

(0) лови Кнута)) вторая ссылка, третья книга.. там все есть)) http://yandex.ru/yandsearch?text=кнут%20искусство%20программирования&lr=213&csg=0%2C0%2C0%2C1%2C3%2C0%2C0
Гони пряник...

(2) на http://yandex.ru/images/search?text=пряник&stype=image

(2) много букав, не осилил.. ;-)

(0) частный случай только для чисел? а если расширить на любой тип, в том числе составной, по заданным правилам сравнения?

смешно видеть в одной строке "рекурсия" и "1 буферная ячейка"

(6) Жан, не надо пердежон!
Например, 100 ячеек, во всех ячейках товар стоит не на своем месте. Как минимум без 1 буферной ячейки - не обойтись... - если мы двигаем реальный физический товар, а не виртуальные сущности типа переменных/ссылок.

(5) я рассматривал случай, где есть некий уникальный ИД, характеризующий сущность (у меня сущность = товар, ИД = артикул, сущность имеет "вес", описываемый числом).

(7) 100 ячеек замкнуты в 8-ку и есть операция сдвига (шт. товара меньше чем 100) т.е. двигаем нескоко товаров по этой восьмерке... ?

(9) это вопрос или предложение рассмотреть такую ситуацию?

(9)+ это так способ избавиться от буфера...

(11) в случае если 100 ячеек и 100 артикулов (разных) - не прокатит.

(12) не помню точно эту детскую головоломку с шариками в 8-ке но переставлять там точно можно было...

т.е. прокатит даже при 100=100

(11) если какие-то ячейки пустые - то от буфера можно избавиться, я таки думаю да.

(13)+
https://ru.wikipedia.org/wiki/Волшебные_кольца

(15) нэту буфера

(13) хм.. как это оно прокатит...?
возьми вырожденный случай: я = ячейка, т = товар
.
исходное положение (неправильное):
Я1,Т2
Я2,Т1
.
конечное положение (правильное):
Я1,Т1
Я2,Т2
.
Переведи исходное положение в конечное без использования буфера...?

(17) тут вырожденный случай слишком мало ячеек и товара но пусть эти две ячейки замкнуты т.е. при движении в любую сторону они местами то поменяются ))

1-2 > 2-1

(18) не забывай, что мы оперируем ФИЗИЧЕСКИМИ сущностями (палеты с товаром, стоящие в ячейках). просто так палеты не "поменяются" - они туннелировать не могут. чтобы поменять - надо _освободить_ какое-то место...

(18) вот уж эти одноцэшники, оторванные от реальности...
;-)

Представляю этакую ленту транспортера в форме головоломки (с двумя пересечениями колец) :)

И типа перемещение ленты очень быстрое = скорости вытащить паллету и задвинуть в другое место

(15) там на картинке 10 пустых ячеек, а ты говоришь, что нет буфера

(21) все равно не проканает - здесь у тебя фигурирует "вытащить палету". - палету нельзя вытащить в воздух, даже если это делать очень быстро

(23) "вытащить паллету" это только для сравнения скорости перестановок с обычным расположением ячеек в одну линию

понятно что в случае такого 8-зного склада должно быть место откуда забирают паллеты и куда их засовывают, но это же не буфер :) т.к. в перестановках это место не учавствует

(22) не понял где нашел пустые ячейки? тама "черные" шарики а не пустые...

(24) ты тупой или прикидываешься? ;-)
Восьмерочный склад в реальности нигде не видел и не знаю такого
Если двигать всю восьмерку без буфера то все равно не получится товар стоит на фиксированных номерахсекторах как в рулетке и с одного номера на другой не туннелирует в процессе передвижения восьмерки занимают палеты промежуточное положение между пронумерованными секторами-по сути это и есть буфер
Даже если считать что буфера нет надо еще посчитать что по затратам выгоднее толкать всю цепочку палет или двигать по одной;-)

Не понял вообще в чем суть задачи. Отсортировать товар на складе или массив?

Наванговал: Нужно отсортировать товар на складе как можно быстрее использую какое-то количество манипуляторов (не знаю как они называются)?

(7) тогда указал бы в (0) по какому параметру ты алгоритм подбираешь; если у тебя реальный склад и что-то двигается, то предположу, что это количество перестановок или обменов (а не сравнений, которое обычно считают для сложности алгоритма). Тут та же сортировка выбором дает всего (N-1) обмен. С другой стороны, не ясно, что мешает сначала отсортировать товары виртуально любым доступным алгоритмом, а потом дать управляещие команды по перестановке (здесь так же получится N-1 обмен).

По поводу перестановок. В математике они так и называются.

Пример:

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

Наверху исходный массив, внизу отсортированный.

Цикл - перестановка по циклу.

Пример:

(2 3 1)

Соответствует перестановке

2 3 1
3 1 2

Есть теорема о том, что любая перестановка может быть представлена в виде произведения (композиции) независимых циклов.

Возьмем нашу перестановку из первого примера. Получаем следующие НЕЗАВИСИМЫЕ циклы.

(2 1 4 3)(9 6 7 8)

Теперь вернемся к нашей задаче. Берем первый цикл и начинаем перемещать товар по складу согласно ему. Для этого нам достаточно 1 манипулятора. Берем товар из ячейки №1, везем к ячейки №2, вынимаем товар из ячеки №2 и ставим привезенный товар туда. Намного удобнее, если бы ездило два манипулятора одновременно. Чтобы осуществить перестановку по циклу максимально быстро нужно иметь количество манипуляторов равное длине цикла.

Надеюсь, то, что надо.

(26) а кто мешает сделать склад в виде 8-ки? точнее двух пересекающихся в двух местах колец?

технология есть http://www.mmkmmk.ru/konvejernie-sistemi-transporteri-rolgangi-i-pr/rolgang-privodnoj.html

и http://ipuzzles.ru/wp-content/uploads/2010/02/rings.swf менять местами можно прекрасно "туннелировать" паллеты

(30)+ согласен что для реальности это изврат ;) но как теоретическая фигня весьма занятно и буфера нету и погрузчик не нужен

это все для програмной сортировки или для реальной физической сортировки коробок с товарами?

(32) ну у ТС для реальной, а все прочие для виртуальной ))

(28) да, именно так и делаю

(29) спсб повтыкаю днем

(29) исходная расстановка
2 3 4 1

Есть 1 манипулятор
Есть 1 свободная ячейкабуфер
Каков будет оптимальный вариант перестановок

Я же тебе писал алгоритм.
Единицу в буфер, Четверку на свое место, тройку на свое место, двойку на свое место, единицу на свое место.
Минимальное число операций равно Х раз положить в буфер(операция "положить в буфер" - выполняется один раз для каждой группы, в которой все контейнеры стоят не на своих местах, при этом в совокупности группа занимает свое конечное место) + количество контейнеров не на своих местах.
Я тебе в прошлой ветке привел алгоритм который расставит именно за это количество операций.

например для
2 1 4 3
Две группы - 2,1 и 4,3
Значит суммарное количество операций - 4 (не на своих местах) + 2 (две группы) = 6

Алгоритм -
1. снимаем в буфер любой! ящик который стоит не на своем месте.
2. пока на свободное место претендует ящик не из буфера, ставим его на свободное место. Иначе ставим на место ящик из буфера, и переходим к пункту 1.

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

(36) А что значит свободная ячейкабуфер? Манипулятор на пол не может поставить паллету? Вынуть ту, которую нужно перемещать следующую, поставить ее на пол и первую воткнуть на ее место.

Суть цикла заключается в том, что нужно переместить товаров равное его длине. Меньше никак. От того, что товар следуя из точки А в точку Б полежит в буфере - ничего не изменится.

Видимо, есть какие-то особенности по операции перемещения, подробнее, пожалуйста.

(40) "поставить ее на пол"
- вот этот "пол" и есть буфер, причем конкретно адресный.
взять палету из ячеки-источника на манипулятор, довести до нужного места и поставить на пол-буфер = 1 перемещение
.
достать палету из ячейки-приемника (далее не детализируем) - второе перемещение.
.
из буфера поставить в ячейку приемник - третьеперемещение

(39) NS, большое спасибо, что уделяешь мне время.
.
"И так-же легко показать что два и более свободных буферных места не ускорят процедуру по количеству перемещений по сравнению с одним буферным местом."
.
да, это я уже проработал (чуть раньше чем поднял эту ветку) и понял.

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

Ты алгоритм для карщиков рисуешь что ли на склад ?
Никто не будет пользоваться, никогда..
Поставят так, как им удобнее, а не так, как у тебя в бумажке напишут.
Гарантия 99%

(40) Основная операция - поднять паллет и опустить. Перевезти намного проще.

(37) если рассматривать упорядоченный ряд слева направл - то левые позиции имеют наибольший "вес". И их желательно упорядочить в первую очередь.
.
то есть - если есть ряд палет из 100 ячеек, 50 ячеек имеют вес (просто количество подходов к товару) от 150 до 200, а остальные 50 ячеек имеют вес от 20 до 30 - то по большому счету вторые 50 ячеек (с малыми весами) - их упорядоченность строгая особой ролди не играет. главное - чтобы первые 50 ячеек с большими весами(и они стоят вразброд пол ряду) - вот их надо упорядочить в первую очередь (есть еще ограничивающий ресурс "время", отведенное на перестановку).
.
Поэтому упорядочение всегда (?) надо начинать с правильного выставления самого левого члена ряда. потом второго. Или же алгоритм, который обеспечивает правильную расстановку первых N членов ряда, остальные члены ряда - пофиг как выстроятся (будет время - их досортируем/переставим потом)

(45) тут проще - работаем с ячейкаи рабочих мест, на 1 ярусе ;-)

(46) Так выбирай слева первую ячейку в которой стоит неправильный паллет. А дальше по алгоритму всё однозначно. Вариантов нет.

(44) посмотри видео как склад амазон в сша работает )))
http://geektimes.ru/post/242344/

(39) не учитывается, что погрузчиков может быть более одного и что 2 погрузчика могут не разойтись на дороге

(49) это я видел.
ЗЫ: еще хороший пример - автоматическая выдача автомобилей фольц в германии (там где гараж в много этажей)

НО, у Чебура то поди наш совковый склад и вся автоматизацию для грузчиков пишется поди, разве нет ?
Как будет выглядеть задание на "сортировку" для них ?..Они там с ума то не сойдут ?
:))

(50) Этого не было в задаче.

(41) Ну тогда для одного цикла 1 буфер, большее количество только усложнит все.
(46) Считай средний вес цикла (содержащихся ячеек). Сдвигай товар в первую очередь по циклу с наибольшим весом. А еще можно выявлять последовательности непрерывные с наибольшими весами и с них начинай сортировку. Тогда количество буферов нужно будет равное максимальному количеству начатых но не полностью отсортированных циклов в течении всей процедуры сортировки.

(51) Ага, прикольно. Внушительно. Я в свое время участвовал в проекте создания Автоматизированной парковки (где-то в Королеве ее смонтировали, но уже без меня). Выглядело оно на тестах так: http://youtu.be/3nv0Wx5uCyw

(51) Ну у нас маршруты (сборщиков) на складе работают. Никаких проблем особо нет, и внедрили очень быстро. Почему бы не внедрить маршруты погрузчиков?

(0) А по теме, имха, перестановка слишком дорогая операция, чтобы делать ее просто так. Выгоднее оставить как есть, и лишь в будущем запланировать размещать приоритетный товар в более "выгодные" ячейки.

(44) это у тя бардак на складе ;-)
а у мну - все нормально.
никто сам не двигает и не ставит "как удобнее", у мну все по заданиям, как положено в правильной компании! ;-)

(56) я в курске, что ты умный! ;-)
.
рабочие ячейки (1артикул=1ячейка) практически никогда не являются пустыми, чтобы  динамически переназначать рабочие ячейки.
.
перестановки не совершаются "просто так" - именно потому что это дорогая по ресурсам операция. делается целенаправленно в периоды когда ниprfz загруженность склада

(48) ну так и делаю.
тут вопрос в том, что когда сразу переставлять весь ряд - то достаточно одного буфера. а если обеспечивать правильную расстановку начала ряда (с большими весами) - и не обеспечивать сортировку/перестановку хвостов - тут я еще руками "не прочуствовал"

(51) да тупо будет на ТСД бери палету из этой ячейки вези туда-то и все..

тут еще хорошо бы как-то распаралелить процесс перестановок.
вот насчитал я допустим план (очередь заданий) на перестановку. Как вычленить "непересекающиеся" последовательности перестановок - чтобы их можно было выполнять независимым сборщикам?

(61) Независимые циклы. Или последовательности из циклов.

(51) склад нормальный, 6 тыщ квадратов, высотнеы узкопрожодные стелажи и мезонин. перестановку будут делать пипл с рохлями, ибо другие средства автоматизации не подойдут, штабелер - накладно по времени, погрузчики - вилы неразворотные.

(62) вот как раз задача - как их вычленить..?

(64) Кого, циклы независимые? Или последовательности?

кому интересно потренироваться: моксели с данными
.
http://файлообменник.рф/i28lfixo31j6.html - исходная неправильная расстановка
.
http://файлообменник.рф/pjfbzdcse9gi.html - исходная правильная расстановка
.
для "разминки" - важно чтобы были упорядочены товары/ячейки с весом до 10 включительно, остальные - несущественно

(66) зачем так издеваться)

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

(68) если есть место для разъезда/расхождения нескольких "переставляльщиков" то кол-во могущих одновременно работать равно кол-ву буферных мест+1, ну еще ограничение на кол-во неправильно стоящих товаров (нет смысла иметь)

(69) место для разъезда нескольких работников - есть

(69) ок, буфер - один, значит переставляльщиков - два может быть..?
.
а как из насчитанных заранее перестановок выбрать независимые друг от друга перестановки чтобы их "раздать" переставляльщикам?

(71) ммм 2 раздавальщика - 1 буфер

1-й берет любой товар не на своем месте и тащит в буфер
в это же время
2-й берет тот товар который должен нужно поставить в то место откуда вытащил 1-й и тащит его туды

и т.д.

(72)+ т.е. алгоритм то один просто параллельное выполнение непересекающихся операций (не мешают друг другу по месту)

если еть еще буфер то еще один 3-й "переставляльщик" может в то же время вытаскивать товар в этот буфер эээ

походу ошибся не X+1 а X*2 от кол-ва буферов можно параллелить

(73) хотя не все зависит от "неправильности" изначальной расстановки

максимальный вариант число "переставляльщиков" равно числу мест

например 2-3-4-1 нужно переставить в 1-2-3-4 тогда работают одновременно 4-ро, 1-й тащит в буфер 1(по факту сразу из буфера тащит на место 2-ки когда оно освободится), 2-4-й переставляют одновременно на нужные места свои товары

(64) Это же подзадача вышеописанного алгоритма. Просто снимаешь любой стоящий не на своем месте, и по очереди ставишь на пустое место тот, который должен стоять.
Как только дошли до необходимости выставлять из буфера - вот тебе и цикл (паллеты стоящие не на своих местах, но в совокупности занимающие свое искомое место).

(72) да правильно но не проканает - пипл должен работать независимо
А здесь начало операции зависит от другого человека
Полягут на синхронизации усилий смайл

(75) пытаюсь осмыслить

(75) плохо у меня мозги на отвлеченную матиматику заточены
Допустим сейчас товары стоят вот так
Яn Тm
Где
яn ecть порядковый номер ячейки
тm есть товар который должен стоять в ячейке с номером m
Правильно расставить надо 30 товаров от начала ряда

Исходная расстановка

Я1 т80
Я2 т60
Я20 т1
Я70 т2

Перемещения
Я1 пусто, т80 в буфер
Т1 из я20 переставляю в я1
Тут ок

Теперь мне надо освободить я2 чтобы из я20 взять т2 и поставить в я2
Но я2 я освободить не могу так как некуда-буфер занят
Скидываю т80 из буфера в я20

Но потом мне т80 из я20 придется снова доставать чтобы в я20 поставить т20

Где у меня ошибка?

(79) Как тебе может потребоваться повторно доставать, если ты ставишь контейнеры только уже на конечное место?

пока четко ясно одно
если надо переставить\упорядочить весь ряд - то достаточно одного буфера, так как я могу вычислит какую надо сделать самую первую перестановку в буфер, чтобы потом по цепочке переставлять все правильно.

а вот если мне надо только часть ряда упорядочить - пока в бошке у меня не уложилось как надо..
.
если надо упорядочить чтобы стояли например правильно только первые 30 товаров из ста - в предыдущем комменте уже получается неоптимально...
.

Ты можешь вместо Я и Т написать номер ячейки по порядку.
И номер ячейки для контейнера в которой он должен стоять после сортировки? Зачем ты всех путаешь, а в первую очередь себя?

(81) попробуй делать это все днем для разнообразия например)) не в пример продуктивнее будет, например))

(80) потомц что в я20 должен стоять товар т20, а у меня я20 занято товаром т80

(81) Ровно так-же как основной алгоритм, только когда свободна ячейка выше 30 - используешь её как буфер, перейдя на первый шаг алгоритма.
(84) У тебя в условии нет товара Т20.

И зачем тебе вообще смотреть занятые ячейки? На каждом шаге алгоритма ты смотришь только свободные ячейки, и в свободную ячейку ставишь тот Т, который должен там стоять.

(82) выше по тексту - примеры мокселей с исходными данными.
.
здесь оперирую
Я1 - ячейка с порядковым номером 1
Я2 - ячейка с порядковым номером 2
и т.д.
.
Т1 - товар, который в итоговой растановке должен стоят в Я1
Т2 - товар, который в итоговой растановке должен стоят в Я2
Т80 - товар, который в итоговой расстановке при полной перестановке ряда должен стоять в Я80, при частичной перестановке ряда (например только первых 30 товаров, от т1 до т3) - пофиг где будет стоять, главное что он не будет стоять в ячейках от я1 до я30

(85) т20 есть в исходной неправильной расстановке - тоже стоит где-то..

(86) на примере (78) и (79) -
.
Перемещения
Я1 пусто, т80 в буфер
Т1 из я20 переставляю в я1
Тут ок
.
теперь мне надо как-то поставить т2 в я2 - вопрос: каким образом?

(85) надо подумать... насчет использовать свободную ячейку в хвосте ряда как буфер... недотумкиваю... надо поиграть

(83) днем я занимаюсь всякой неинтересной херней, которая обеспечивает оперативную текущую работу.. ;-)

ага.. понятно, где где в (79) недотумкал..
вторым шагом в пустую я20 ставим т20...

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

Попробую еще раз
.
Исходная расстановка

Я1 т80
Я2 т60
...
Я20 т1
Я50 т20
Я70 т2
...
Я80 т65

(94) Ты можешь просто написать подряд идущий числа, как все нормальные люди нумеруют?
У тебя есть Я50, Я70, но нет соответствующих Т.
Есть Т65, Т60, но нет соответствующих Я.

На натуральном ряде тренируются сортировать.

Перестановки
.
(буфер, пусто)
.
(Я1, Т80) -> (буфер,Т80), (Я1,пусто)
(Я20, Т1) -> (Я1,Т1), (Я20,пусто)
(Я50, Т20) -> (Я20,Т20), (Я50,пусто)
.
тут вроде ок.
.
Следуя заветам классиков "..На каждом шаге алгоритма ты смотришь только свободные ячейки, и в свободную ячейку ставишь тот Т, который должен там стоять." - смотрим - сейчас свободня Я50 - в ней вообщем должен стоять Т50 - если Т50 находится в голове ряда - забираем его оттуда и пошел очередной виток алгоритма по циклу.. отлично.. Если Я50 стоит где-то в хвосте ряда то ставить т50 в я50 - смысла нет, так как хвост ряда несущественен... ага... тогда в голове ряда (в ячейках с 1 по 30) - смотрим товар какой-нибудь который должен стоять в хвосте - перекидываем его в хвост и очередной виток алгоритма.. так отличненько...
вроде должно склеится...

(96) Я не понимаю что ты делаешь. В принципе.
Ты не можешь пронумеровать ячейки по порядку? Или не можешь Т пронумеровать по порядку начиная с единицы? Чем ты вообще занимаешься? ИМХО просто издеваешься над здравым смыслом.

(95) ну правильно, на натуральном ряде.
.
"У тебя есть Я50, Я70, но нет соответствующих Т.
Есть Т65, Т60, но нет соответствующих Я."
.
есть соответствующие Я, опущены просто чтобы не писать весь ряд
.
просто неудобно
когда написано
4 8 12 30 5 7 11 8
смотреть на каком месте стоит 5

(97) не, все правильно ты говоришь.
сортируем натуральный неупорядоченный ряд

(98) Я честно, вообще уже не понимаю какую задачу ты решаешь.
Нумеруешь согласно местам на которых должно стоять.
Т5 - должно стоять на пятом месте. Как может быть непонятно на каком месте должно стоять Т5?
Я5 - это пятое место.

(100) совершенно верно

Задача выглядит так -
Я1 Т6
Я2 Т1
Я3 Т3
Я4 Т5
Я5 Т2
Я6 Т4

Пронумеровать надо натуральным рядом. Т5 должно стоять в месте Я5.

А в (94) что за бред? Зачем ты так их нумеруешь? Чтоб запутаться? Тебе это удалось.

(102) правильно.
в (94) записана точно то же что ты написал в (102), только я не весь ряд написал, часть опустил для сокращения.

(102) приведенный пример можно тупо записать как
6,1,3,5,2,4

(104) Ничего не понял. У тебя не все "Я" есть? То есть они пронумерованы натуральным рядом, но часть почему-то опущена, а часть указана. Что происходит с пропущенными Ячейками? И чем указанные от них отличаются?
Почему ты указал Я1, но не указал Я3 в (94)?

(104) в терминах (94)?!

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

(100) в принципе, ты мне все нужные мне подсказки дал, для мну все вроде понятно...
.
просто если перестановки неупорядоченного ряда
6,1,3,5,2,4
выдавать складским как задания тяжко будет им читать типа
"возьми 5 с четвертого порядкового места" - это все равно придется транслировать в нотацию складской записи, где четвертое порядковое место окажется ячейкой номер 8 ;-)
.

(107) ну так и делаю, блин ;-)
за исключением что ячейки я могу "пронумеровать" в алгоритме от 1 до N, а в реальности нумерация не последовательная...

(108) При чем тут "складские"? Мы алгоритм обсуждаем? Или что?

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

(110) алгоритм, алгоритм обсуждаем! ;-)
.
просто мну интересно как бы в обсуждении голого "алгоритма" ты бы мне подсказку дал вот эту из (85) "...только когда свободна ячейка выше 30 - используешь её как буфер, перейдя на первый шаг алгоритма"
.
;-)

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

(112) Если ты сортируешь не все товары, то те товары, которые могут стоять где угодно обзываешь например буквой "X" - хлам :), те ячейки, которые не нужно сортировать тоже буквой "X", Если Х стоит на месте Х - значит он стоит на своем месте.
Если свободна ячейка "X" - то берешь любой X-товар стоящий не на своем месте (на значимой ячейке), и ставишь его в пустую ячейку.

(114) ээээ! я ну не совсем глупый, я это уже дотумкал в потоке сознания в (96) ;-)

Ветку прикрыл.