Есть неупорядоченный массив чисел размерностью M, где М - колво элементов массива.
Числа в массиве - любые значения от 0 до N.
Числа в массиве могут быть неуникальными.
Любим порядок. Хотим получить упорядоченный массив по убыванию.
Получить его легко - тупо отсортируем числа массива по убыванию.
.
Доступен дополнительный "буфер" (массив) размерностью K, где К - колво элементов буфера, К может быть в принципе любым от 1 до М.
.
То есть в наличии и неотсортированный массив, и отсортированный массив.
.
Какой алгоритм является оптимальным с точки зрения минимизации количества перестановок элементов исходного неотсортированного массива для получения конечного отсортированного массива (можно использовать буфер, для промежуточного хранения сортируемого массива/его чисел).
.

https://ru.wikipedia.org/wiki/Быстрая_сортировка

O(log n) - вполне себе скорость.

(0) Уверен что по "количеству перестановок"?
(1) Имел в виду наверно O(n*log n), решается естественно за О(n) при такой формулировке.

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

(2) математик я слабый... к сожалению.

(3) Может быть меньше, но сложность по количеству перестановок все-равно О(M)
Vинимальный - каждое стоящее не на своем месте поставить на свое место. Вроде достаточно одной доп. переменной для этого. Но по количеству сравнений будет О(M^2)

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

(6) Писать надо.

(5) вот у меня получается что если больше 1 переменной промежуточной - то гораздо меньше будет перестановок...

(6) для какой версии 1С то хоть нуна?

(7) ну вот я написал, но мну сомнения гложут... а так как я математик слабый - то сомнения сильные...

(9) для клюшек давай!

в принцуипе даже готов конкурс устроить с денежным призом ;-)

в качестве массива хочется ТЗ юзать для большей универсальности!

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

(12) Конкурс? Ну у тебя и юмор.
Ищем первое значение которое стоит не на своем месте, ставим его на свое место, значение по адресу куда поставили так-же ставим на "свое место" и т.д.

можно даже упростить (усложнить?) - главное чтобы были упорядочены не все элементы массива, а первые X

(15) угу и при этом нужно выполнить кучу сравнений на > < в результате да перестановок минимум а тормозиит ))

(16) Это задачу не меняет совершенно. Ровно та-же задача.

может все таки надо не минимум перестановок а быстрейший?

(17) Прочитай условие - минимизация количества перестановок, а не сравнений. Сравнений будет О(M^2)

(20) да вот и спрашиваю зачем нужен именно "минимум перестановок"?

(21)+ т.е. понятно что когда может не хватить памяти то такие алгоритмы и применяют, например можно сортировку делать прямо на hdd(ssd) из памяти одна переменная ))

(21) Практический пример? Стоит в ряд 100 бетонных маркированных блоков. Переставить в порядке убывания маркировки.

(15) хитрый какой... давай нагрузим физикой. - числа вполне реальные физ.объекты.
.
> Ищем первое значение которое стоит не на своем месте,
- найти не вопрос.
> ставим его на свое место,
"свое место" - занято. значит - осовобождаем "свое место" - оттуда "лишнее" число сдвигаем в буфер, первое число ставим на свое место.
- 2 перестановки. и "лишнее" число - в буфере.

(22) При чем тут память?

(21) потому что гоняем не электроны, а вполне себе физобъекты

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

(24) ничего не понял. Ты хочешь сказать что нужно две переменных, так как мы должны помнить пустое место (из которого мы переместили) и значение в руках?

(1) Таких сортировок не существует. Хотя бы потому, что для сортировки надо как минимум считать значения всех элементов, алгоритмы сортировок никак не могут быть лучше, чем О(n)

(28) угу.. Представь: мы двигаем палеты по складу. стоят неоптимально в ряду. надо переставить чтобы стояли оптимально.

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

(30) задача понятна теперь, всегда нужно знать прикладную область ))

(30) То есть переставлять только рядом стоящие? Не поверишь! Но оптимален пузырек! :)

