Задача: Есть N-количество заготовок. Необходимо создать матрицу всех возможных комбинаций.

Есть еще какой-нибудь вариант кроме цикла в цикле?

(0) Чем плох цикл?

цикл включает дублирующиеся варианты
при N>20 слишком много вариантов.

пример
множество 0,1,2

1.цикл
0;1;2;0,1;0,2;0,1,2;1,0;1,2;1,0,2;1,2,0;2,0;2,1;2,1,0;2,0,1

2. Нужно
0;1;2;0,1,2;0,1;0,2;1,2;2,0

фильтр не предлагать, ибо смысл не в том чтобы не было лишних вариантов, а в ресурсах требуемых на расчет матрицы вариантов

2. Нужно
0;1;2;0,1,2;0,1;0,2;1,2

лишний вариант был =)

(5) Логичнее тогда так:
0;1;2;0,1;0,2;1,2;0,1,2;
Цикл с увеличением числа элементов.

Я ничего не понял

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

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

Реализация: самое простое, это у каждого варианта задать разный порядок. Допустим так (номер варианта - код):
1 - 1
2 - 10
3 - 100
4 - 1000
5 - 10000
и т.д.

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

Пример:
Число 11001 - это 1, 4, 5.
Число 11 - это 1, 2.
Число 1010 - это 2, 4.
Число 11111 - это 1, 2, 3, 4, 5

(5) Логичнее тогда так:
0;1;2;0,1;0,2;1,2;0,1,2;
Цикл с увеличением числа элементов.

Все равно будут дубли. Нужна так называемая перестановка без повторений.

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

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

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

1 - 1
2 - 10
3 - 100
4 - 1000
5 - 10000

и т.д.

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

Пример:
Число 11001 - это 1, 4, 5.
Число 11 - это 1, 2.
Число 1010 - это 2, 4.
Число 11111 - это 1, 2, 3, 4, 5

Не покатит. в последовательности может быть несколько одинаковых элементов

(10) Почему?
Давай на примере:
Число 12001 - это 1, 4, 4, 5.
Число 12 - это 1, 1, 2.
Число 1050 - это 2, 2, 2, 2, 2, 4.
Число 13112 - это 1, 1, 2, 3, 4, 4, 4, 5

(11) Идея хороша при небольшом количестве разрядов. Уж не помню, на каких числах у меня запрос захлебываться начал...
Если идею дополнить более прогрессивным вариантом кодирования/декодирования переменных, то будет вообще бомба, но я в этом не силен :)

(9) Какие дубли в приведенной последовательности?
Это не перестановки, а сочетания без повторений .

Опишу ситуацию подробно.
Производство пластиковых окон. Оптимизация по распилу профиля ПВХ перед выгрузкой на станок резки.

В массиве заготовок допустим на 3 изделия с габаритами: 1300*1200,2080*680,1300*700 будут:

1300
1300
1200
1200
2080
2080
680
680
1300
1300
700
700

длина одного хлыста профиля 6.5м. Необходимо найти наиболее удачные комбинации с минимальными отходами. Для этого надо СОБРАТЬ ВСЕ ВОЗМОЖНЫЕ ВАРИАНТЫ без повторов, исключив варианты превышающие длину хлыста и далее уже определить оптимальный

Сейчас, пока думал пришел к мысли что можно ограничить число элементов в варианте путем вычисления ДлинаХлыста/МинимальнаяЗаготовка.Это сократит количество вариантов на много порядков.

Но все равно никак не могу придумать алгоритм перестановки без дублей

просто допустим количество вариантов при 6 элементах это уже 720 вариантов без повторений, с повторами намного больше. а при нормальной выгрузке 50 изделий число элементов 200
Никаких ресурсов не хватит

(14) Я ничего не понял... Тебе из профиля нужно сделать 3 рамы с габаритами 1300*1200, 2080*680, 1300*700 или чо?

надо оптимизировать распил. т е надо наиболее оптимально подобрать заготовки друг к другу чтобы общая длинна была как можно ближе к 6.5м
Например
700+700+1300+1300+1200+1300 = 6500
2080+2080+680+1200 = 6040
2080+1300+1200 = 4580

в итоге разрез 3 палок с 1 нет отхода, со второй 460мм,с третьей остаток 1920мм

