Перестановка

есть список list_a=(a1 a2 a3 ... aN).
начинаем перестановки с a1:
1) меняем местами a1 и а2, получаем новый список
(a2 a1 a3 ... aN)
2)  меняем местами a1 и а3, получаем новый список
(a3 a2 a1 ... aN)
...........................
меняем местами a1 и аN, получаем новый список
(aN a2 a3 ... a1)
повторяем теже процедуры с a2, переставляя a2 только с теми элементами, которые стоят после a2 (с a3, a4, ... aN).
если перставлять a2 с a1, то получим повторяющийся вариант
(a2 a1 a3 ... aN), который был уже получен на шаге 1).
алгоритм сочинил  находу, возможны изъяны.
------------------------------------------------------------
"Никому не верь!"     (C) X-Files

Нет, какие преподаватели, они 6 лет назад закончились :)
Это будет прога по оптимальной нарезке заготовок из проката, я уже вышел на более менее оптимальные результаты с:

(setq VARIANTS NIL)
      (setq ELEMENT NIL)
      (setq PREFIX NIL)
      (setq SUFFIX NIL)
      (setq ELEMENT (list (car DETAILLIST)))
      (setq PREFIX (list (cadr DETAILLIST)))
      (setq SUFFIX (cddr DETAILLIST))
      (setq VARIANTS (append VARIANTS (list (append ELEMENT PREFIX SUFFIX))))
      (setq TEMPLIST (append PREFIX ELEMENT SUFFIX))
      (setq N (length DETAILLIST))
      (setq N (- (repeat (1- (length DETAILLIST)) (setq N (+ N (1- (length DETAILLIST))))) 2))
      (repeat N
        (setq VARIANTS (append VARIANTS (list TEMPLIST)))
        (if    SUFFIX
          (progn
        (setq PREFIX (append PREFIX (list (car SUFFIX))))
        (setq SUFFIX (cdr SUFFIX))
        (setq TEMPLIST (append PREFIX ELEMENT SUFFIX))
        ) ;_ end of progn
          (progn
        (setq ELEMENT (list (car TEMPLIST)))
        (setq PREFIX (list (cadr TEMPLIST)))
        (setq SUFFIX (cddr TEMPLIST))
        (setq TEMPLIST (append PREFIX ELEMENT SUFFIX))
        ) ;_ end of progn
          ) ;_ end of if
        ) ;_ end of repeat

но хочется узнать на сколько они оптимальны? :)

1. т.к. прога до конца не оформлена, то

(setq VARIANTS NIL)
(setq ELEMENT NIL)
(setq PREFIX NIL)
(setq SUFFIX NIL)

просто обнуляют переменные.
2.

(setq N (length DETAILLIST))
(setq N (- (repeat (1- (length DETAILLIST)) (setq N (+ N (1- (length DETAILLIST))))) 2))
(repeat N ...)

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

(while (not (equal TEMPLIST DETAILLIST)) ...)

т.о. для списка '(1 2 3 4) получаем:

(
(1 2 3 4)
(2 1 3 4)
(2 3 1 4)
(2 3 4 1)
(3 2 4 1)
(3 4 2 1)
(3 4 1 2)
(4 3 1 2)
(4 1 3 2)
(4 1 2 3)
(1 4 2 3)
(1 2 4 3)
)

Логика прослеживается?
Тогда получим:

(setq ELEMENT (list (car DETAILLIST)))
(setq PREFIX (list (cadr DETAILLIST)))
(setq SUFFIX (cddr DETAILLIST))
(setq VARIANTS (list (append ELEMENT PREFIX SUFFIX)))
(setq TEMPLIST (append PREFIX ELEMENT SUFFIX))
(while (not (equal TEMPLIST DETAILLIST))
  (setq VARIANTS (append VARIANTS (list TEMPLIST)))
  (if SUFFIX
    (progn
      (setq PREFIX (append PREFIX (list (car SUFFIX))))
      (setq SUFFIX (cdr SUFFIX))
      (setq TEMPLIST (append PREFIX ELEMENT SUFFIX))
      ) ;_ end of progn
    (progn
      (setq ELEMENT (list (car TEMPLIST)))
      (setq PREFIX (list (cadr TEMPLIST)))
      (setq SUFFIX (cddr TEMPLIST))
      (setq TEMPLIST (append PREFIX ELEMENT SUFFIX))
      ) ;_ end of progn
    ) ;_ end of if
  ) ;_ end of repeat
VARIANTS

3.Длина запускаемого списка DETAILLIST в среднем около 30-40 элементов.

По поводу N в пункте 2. > DMS (2003-11-10 08:38:19) я немного поторопился, нельзя менять на цикл, т.к. могут попасться две одинаковых заготовки и цикл остановиться, так что код в > DMS (2003-11-06 16:39:57) остаётся в силе, думаю назначение N уже понятно, а как оно получается на пальцах не объясниш, нужно расписать на бумажке.