в ряду есть пусте палеты..

И сложность тогда по перестановкам О(M^2)

(32)+ т.е. есть ряд паллет (с весом), есть буферный ряд куда можно переставлять временно, и есть ряд куда нужно переставить  - или нету 3-го ряда и нужно паллеты в том же 1-м ряду оставить?

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

(33) кстати да может все таки не кол-во перестановок нужно уменьшить а пройденный ими путь при передвижениях?

(36) совершенно верно. есть буферный ряд - временный и исходный ряд с палетами. все больше места нет. после окончания персеановок буферный ряд - д.б. пустой.

(37) Не нужен безразмерный буфер. Достаточно буфера на один элемент.

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

(41) а каким образом (алгоритмом) получили эту табличку пофиг в данном случае...

(38) если это облегчит решение задачи - то пусть будет так...

(41) да, две табличик а) старые места и б) новые места - их не проблема получить. получаются мгновенно.

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

это кроме 1-го ряда по буферу 2 паллеты разъедутся?

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

(45) просто если нет, то это головоломка получается если нужно переставить местами 1-ю и последнюю паллеты ))

(45) палеты таскает один человек (пока так). поэтому никто никому не мешает - взял палету - вытащил откуда-то, поставил куда-то. и т.д. пока не получим из старой - новую расстановку

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

(48) т.е. буфер он многорядный? можно поставить паллеты не в ряд а еще одним рядом? сколько максимум?

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

Исходные данные
Палета    вес
01-001-01    26
01-002-01    27
01-003-01    14
01-004-01    31
01-005-01    23
01-006-01    21
01-007-01    30
01-008-01    25
01-009-01    24
01-010-01    23
01-011-01    21
01-012-01    8
01-013-01    8
01-014-01    3
01-015-01    21
01-016-01    3
01-017-01    7
01-018-01    6
01-019-01    10
01-020-01    26
01-021-01    17
01-022-01    27
01-023-01    7
01-024-01    15
01-025-01    15
01-026-01    28
01-027-01    15
01-028-01    30
01-029-01    8
01-030-01    2
01-031-01    13
01-032-01    2
01-033-01    16
01-034-01    9
01-035-01    18
01-036-01    6
01-043-01    11
01-044-01    4
01-045-01    9
01-046-01    6
01-047-01    4
01-048-01    6
01-049-01    3
01-050-01    3
01-051-01    8
01-052-01    3
01-053-01    8
01-054-01    3
01-055-01    5
01-056-01    5
01-057-01    4
01-058-01    2
01-059-01    13
01-060-01    3
01-061-01    11
01-062-01    4
01-063-01    4
01-064-01    2
01-065-01    11
01-066-01    0
01-067-01    15
01-069-01    10
01-071-01    1
01-073-01    12
01-074-01    15
01-075-01    5
01-076-01    2
01-077-01    3
01-078-01    4
01-079-01    4
01-080-01    9
01-081-01    2
01-082-01    5
01-083-01    4
01-084-01    25
01-085-01    9
01-086-01    0
01-087-01    2
01-088-01    3
01-089-01    5
01-090-01    22
01-091-01    7
01-092-01    3
01-093-01    14
01-094-01    3
01-095-01    4
01-096-01    3
01-103-01    4
01-104-01    3
01-105-01    7
01-106-01    3
01-107-01    15
01-108-01    2
01-109-01    11
01-110-01    2
01-111-01    4
01-112-01    4
01-113-01    12
01-114-01    4
01-115-01    0
01-116-01    5
01-117-01    2
01-118-01    5
01-119-01    3
01-120-01    0
01-121-01    1
01-122-01    1
01-123-01    1
01-124-01    1
01-125-01    2
01-126-01    1
01-127-01    6
01-128-01    0
01-129-01    2
01-130-01    3
01-131-01    2
01-132-01    7
01-133-01    2
01-134-01    9
01-135-01    3
01-136-01    3
01-137-01    0
01-138-01    4
01-139-01    3
01-140-01    1
01-141-01    7
01-142-01    3
01-143-01    3
01-144-01    7