(17) (18) Слабак!
700+700+1300+1300+1200+1300 = 6500
2080+1300+1200+680+1200 = 6460
2080+2080 = 4160
с 1 - нет отхода
с 2 - отход 40 мм
с 3 - остаток 2340 мм

=))

Идеальный результат получен. Осталось написать код, который это сможет сделать :)

(19) Нашел ошибку, в (17) она тоже есть - один кусок 2080 лишний.
В итоге результат:

700+700+1300+1300+1200+1300 = 6500
2080+1300+1200+680+1200 = 6460
2080 = 2080
с 1 - нет отхода
с 2 - отход 40 мм
с 3 - остаток 4420 мм

(17) (18) Слабак!
700+700+1300+1300+1200+1300 = 6500
2080+1300+1200+680+1200 = 6460
2080+2080 = 4160

с 1 - нет отхода
с 2 - отход 40 мм
с 3 - остаток 2340 мм

=))

как вариант =)

просто 460 это ходовой остаток а не утиль =)

вот и проблема в алгоритме сочетания который не повесит машину при N>12

циклы вешают при N>9 съедается 7 гигов оперативы и платформа благополучно схлопывается ((((

если навешивать условия записи в матрицу то время обработки измеряется сутками

Напоминает задачку про рюкзак

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

а хотя при 9 элементах из которых ходовые будут только варианты с 6. но проблема в повторах которые увеличивают обрабатываемые данные на несколько порядков. Исключение их даст возможность обрабатывать результат до 9 элементов. Хотя тоже проблематично потом будет работать с таблицей в 362880 строк

(27) А в чем проблема, дело компьютера обрабатывать данные, так пусть молотит. Если проиндексировать таблицу, еще быстрее будет работать.

А где припуск на толщину дика пилы?

(26) Я так понял, что нет типовых размеров заготовок и они могут быть произвольной длины...

самое смешное что будет как всегда:

"мне плевать на вашу матрицу раскроя, мастеру виднее" :)

(30) Но вот возьмем и пересчитаем все произвольные наперед.
Как вариант конечно. Может ТС придумает как на ходу посчитать быстро.

А где припуск на толщину дика пилы?

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

самое смешное что будет как всегда:

"мне плевать на вашу матрицу раскроя, мастеру виднее" :)

не у нас тут автоматизированная линия вплоть до сварки =) дальше уже да хД

А в чем проблема, дело компьютера обрабатывать данные, так пусть молотит. Если проиндексировать таблицу, еще быстрее будет работать.

проблема как раз в том что машина не может обработать такое количество вариантов в принципе. сервак с 2 головами Xeon'ы 16 гигов оперативы,рейд 10 ssd.

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

Да.. есть некоторые ограничения не менее 500мм и не более хлыста.

(35) я в похожей ситуации (не хватало скорости 1С для перебора вариантов в задаче коммивояжера) - написал ВК и насладился быстродействием.

(34) тогда не все потеряно, но мне кажется что это надо не в 1С делать а выносить во внешнюю компоненту.. типа http://www.astrapro.ru/astranest.asp

http://tehtran.com/nestf.html

и курить именно на  тему сопряжения стороннего отработанного и обкатанного ПО с 1Сом..

+(38) потому что вот такое: http://www.tehtran.com/sites/default/files/imagecache/700w/images/avtoobrabotka.png  - 0па треснет на 1С реализовывать..

Вообще, это оптимизационная задача. Соответственно надо искать  нужный мат. метод и реализовывать его в коде. Т.е строится функция A1x1 + A2x2 + A3x3 <= С, где x1, x2, x3 и т.д - это количества, а коэффициентами выступают площади. Ограничивается это площадью бруска. После чего самое сложное, выбрать соответствующий мат. метод поиска решения. Увы, 4 курс универа, где мы это изучали уже давно позади и с выбором я не помогу с ходу. Надо гуглить :(

(0)
дайте полное описание задачи.

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

разве это не задача о рюкзаке???

(42) даже более простая.

(43) в чем тогда проблема загуглить решение задачи о рюкзаке?

(44) загуглено, реализованно методом ветвей и границ. Не дает точный результат за счет невозможности обработки всего объема данных. Макс число вариантов в ветке 30. т е точность от нормального объема в 200 заготовок всего около 15%.

вот сейчас ребята в принципе подкинули идею на вк перенести. быстродействие повысить. но все равно как не крути машина 100% не даст таким образом. макс до 30-40

(43)
нет. более сложная. в задаче о ранце  1 параметр оптимизации - вес.

(46) 2 параметра. вес и стоимость. тут 1 параметр

http://infostart.ru/public/184599/

(48) спасибо. интересная тема. завтра подгоню под свою задачу и посмотрим что получится

Да не, мне кажется, задачу можно решить намного проще... Например так:

//Инициализация исходных данных
    ВывестиСписокЗамен = Ложь;
    
    ДлинаМатериала = 6500;
    
    СписокЗаготовок = Новый СписокЗначений;
    СписокЗаготовок.Добавить(1300);
    СписокЗаготовок.Добавить(1300);
    СписокЗаготовок.Добавить(1200);
    СписокЗаготовок.Добавить(1200);
    СписокЗаготовок.Добавить(2080);
    СписокЗаготовок.Добавить(2080);
    СписокЗаготовок.Добавить(680);
    СписокЗаготовок.Добавить(680);
    СписокЗаготовок.Добавить(1300);
    СписокЗаготовок.Добавить(1300);
    СписокЗаготовок.Добавить(700);
    СписокЗаготовок.Добавить(700);
    
    КоличествоЗаготовок = СписокЗаготовок.Количество();
    
    ВремяНачала = ТекущаяУниверсальнаяДатаВМиллисекундах();
    
    //Составим матрицу раскроя
    МатрицаРаскроя = Новый ТаблицаЗначений;
    МатрицаРаскроя.Колонки.Добавить("ИтогоДлина");
    Для НомерЗаготовки = 1 По КоличествоЗаготовок Цикл
        МатрицаРаскроя.Колонки.Добавить("ДлинаЗаготовки" + НомерЗаготовки);
    КонецЦикла;
    
    Для НомерЗаготовки = 1 По КоличествоЗаготовок Цикл
        ДлинаЗаготовки = СписокЗаготовок[НомерЗаготовки - 1].Значение;
        ЗаготовкаНЕРазмещена = Истина;
        Для Каждого СтрокаМатрицыРаскроя Из МатрицаРаскроя Цикл
            Если ДлинаМатериала - СтрокаМатрицыРаскроя.ИтогоДлина >= ДлинаЗаготовки Тогда
                СтрокаМатрицыРаскроя.ИтогоДлина = СтрокаМатрицыРаскроя.ИтогоДлина + ДлинаЗаготовки;
                СтрокаМатрицыРаскроя["ДлинаЗаготовки" + НомерЗаготовки] = ДлинаЗаготовки;
                ЗаготовкаНЕРазмещена = Ложь;
                Прервать;
            КонецЕсли;
        КонецЦикла;
        Если ЗаготовкаНЕРазмещена Тогда
            СтрокаМатрицыРаскроя = МатрицаРаскроя.Добавить();
            СтрокаМатрицыРаскроя.ИтогоДлина = ДлинаЗаготовки;
            Для Сч = 1 По КоличествоЗаготовок Цикл
                СтрокаМатрицыРаскроя["ДлинаЗаготовки" + Сч] = ?(Сч = НомерЗаготовки, ДлинаЗаготовки, 0);
            КонецЦикла;
        КонецЕсли;
    КонецЦикла;
    
    //Выводим результат
    Сообщить("Вариант тупого перебора (" + Формат((ТекущаяУниверсальнаяДатаВМиллисекундах() - ВремяНачала) / 1000, "ЧДЦ=3; ЧН=") + " сек.)");
    Для Каждого СтрокаМатрицыРаскроя Из МатрицаРаскроя Цикл
        ТекстСообщения = "";
        Для НомерЗаготовки = 1 По КоличествоЗаготовок Цикл
            Если СтрокаМатрицыРаскроя["ДлинаЗаготовки" + НомерЗаготовки] = 0 Тогда
                Продолжить;
            КонецЕсли;
            ТекстСообщения = ТекстСообщения + ?(ПустаяСтрока(ТекстСообщения), "", " + ") + СтрокаМатрицыРаскроя["ДлинаЗаготовки" + НомерЗаготовки];
        КонецЦикла;
        Сообщить(ТекстСообщения + ". Итого " + СтрокаМатрицыРаскроя.ИтогоДлина + ". Остаток " + (ДлинаМатериала - СтрокаМатрицыРаскроя.ИтогоДлина) + ".");
    КонецЦикла;
    
    ВремяНачала = ТекущаяУниверсальнаяДатаВМиллисекундах();
    
    //Составим таблицу замен
    ТаблицаЗамен = Новый ТаблицаЗначений;
    ТаблицаЗамен.Колонки.Добавить("Разница");
    ТаблицаЗамен.Колонки.Добавить("НомерЗаготовки");
    ТаблицаЗамен.Колонки.Добавить("ДлинаЗаготовки");
    ТаблицаЗамен.Колонки.Добавить("НомерЗаготовкиДляЗамены");
    ТаблицаЗамен.Колонки.Добавить("ДлинаЗаготовкиДляЗамены");
    
    Для НомерЗаготовки = 1 По КоличествоЗаготовок Цикл
        Для НомерЗаготовкиДляЗамены = 1 По КоличествоЗаготовок Цикл
            Если НомерЗаготовки = НомерЗаготовкиДляЗамены ИЛИ СписокЗаготовок[НомерЗаготовки - 1].Значение >= СписокЗаготовок[НомерЗаготовкиДляЗамены - 1].Значение Тогда
                Продолжить;
            Иначе
                СтрокаТаблицыЗамен = ТаблицаЗамен.Добавить();
                СтрокаТаблицыЗамен.Разница                    = СписокЗаготовок[НомерЗаготовкиДляЗамены - 1].Значение - СписокЗаготовок[НомерЗаготовки - 1].Значение;
                СтрокаТаблицыЗамен.НомерЗаготовки            = НомерЗаготовки;
                СтрокаТаблицыЗамен.НомерЗаготовкиДляЗамены    = НомерЗаготовкиДляЗамены;
            КонецЕсли;
        КонецЦикла;
    КонецЦикла;
    
    //Производим перестановки заготовок
    Если ВывестиСписокЗамен Тогда
        Сообщить("Производимые замены (номер строки / номер колонки : значение):");
    КонецЕсли;
    Для Каждого СтрокаМатрицыРаскроя Из МатрицаРаскроя Цикл
        Для Каждого СтрокаТаблицыЗамен Из ТаблицаЗамен Цикл
            Если СтрокаМатрицыРаскроя["ДлинаЗаготовки" + СтрокаТаблицыЗамен.НомерЗаготовки] <> 0 И СтрокаТаблицыЗамен.Разница <= ДлинаМатериала - СтрокаМатрицыРаскроя.ИтогоДлина Тогда
                НайденныеСтроки = МатрицаРаскроя.НайтиСтроки(Новый Структура("ДлинаЗаготовки" + СтрокаТаблицыЗамен.НомерЗаготовкиДляЗамены, СтрокаМатрицыРаскроя["ДлинаЗаготовки" + СтрокаТаблицыЗамен.НомерЗаготовки] + СтрокаТаблицыЗамен.Разница));
                Для Каждого НайденнаяСтрока Из НайденныеСтроки Цикл
                    Если МатрицаРаскроя.Индекс(НайденнаяСтрока) <= МатрицаРаскроя.Индекс(СтрокаМатрицыРаскроя) Тогда
                        Продолжить;
                    Иначе
                        Если ВывестиСписокЗамен Тогда
                            Сообщить("" + (МатрицаРаскроя.Индекс(СтрокаМатрицыРаскроя) + 1) + " / " + СтрокаТаблицыЗамен.НомерЗаготовки + " : " + СтрокаМатрицыРаскроя["ДлинаЗаготовки" + СтрокаТаблицыЗамен.НомерЗаготовки] + " -> " + (МатрицаРаскроя.Индекс(НайденнаяСтрока) + 1) + " / " + СтрокаТаблицыЗамен.НомерЗаготовкиДляЗамены + " : " + НайденнаяСтрока["ДлинаЗаготовки" + СтрокаТаблицыЗамен.НомерЗаготовкиДляЗамены]);
                        КонецЕсли;
                        СтрокаМатрицыРаскроя.ИтогоДлина                                                        = СтрокаМатрицыРаскроя.ИтогоДлина + СтрокаТаблицыЗамен.Разница;
                        НайденнаяСтрока.ИтогоДлина                                                            = НайденнаяСтрока.ИтогоДлина - СтрокаТаблицыЗамен.Разница;
                        СтрокаМатрицыРаскроя["ДлинаЗаготовки" + СтрокаТаблицыЗамен.НомерЗаготовкиДляЗамены]    = НайденнаяСтрока["ДлинаЗаготовки" + СтрокаТаблицыЗамен.НомерЗаготовкиДляЗамены];
                        НайденнаяСтрока["ДлинаЗаготовки" + СтрокаТаблицыЗамен.НомерЗаготовки]                = СтрокаМатрицыРаскроя["ДлинаЗаготовки" + СтрокаТаблицыЗамен.НомерЗаготовки];
                        СтрокаМатрицыРаскроя["ДлинаЗаготовки" + СтрокаТаблицыЗамен.НомерЗаготовки]            = 0;
                        НайденнаяСтрока["ДлинаЗаготовки" + СтрокаТаблицыЗамен.НомерЗаготовкиДляЗамены]        = 0;
                        Прервать;
                    КонецЕсли;
                КонецЦикла;
            КонецЕсли;
        КонецЦикла;
    КонецЦикла;
    
    //Выводим результат
    Сообщить("Вариант после замен (" + Формат((ТекущаяУниверсальнаяДатаВМиллисекундах() - ВремяНачала) / 1000, "ЧДЦ=3; ЧН=") + " сек.)");
    Для Каждого СтрокаМатрицыРаскроя Из МатрицаРаскроя Цикл
        ТекстСообщения = "";
        Для НомерЗаготовки = 1 По КоличествоЗаготовок Цикл
            Если СтрокаМатрицыРаскроя["ДлинаЗаготовки" + НомерЗаготовки] = 0 Тогда
                Продолжить;
            КонецЕсли;
            ТекстСообщения = ТекстСообщения + ?(ПустаяСтрока(ТекстСообщения), "", " + ") + СтрокаМатрицыРаскроя["ДлинаЗаготовки" + НомерЗаготовки];
        КонецЦикла;
        Сообщить(ТекстСообщения + ". Итого " + СтрокаМатрицыРаскроя.ИтогоДлина + ". Остаток " + (ДлинаМатериала - СтрокаМатрицыРаскроя.ИтогоДлина) + ".");
    КонецЦикла;

(51) Результат:
Вариант тупого перебора (0,000 сек.)
1 300 + 1 300 + 1 200 + 1 200 + 680 + 680. Итого 6 360. Остаток 140.
2 080 + 2 080 + 1 300 + 700. Итого 6 160. Остаток 340.
1 300 + 700. Итого 2 000. Остаток 4 500.
Вариант после замен (0,016 сек.)
1 300 + 1 300 + 1 200 + 1 300 + 700 + 700. Итого 6 500. Остаток 0.
2 080 + 2 080 + 680 + 1 300. Итого 6 140. Остаток 360.
1 200 + 680. Итого 1 880. Остаток 4 620.

+(21) Кстати, в (17) ещё ошибка: потерялась одна 680 и лишняя 1200

(51) Главное тут идея. Реализация добавлена для наглядности. Можно, конечно, и не один проход замен сделать, а несколько (добавить цикл и условие по желанию).

(52) Ах да, тест производился на файловой базе.
Платформа 8.2.19.90.
ОС Win7 x86.
CPU Intel Core2Quad Q8200.
RAM 2,0 GB
Винт обычный, 7200 RPM. RAID отсутствует.

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

Симплекс метод.

Метод последовательного спуска гляньте.

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

(59) Много воды утекло. Теперь ещё штук 10 методов найти можно))

(56) ну у нас как бы начальство тоже устраивает текущий. А меня нет =D. да и хочется разобраться каким алгоритмом можно делать оптимизацию на большое количество заготовок в наиболее короткие сроки. Думаю подобная задача не последний раз.

(61) Да тут очень от размера партии зависит, и от размеров самих изделий. При нормальном раскладе, получается порядка 2% отход, на партии 20 изделий. Но если много одинаковых изделий "плохих" размеров, отход может вырасти и до 4-5% и никакой оптимизацией не исправишь

(61) Ты (51) смотрел?

(0) задача оптимального раскроя, в 1с не видел решений, если решишь можешь заработать много денег
а вообще почитай литературку по линейному программированию, может охота отпадет

(61) Тебе уже сказали, какими математическими инструментами это решается. Реализовать модифицированный симплекс метод на 1С не проблема.

Забыл одну важную характеристику, при распиле необходимо учитывать длину реза и торцовку,

(65) реализовать -не проблема,
проблема в медленно действии байт машины 1с8.

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