> Сергей Попадьин
Всё правильно, потеряно ровно половина вариантов, далее чем длиннее список, тем потери будут расти в геометрической прогрессии, но в этом как я понимаю и вся прелесть :)
Список из 38 элементов обрабатывается 00:02:36, причём из [5.2302E+44] возможных обрабатывается всего лишь [1406]
вариантов, а результаты вполне удовлетворительны, как и говорил хочу просто проверить их удовлетворительность, пускай комп хоть всю ночь считает, а утром приду и проверю результат.
Просто хочу знать подойдёт такой алгоритм или нет, у меня с этой ссылкой что-то пока туговато :(

Не вдаваясь в предудыщие алгоритмы, касательно задачи оптимальной нарезки проката хочу сказать следующее:
1. В пределах одной заготовки порядок деталей не имеет значения, так как их общая длина все равно одна и та же.
Поэтому, как мне кажется, алгоритм должен быть построен не на полном переборе вариантов комбинаторных разложений, а подбором нужной группы деталей на каждую заготовку.
Иначе для большого списка деталей расчет будет ОЧЕНЬ ОЧЕНЬ долгим!!!!!
2. Первой деталью на каждую новую заготовку всегда надо ложить самую длинную деталь и ей не варьировать. Это утверждение основано чисто логическом заключении о том, что такая деталь обычно все портит, а рано или поздно ее все равно придется положить.
3. Нужно выработать четкие критерии оптимальности. Кол-во заготовок это первый критерий. Но в огромном кол-ве вариантов кол-во заготовок будет одно и тоже, но отличаться разной степенью заполнения.
И тут возника.т вопросы:
- стоит ли искать лучшее, если очевидно что еще одну заготовку сократить не удастся (например, просто начальная сумма длин деталей больше длины заготовок). Можно просто прервать перебор
- или же важны длины остатков. Тогда нужно ввести критерий полезного остатка (по длине) и смотреть сколько полезных остатков получится. Тогда критерий такой: максимальная длина ПОЛЕЗНЫХ остатков при минимуме заготовок.
Я занимался похожей задачей долго. И для профиля и для прямоугольных плит. Еще раз суть моего высказывания: НЕ РЕШАЙ ЗАДАЧУ ПОЛНЫМ ПЕРЕБОРОМ!!! Ничего страшного не случится, если найденный тобой вариант будет хуже гипотетически оптимального на пару процентов. Этот самый оптимальный вариант все равно никто не узнает!!!

> VH
:)
VH, Вы просто ГЕНИЙ!
Громадное СПАСИБО!
Сразу пока не могу разобрать принципа, но обязательно это сделаю.
Ещё раз СПАСИБО!

> Олег
1. Абсолютно согласен, но до реального воплощения пока далеко.
2. Так и есть запускаемый список сортируется по убыванию и чисто из алгоритма обработки первой всегда кладётся самая длинная, кстати, самый первый вариант проги и был основан только на убывающем списке, но результаты показали, что есть лучшие варианты.
3. У меня пока два критерия отбора:
число остатков, а следовательно и число используемых прокатных профилей должно быть минимальным
максимальный остаток должен быть максимальным (туфталогия какая-то получилась :)
про полезные остатки тоже думал, но ведь их можно всегда вложить в список обработки как деталь и тогда мы всё-равно придём к верхним двум критериям.
В любом случае хочу поблагодарить всех учавствовавших в обсуждении, конечно, особое СПАСИБО VH, чтоб я без него делал!
Желаю Всем удачи!

> VH
Спасибо за пояснения, пытаюсь разобраться, пробовал распечатав на бумажке список, найти очевидную логику перестановок - безуспешно.
А вот и первые результаты:
с моим алгоритмом
----------------------------------------------------------
Max length: [5800]
Cutting width: [2.5]
(3500.0 3200.0 2900.0 2600.0 2200.0 1800.0 1200.0 800.0)
List length: [8]
Total list elements length: [18200.0]
Wait a minute, processing data...
Done in 00:00:01
Processed [56] variants of the [40320] possible.
Remainders: (292.5 395.0 295.0 3997.5)
-------------------------Cuttings-------------------------
1 (1200.0 800.0 3500.0)
2 (3200.0 2200.0)
3 (2900.0 2600.0)
4 (1800.0)
----------------------------------------------------------
с алгоритмом VH
----------------------------------------------------------
Max length: [5800]
Cutting width: [2.5]
(3500.0 3200.0 2900.0 2600.0 2200.0 1800.0 1200.0 800.0)
List length: [8]
Total list elements length: [18200.0]
Wait a minute, processing data...
Done in 00:18:14
Processed [40320] variants of the [40320] possible.
Remainders: (592.5 295.0 95.0 3997.5)
-------------------------Cuttings-------------------------
1 (3200.0 1200.0 800.0)
2 (2600.0 2900.0)
3 (3500.0 2200.0)
4 (1800.0)
----------------------------------------------------------
В первом приближении одно и тоже, но есть над чем подумать.

> Олег
Не, Олег, не 18 секунд, а 18 минут, а мой 1 секунда!!!
Я полностью с Вами согласен, конечно, откажусь от полного перебора, но после наработки статистики, хотя бы вариантов 10 посчитать и оценить разницу. Пока даже не могу себе представить сколько будет считаться вариант из 30 элементов.
Хочу сказать пару слов про критерии, добавил ещё один, т.е. если длины списков остатков равны и max элементы равны, то следует выбрать вариант у которого min элемент наименьший.
Жаль, пока не дают спокойно до конца доделать, а руки чешуться-я-я :)

> VH
Поздно :)
Функции уже соответственно переименованы в VHSHIFT VHLIST VHSORT, так сказать по имени их создателя :)

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

Мой анти-рекурсивный подход к сабжу:

(defun ins (li e)
(setq n 0)(setq lt nil)
(
repeat (length li)
(setq lt (append lt (list (append
(reverse (cdr (member (nth n li) (reverse li))))
(cons e (member (nth n li) li))))))
(setq n (1+ n))
)
(append lt (list (reverse (cons e (reverse li)))))
)
(setq ls '(1 2 3 4 5)) [b];;;входной список[/b]
(setq lt '((1))) [b];;;первый атом списка[/b]
(setq m 0)
(
repeat (1- (length ls))
(setq m (1+ m))(setq lz nil)
(foreach sp lt (setq lz (append lz (ins sp (nth m ls)))))
(setq lt lz)
)
(length lt)