Если буфер многорядный (т.е. есть место для разъезда паллет) то алгоритм такой выходит:

1. Вычисляем любым алгоритмом таблицу откуда-куда
2. Берем 1-ю паллету, точнее не берем а вытаскиваем в буфер паллету с того места куда нужно поставить 1-ю
3. Проверяем не свободны ли места куда нужно поставить паллеты из буфера, если свободны - ставим
4. Берем следующую паллету в ряду и по пункту 2.
5. Пункт 3.

(53)+ пропустил между 2 и 3 ставим паллету на освободившееся место

(53) ну у меня так и сделано.. но гложут сомнения

Т.е. правильно

1. Вычисляем любым алгоритмом таблицу откуда-куда
2. Берем 1-ю паллету не на своем месте, точнее не берем а вытаскиваем в буфер паллету с того места куда нужно поставить 1-ю
3. Ставим паллету на освободившееся место.
4. Проверяем не свободны ли места куда нужно поставить паллеты из буфера, если свободны - ставим
5. Снова пункт 2
6. Если все паллеты на своих местах, то чистим буфер и профит...

исходно
Пал    вес
01-001-01    26
01-002-01    27
01-003-01    14
01-004-01    31
01-005-01    23
01-006-01    21
01-007-01    30
01-008-01    25
01-009-01    24
01-010-01    23
01-011-01    21
01-012-01    8
01-013-01    8
01-014-01    3
01-015-01    21
01-016-01    3
01-017-01    7
01-018-01    6
01-019-01    10
01-020-01    26
01-021-01    17
01-022-01    27
01-023-01    7
01-024-01    15
01-025-01    15
01-026-01    28
01-027-01    15
01-028-01    30
01-029-01    8
01-030-01    2
01-031-01    13
01-032-01    2
01-033-01    16
01-034-01    9
01-035-01    18
01-036-01    6
01-043-01    11
01-044-01    4
01-045-01    9
01-046-01    6
01-047-01    4
01-048-01    6
01-049-01    3
01-050-01    3
01-051-01    8
01-052-01    3
01-053-01    8
01-054-01    3
01-055-01    5
01-056-01    5
01-057-01    4
01-058-01    2
01-059-01    13
01-060-01    3
01-061-01    11
01-062-01    4
01-063-01    4
01-064-01    2
01-065-01    11
01-066-01    0
01-067-01    15
01-069-01    10
01-071-01    1
01-073-01    12
01-074-01    15
01-075-01    5
01-076-01    2
01-077-01    3
01-078-01    4
01-079-01    4
01-080-01    9
01-081-01    2
01-082-01    5
01-083-01    4
01-084-01    25
01-085-01    9
01-086-01    0
01-087-01    2
01-088-01    3
01-089-01    5
01-090-01    22
01-091-01    7
01-092-01    3
01-093-01    14
01-094-01    3
01-095-01    4
01-096-01    3
01-103-01    4
01-104-01    3
01-105-01    7
01-106-01    3
01-107-01    15
01-108-01    2
01-109-01    11
01-110-01    2
01-111-01    4
01-112-01    4
01-113-01    12
01-114-01    4
01-115-01    0
01-116-01    5
01-117-01    2
01-118-01    5
01-119-01    3
01-120-01    0
01-121-01    1
01-122-01    1
01-123-01    1
01-124-01    1
01-125-01    2
01-126-01    1
01-127-01    6
01-128-01    0
01-129-01    2
01-130-01    3
01-131-01    2
01-132-01    7
01-133-01    2
01-134-01    9
01-135-01    3
01-136-01    3
01-137-01    0
01-138-01    4
01-139-01    3
01-140-01    1
01-141-01    7
01-142-01    3
01-143-01    3
01-144-01    7

итог
пал    вес
01-001-01    31
01-002-01    30
01-003-01    30
01-004-01    28
01-005-01    27
01-006-01    27
01-007-01    26
01-008-01    26
01-009-01    25
01-010-01    25
01-011-01    24
01-012-01    23
01-013-01    23
01-014-01    22
01-015-01    21
01-016-01    21
01-017-01    21
01-018-01    18
01-019-01    17
01-020-01    16
01-021-01    15
01-022-01    15
01-023-01    15
01-024-01    15
01-025-01    15
01-026-01    15
01-027-01    14
01-028-01    14
01-029-01    13
01-030-01    13
01-031-01    12
01-032-01    12
01-033-01    11
01-034-01    11
01-035-01    11
01-036-01    11
01-043-01    10
01-044-01    10
01-045-01    9
01-046-01    9
01-047-01    9
01-048-01    9
01-049-01    9
01-050-01    8
01-051-01    8
01-052-01    8
01-053-01    8
01-054-01    8
01-055-01    7
01-056-01    7
01-057-01    7
01-058-01    7
01-059-01    7
01-060-01    7
01-061-01    7
01-062-01    6
01-063-01    6
01-064-01    6
01-065-01    6
01-066-01    6
01-067-01    5
01-069-01    5
01-071-01    5
01-073-01    5
01-074-01    5
01-076-01    5
01-075-01    5
01-077-01    4
01-078-01    4
01-079-01    4
01-080-01    4
01-081-01    4
01-082-01    4
01-083-01    4
01-084-01    4
01-085-01    4
01-086-01    4
01-087-01    4
01-088-01    4
01-134-01    4
01-135-01    4
01-089-01    3
01-090-01    3
01-091-01    3
01-092-01    3
01-093-01    3
01-094-01    3
01-095-01    3
01-096-01    3
01-103-01    3
01-104-01    3
01-105-01    3
01-106-01    3
01-107-01    3
01-108-01    3
01-109-01    3
01-110-01    3
01-111-01    3
01-112-01    3
01-113-01    3
01-114-01    3
01-136-01    3
01-115-01    2
01-116-01    2
01-118-01    2
01-119-01    2
01-120-01    2
01-121-01    2
01-122-01    2
01-123-01    2
01-124-01    2
01-125-01    2
01-126-01    2
01-117-01    2
01-127-01    2
01-138-01    2
01-128-01    1
01-129-01    1
01-139-01    1
01-140-01    1
01-141-01    1
01-142-01    1
01-143-01    1
01-130-01    0
01-131-01    0
01-132-01    0
01-133-01    0
01-137-01    0
01-144-01    0

Получилось
Требуемый размер буфера = 20
Мест без движения = 18
Количество перестановок = 165
.
есть помарки в алгоритме, но они несущественные.
.
вот примерно так6
-- шаг: 001 --
01-001-01(26) -> *БУФЕР-БОЛЬШОЙ*(1)
01-004-01(31) -> 01-001-01(пусто)

-- шаг: 002 --
01-002-01(27) -> *БУФЕР-БОЛЬШОЙ*(2)
01-028-01(30) -> 01-002-01(пусто)

-- шаг: 003 --
01-003-01(14) -> *БУФЕР-БОЛЬШОЙ*(3)
01-007-01(30) -> 01-003-01(пусто)

-- шаг: 004 --
01-026-01(28) -> 01-004-01(пусто)

-- шаг: 005 --
01-005-01(23) -> *БУФЕР-БОЛЬШОЙ*(4)
*БУФЕР-БОЛЬШОЙ* (27) -> 01-005-01(пусто)

-- шаг: 006 --
01-006-01(21) -> *БУФЕР-БОЛЬШОЙ*(4)
01-022-01(27) -> 01-006-01(пусто)

-- шаг: 007 --
*БУФЕР-БОЛЬШОЙ* (26) -> 01-007-01(пусто)

-- шаг: 008 --
01-008-01(25) -> *БУФЕР-БОЛЬШОЙ*(4)
01-020-01(26) -> 01-008-01(пусто)

-- шаг: 009 --
01-009-01(24) -> *БУФЕР-БОЛЬШОЙ*(5)
*БУФЕР-БОЛЬШОЙ* (25) -> 01-009-01(пусто)

-- шаг: 010 --
01-010-01(23) -> *БУФЕР-БОЛЬШОЙ*(5)
01-084-01(25) -> 01-010-01(пусто)

-- шаг: 011 --
01-011-01(21) -> *БУФЕР-БОЛЬШОЙ*(6)
*БУФЕР-БОЛЬШОЙ* (24) -> 01-011-01(пусто)

-- шаг: 012 --
01-012-01(8) -> *БУФЕР-БОЛЬШОЙ*(6)
*БУФЕР-БОЛЬШОЙ* (23) -> 01-012-01(пусто)

ну и т.д.

то есть алгоритм как в (56), но гложут сомнения...

ушел на автобус.. с надеждой...

оп понял нужен банальный прогон действий виртуально тогда будет M+1 перестановок ))

т.е. в коде (59) 2-й шаг другой

-- шаг: 001 --
01-001-01(26) -> *БУФЕР-БОЛЬШОЙ*(1)
01-004-01(31) -> 01-001-01(пусто)

Счас место 4 свободно ищем что туда нужно поставить и ставим

-- шаг: 002 --
01-026-01(28) -> 01-004-01(пусто)

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

(62)+ эээ насчет M+1 погорячился, но уменьшить до минимума перестановок можно

(63)+ правильнее будет сказать в самом лучшем случае будет M+1 перестановок, если последним поставленным на место будет единственный элемент который засунули в буфер ))

Для а=1 по м цикл
   пустоеместо=а;
   значение=знач[а];
   Пока значениевотсортированноммассиве[пустоеместо]<>значение Цикл
       темп=найтигденаходится в знач(значениевотсортированноммассиве[пустоеместо]);
       переместить с темп в пустоеместо;
       пустоеместо=темп;
   КонецЦикла;
КонецЦикла

Каждый элемент стоящий не на своем месте будет перемещен ровно один раз, сразу на правильное место.

(66) не не не может с первичной раскладкой не повезти, например самый хреновый случай все элементы попарно нужно переставить ))

1 и 2, 3 и 4 и т.д.

Задачка то действительно весьма конкурсная, узнать минимально необходимое кол-во перестановок ))

(67) Ну и?

(67)+ если перестановка это взять паллету, переставить сразу на нужное место или в буфер, или из буфера в нужное место

(69) перестановка что такое? если использован буфер то это одна или все таки 2 перестановки?

Первое стоит не на своем месте, поднимаем его, смотрим какое должно стоять на нем - второй элемент массива.
Ставим его на первое место, первое опускаем на второе.
После этого второе стоит на своем месте. Третье не на своем, поднимаем его, смотрим какое должно стоять на его месте. Четвертое. Ставим четвертое на третье место. Поднятое опускаем на четвертое. Все четыре стояли не на своих местах. Четыре перестановки мы и сделали.

(71) А не важно, и так и так минимально возможное количество перестановок.

(71) каждое не на своем месте ровно один раз снять (с неправильного места), и один раз поставить (на правильное место). И явно это минимальное количество перестановок.

(72) это если 2 погрузчика работают то да супер а если 1?

Первое стоит не на своем месте, поднимаем его, +1
смотрим какое должно стоять на нем - второй элемент массива.
Ставим его на первое место, +1
первое опускаем на второе. +1

После этого второе стоит на своем месте.

Третье не на своем, поднимаем его +1
, смотрим какое должно стоять на его месте. Четвертое. Ставим четвертое на третье место. +1
Поднятое опускаем на четвертое. +1
Все четыре стояли не на своих местах. Четыре перестановки мы и сделали.

Итого 6 перестановок!

(75) И все равно это минимальное количество перестановок.

Вообщем задача решается за от M+1 до M+M/2 перестановок в случае 1-го погрузчика

(76) да минимальное согласен, и алгоритм (65) походу правильный, только бы еще счетчик перестановок добавить ))

(NS) если в курсе что такое вектор признаков и приходилось заниматься классификацией/кластеризацией то можешь помочь?

(79) Я спать хочу. :)
Конечно я знаю что такое вектор признаков.

(80) это не срочно ;)

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

(81)+ сейчас я решаю ее правилами 2-х видов "хорошо" и "плохо" и сравнением кол-ва этих правил которым удовлетворяет подстрока

но это очень медленно, так как проверяются все подстроки на соответствие всем правилам - полный перебор

вот и хочется ускорить заюзав многомерное пространство признаков подстрок

А где условие то?

(83) А отдельную ветку не создавал, писал в разных сорри

Как насчет очень умной загрузки разных табличных документов из таблиц excel'я?
Тех же накладных из формы Торг-12 и т.д.

У нас сейчас полуручной режим сначала правим ексель ручками, а это очень долго потому что название товара нужно разделить на вид товара, название, артикул и т.д. в форме торг-12 оно одной  строкой идет а нужно раздельно.
Вот и приходится извращаться с НАЙТИ() и ПСТР() и только потом грузить готовую форму.

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

Да конечно проще всего согласовать с поставщиками формат  электронных накладных, вот тока скинуть накладную в экселе может любой манагер любого контрагента и выгрузить в DBF или чем еще не все и притом что делать когда поставщиков несколько десятков как со всеми согласовать?

У меня сейчас сделан некий набросок такой программы:
1. Открывается таблица исходная
2. Пользователь отмечает нужные и ненужные колонки/строки - при этом автоматически все похожие строки/колонки также выделяются цветом, т.е. попадают в нужные и ненужные.
Остальные этапы типа добавление доп.колонок и перенос в них данных из существующих ячеек и прочее пока в обдумывании.


В принципе даже существует аналог для подобного он он слишком сложный для использования когда много разных форматов а не один настроенный.
http://infostart.ru/public/21810/

пример оттуда же

1-я строка кольцо арт.111 17,5 585 3,5 гр. фианит
2-я строка 222 кольцо 18 4,0 гранат
3-я строка кольцо 333 (925) 5,4 гр куб циркония

нужно выделить для каждой строки: артикул, вид изделия, вес, пробу, размер и вставки

вот как это сделать если в строке оно может быть как угодно

(85)+ уже решена задача авто выбора нужных и отбрасывания ненужных ячеек, т.е. всяческие шапки на каждой странице и прочее подобное выкидывает автоматом

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

(70) помещение вбуфер - это есть отдельная перестановка.
Перестановка - элементарное перемещение (откуда, куда)

(62) без разницы - у меня это делается 4 шагом, а не вторым. т.к к увеличению затрат это не приводит, и у тебя и у меня перестановка 01-026-01(28) -> 01-004-01(пусто) производится без дополнительных промежуточных движений.

(75) да, 6 перестановок

если вы уже про многомерные массивы, то там вероятность быстрее считать чем тупо перебором

(65) попытаюсь вкурить...

(66) и (65) вот ты пишешь, елы-палы...

> Каждый элемент стоящий не на своем месте будет перемещен ровно один раз, сразу на правильное место.

- не выйдет. Возьмем колво элементов = N.
Рассмотрим случай, когда все элементы стоят не на своих местах.

Очевидно, что "каждый элемент, стоящий не на своем месте будет перемещен !!ровно один раз, сразу на правильное место!!" - неверно, т.к. любой элемент не может быть перемещен сразу на правильное свое место - так как это место ЗАНЯТО ДРУГИМ элементом. Предварительно правильное место надо освободить (переместить в буфер), то есть совершить более одного перемещения для положения элемента на правильное место.

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

В худшем случае можно получитm оценку макcимального количества перемещений = 2N, все элементы перемещаются в буфер (N перемещений), из буфера каждый элемент кидается на свое место которое заведомо свободно (еще N перемещений).

для конкретной произвольной расстановки - каков будет порядок величины требуемых перемещений по сравнени с N...?

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

(95) дык он уже описан в (65)

Сформулирую задачу еще раз, максимально близко к реальности физической ;-)
1. есть линейный ряд ячеек.
2. ячейки нумеруются от 1 до N.
3. есть М товаров, где М не больше N
   М=N - в каждой ячейке лежит разный товар (один и тот же товар не может занимать больше 1 ячейки), свободных ячеек нет.
   М<N - в каждой ячейке лежит разный товар, есть свободные ячейки
4. каждый товар имеет произвольный вес, пустые ячейки соответственно имеют вес=0.
5. Имеется свободное буферное пространство размером N ячеек (что эквивалентно неограниченному размеру буфера)
6. требуется упорядочить расстановку товаров в ряду по убыванию веса с минимально возможным количеством перемещений товаров между ячейками/буфером (и сообщить сколько максимально задейстовано буферных ячеек).
7. Перемещения выполняет 1 человек.
8. Товар может находиться либо в ячейке, либо в буфере, в "воздухе" не болтается...
.
пункт 6 может быть дополнительно ограничен условием на размер буферных ячеек: сколько надо перемещений если буферная ячейка  =1? = 2..?

(94) от N+1 до N+N/2 точнее только прогоном алгоритма в (65) с добавленным счетчиком

ну или нахождением кол-ва паллет которые нужно поменять просто местами, каждая такая пара паллет дает +1 к N

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

(97) криво описан, где буфер там?
NS уж сильно абcтрагировался... $-)

(100) дык не вышло у него больше одного значения в буфер засунуть ))

значение у него буфер

(101) т.е. даже самый оптимальный алгоритм не требует больше одного буферного места

(99) в (65) криво - хотя бы потому что если помещение в буфер это оператор
значение=знач[а];
то в лучшем случае расстановки (когда все товары стоят на своих местах) товар сделает лишнее движение по буферу (или останется в буфере)

(102) вот сомневаюсь я...

(103) дык это ж алгоритм а не прога управления роботом-погрузчиком ))

(105) да пофиг робот или прога/алгоритм.. последовательность шагов/перемещений нужна

Вот совсем близко к реальности, живые данные
Товар-Ячейка-Вес
(вес - это некий обобщенный критерий), м.б.=0
ячейка может быть пустая, пустая ячейка тоже имеет вес=0
.
Товар    Ячейка    Вес
630044    01-001-01    26
420244    01-002-01    27
900638    01-003-01    14
420256    01-004-01    31
900092    01-005-01    23
420258    01-006-01    21
900082    01-007-01    30
420616    01-008-01    25
900094    01-009-01    24
630880    01-010-01    23
428132    01-011-01    21
630414    01-012-01    8
900884    01-013-01    8
595056    01-014-01    3
900048    01-015-01    21
595066    01-016-01    3
634522    01-017-01    7
634524    01-018-01    6
630886    01-019-01    10
420644    01-020-01    26
900076    01-021-01    17
900620    01-022-01    27
630536    01-023-01    7
668220    01-024-01    15
900870    01-025-01    15
378878    01-026-01    28
900872    01-027-01    15
428260    01-028-01    30
900874    01-029-01    8
594124    01-030-01    2
794003    01-031-01    13
594128    01-032-01    2
900020    01-033-01    16
594222    01-034-01    9
900022    01-035-01    18
594225    01-036-01    6
900026    01-043-01    11
892066    01-044-01    4
900030    01-045-01    9
892064    01-046-01    6
900032    01-047-01    4
318022    01-048-01    6
900034    01-049-01    3
318512    01-050-01    3
900036    01-051-01    8
892044    01-052-01    3
900040    01-053-01    8
892042    01-054-01    3
668142    01-055-01    5
892040    01-056-01    5
900043    01-057-01    4
892018    01-058-01    2
900044    01-059-01    13
892016    01-060-01    3
630884    01-061-01    11
892014    01-062-01    4
900049    01-063-01    4
863152    01-064-01    2
900050    01-065-01    11
623570    01-066-01    0
900054    01-067-01    15
900056    01-069-01    10
900070    01-071-01    1
900060    01-073-01    12
888425    01-074-01    15
900062    01-075-01    5
863154    01-076-01    2
900063    01-077-01    3
602020    01-078-01    4
601250    01-079-01    4
863080    01-080-01    9
601028    01-081-01    2
602024    01-082-01    5
595064    01-083-01    4
888225    01-084-01    25
594012    01-085-01    9
    01-086-01    0
892320    01-087-01    2
637410    01-088-01    3
668140    01-089-01    5
643555    01-090-01    22
900676    01-091-01    7
594018    01-092-01    3
900084    01-093-01    14
594020    01-094-01    3
637414    01-095-01    4
594022    01-096-01    3
900832    01-103-01    4
594024    01-104-01    3
631424    01-105-01    7
594026    01-106-01    3
900634    01-107-01    15
594028    01-108-01    2
900636    01-109-01    11
892068    01-110-01    2
900810    01-111-01    4
892092    01-112-01    4
900812    01-113-01    12
892094    01-114-01    4
630329    01-115-01    0
892090    01-116-01    5
630889    01-117-01    2
594244    01-118-01    5
630914    01-119-01    3
630330    01-120-01    0
594236    01-121-01    1
594328    01-122-01    1
897422    01-123-01    1
594520    01-124-01    1
892340    01-125-01    2
594524    01-126-01    1
420645    01-127-01    6
630331    01-128-01    0
897420    01-129-01    2
630364    01-130-01    3
892322    01-131-01    2
634520    01-132-01    7
900644    01-133-01    2
630690    01-134-01    9
896962    01-135-01    3
630890    01-136-01    3
623344    01-137-01    0
630917    01-138-01    4
630916    01-139-01    3
900698    01-140-01    1
900898    01-141-01    7
896964    01-142-01    3
906320    01-143-01    3
637428    01-144-01    7

01-086-01 - пустая ячейка

если нужена всего 1 буферная ячейка - ну сильно сомнительно мне это... не получается у мну так...

ага.. вроде кажется начинаю въезжать...

Я не хочу быть самым богатым человеком на кладбище. Засыпать с чувством, что за день я сделал какую-нибудь потрясающую вещь — вот что меня интересует. Стив Джобс, 1996 г.
- ну точняк про меня...

все, понял (вроде) что в (65) NS написал...
мдя.. пойти застрелиться что ли...

Притоплю пока.. до разборок..

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

.. и сращзу все тсановится интереснеее.. (?)

(6) выгрузить массив в список и отсортировать

(114)  алгоритм при этом не меняется.

(0) возьми алгоритм QuickSort, к примеру на C, и перепиши на 1С  - это легко, я даже когда то делал для прикола, только оно потерялось.

собственно,  http://infostart.ru/public/128251/

(116) мне нравится Ваш юмор но надо все таки призаки )) или :) ставить...

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

Так что - массив может потребоваться только для того, чтобы сохранить данные перестановок до того, как они будут сделаны и избежать многократной перестановки одного элемента.
Для 1С, насколько я понимаю, копирование переменных не приводит к копированию объектов, так что перестановка не даёт большой нагрузки на память, а вот сравнение элементов - обращение к полям объекта - даёт некоторую нагрузку.

(121) Ты о чем?

(122) Я о том, что когда идёт оценка O(n), то оцениваются какие-то "сферические операции в вакууме".
В реальных данных, может оказаться, что одна перестановка стоит по затратам времени десяти и более сравнений.

Не забываем, также, что в базах данных сами записи вообще не затрагиваются - вместо перестановок создаётся дерево индекса.

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

читаю.