Добрый день. Интересуют алгоритм обхода вершин в 1С. Есть ли какие-то интересные статьи на этот счет?
Как пример - есть некий массив. Допустим это массив с номерами строк в документе. Необходимо этот массив обойти всеми путями, чтобы получит требуемый путь/цепь.
Если кому-то более интересно, то задача такая: Есть некая сумма, необходимо эту сумму собрать из нескольких сумм в строках документа. Причем варианты могут быть любыми. Например сумма 100 рублей собирается из строк документа 3, 9, 18

Сколько строк?

(1) +1 сколько строк и с какой точностью подбор

(1) Количество вершин неизвестно. Т.е. вершина-точка выхода может быть любой. Условие на выход, что разница между изначальной суммой и суммой собранной в обходе равно нулю. Т.е. может быть 1, а может и число строк в документе.

(0)http://yaforyou.ru/?q=Задача%20о%20рюкзаке

(4) ну тут ещё думать придется.

(3) 1с для такого не рассчитана. Должны же быть сторонние сервисы?

(4)+ Формально, нужно найти решение уравнения: СУММА(Аi*Xi) = 100, Xi = 0 или 1.
Можете сделать перебор этих 2^N значений. Например, рекурсивно.
Или погуглить насчет рюкзака.

(0) на нимфостарте смотри статьи Ильдаровича

Там есть и про построениеипроизвольного графа и про обход разными методами

(0) если точность не важна, например, при задании суммы =100 нашли 125, то задачу можно вообще рандомом искать.

Ну или устанавливать допустимую погрешность в вычислении.

(0) Так что найти надо? Все последовательности, сумма нарастающим итогом которых равна допустим 100.
Если нет отрицательных чисел, то не учитывать строки где сумма больше 100.
Сгенерировать все последовательности. Посчитать нарастающий итог. Если где-то получается 100, то такая последовательность подходит.
Свернуть одинаковые последовательности - ("начало" у последовательности одинаковая, а "хвост" разный).

Если количество строк изначально ограничено каким-то числом, то можно на SQL.
В 1С есть SQL запросы.

Нашел вычисление пути/цепи запросом с использованием кросс джион. Может кому будет интересно.
В функцию передаются 2 одинаковых массива. Массивы содержат только числа. В прикладной задаче это номера строк.

&НаСервереБезКонтекста
Функция ПолучитьВсеВарианты(МассивСвободныеВершины, МассивЭталон)
    
    ТекстШаблон = "ВЫБРАТЬ ";
    
    Для ИндексМассива = 0 По МассивСвободныеВершины.Количество() - 1 Цикл
        
        Если ИндексМассива = 0 Тогда
            ТекстШаблон = ТекстШаблон + Формат(МассивСвободныеВершины[ИндексМассива], "ЧГ=");
        Иначе
            ТекстШаблон = ТекстШаблон + " ВЫБРАТЬ "+ Формат(МассивСвободныеВершины[ИндексМассива], "ЧГ=");
        КонецЕсли;
        
        Если ИндексМассива = 0 Тогда
            ТекстШаблон = ТекстШаблон + Символы.ПС +" КАК Символ ПОМЕСТИТЬ ТаблицаВершин ";
        КонецЕсли;
        
        Если ИндексМассива <> МассивСвободныеВершины.Количество() - 1 Тогда
            ТекстШаблон = ТекстШаблон + Символы.ПС + " ОБЪЕДИНИТЬ ВСЕ ";
        Иначе
            ТекстШаблон = ТекстШаблон + Символы.ПС + " ; ";
        КонецЕсли;
        
    КонецЦикла;
    
    ТекстШаблон = ТекстШаблон + " ВЫБРАТЬ * ИЗ ";
    
    Для ИндексМассива = 0 По МассивСвободныеВершины.Количество() - 1 Цикл
        
        Если ИндексМассива <> МассивСвободныеВершины.Количество() - 1 Тогда
            ТекстШаблон = ТекстШаблон + " ТаблицаВершин КАК ТаблицаВершин" +Формат(МассивСвободныеВершины[ИндексМассива], "ЧГ=")+ ", ";
        Иначе
            ТекстШаблон = ТекстШаблон + " ТаблицаВершин КАК ТаблицаВершин" +Формат(МассивСвободныеВершины[ИндексМассива], "ЧГ=")+ " ";
        КонецЕсли;
        
    КонецЦикла;
    
    ТекстШаблон = ТекстШаблон + Символы.ПС + "ГДЕ ";
    
    Для ИндексМассива = 0 По МассивСвободныеВершины.Количество() - 1 Цикл
        
        ТекстШаблон = ТекстШаблон + " НЕ ТаблицаВершин" +Формат(МассивСвободныеВершины[ИндексМассива], "ЧГ=")+ ".Символ В ( ";
        Для ИндексЭталон = 0 По МассивЭталон.Количество() - 1 Цикл
            
            Если ИндексЭталон = МассивЭталон.Количество() - 1 И ИндексМассива = МассивСвободныеВершины.Количество() - 1 Тогда
                ТекстШаблон = Лев(ТекстШаблон, СтрДлина(ТекстШаблон) - 2) + ") ";
                Продолжить;
            ИначеЕсли ИндексЭталон = ИндексМассива Тогда
                Продолжить;
            КонецЕсли;
            
            Если ИндексЭталон <> МассивЭталон.Количество() - 1 Тогда
                ТекстШаблон = ТекстШаблон + " ТаблицаВершин" +Формат(МассивЭталон[ИндексЭталон], "ЧГ=")+ ".Символ, ";
            Иначе
                ТекстШаблон = ТекстШаблон + " ТаблицаВершин" +Формат(МассивЭталон[ИндексЭталон], "ЧГ=")+ ".Символ) ";
            КонецЕсли;
            
        КонецЦикла;
        
        Если ИндексМассива <> МассивСвободныеВершины.Количество() - 1 Тогда
            ТекстШаблон = ТекстШаблон + " И ";
        КонецЕсли;
        
    КонецЦикла;
    
    ЗапросПути = Новый Запрос;
    ЗапросПути.Текст = ТекстШаблон;
    
    АутКам = ЗапросПути.Выполнить().Выгрузить();

    Возврат АутКам;
    
КонецФункции

Функция возвращает таблицу значений с всеми возможными вариантами путей/цепей для переданного массива цифр.

(13) Опять таки, если в массиве будут дубли цифр, то функция не сработает. Я исходил из того что номера вершин графа уникальные цифры.

(8) Спасибо за совет. Глянул, интересно. Почитаю на досуге.

Еще добавлю кому интересно сразу проверить.
Для чисел 9, 10, 11, 12. Получается такой текст запроса:

ВЫБРАТЬ 9
КАК Символ ПОМЕСТИТЬ ТаблицаВершин
ОБЪЕДИНИТЬ ВСЕ  ВЫБРАТЬ 10
ОБЪЕДИНИТЬ ВСЕ  ВЫБРАТЬ 11
ОБЪЕДИНИТЬ ВСЕ  ВЫБРАТЬ 12
;  ВЫБРАТЬ * ИЗ  ТаблицаВершин КАК ТаблицаВершин9,  ТаблицаВершин КАК ТаблицаВершин10,  ТаблицаВершин КАК ТаблицаВершин11,  ТаблицаВершин КАК ТаблицаВершин12
ГДЕ  НЕ ТаблицаВершин9.Символ В (  ТаблицаВершин10.Символ,  ТаблицаВершин11.Символ,  ТаблицаВершин12.Символ)  И  НЕ ТаблицаВершин10.Символ В (  ТаблицаВершин9.Символ,  ТаблицаВершин11.Символ,  ТаблицаВершин12.Символ)  И  НЕ ТаблицаВершин11.Символ В (  ТаблицаВершин9.Символ,  ТаблицаВершин10.Символ,  ТаблицаВершин12.Символ)  И  НЕ ТаблицаВершин12.Символ В (  ТаблицаВершин9.Символ,  ТаблицаВершин10.Символ,  ТаблицаВершин11.Символ)

(11) на пункте сгенерировать все последовательности все закончится.

(17)
20+30+50=100
50+30+20=100

Это две последовательности или одна?

(18) неизвестно. Это веса или номера? Номера без повторений. А веса все одинаковые могут быть

(19) Что значит не известно? У тебя три вершины с весом 20, 30 и 50.
А=20; Б=30; С=50

Последовательности АБС, АСБ, БАС, БСА, САБ, СБА.
Это всё разные последовательности или одна?

(20) одна.

(21) Тогда проще. Это количество сочетаний, независимо от порядка.

(22) Нужны не последовательности (порядок не важен), а подмножества, которых всего 2^N. Число подмножеств, дающих нужную сумму = числу решений уравнения в (7).
Число сочетаний из N по сколько?

(6) да ладно... я вон считал массивы из сотни тысяч строк....

(16) можешь упереться в количество таблиц...

(0) есть множество алгоритмов для решения задачи, начиная от пузырька и заканчивая делением (например https://ru.wikipedia.org/wiki/Разделяй_и_властвуй_(информатика) )

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

(25) так там и не надо все перебирать.

я делал 3д триангуляцию для матриц 1000*1000*1000 точек, да это не быстро, но вполне подъемно, главное не пытаться это сделать в лоб...

(25) А чего там считать для 30 чисел (n!)/((n-k)!*k!):

(30!)/((30-1)!*1!) = 30!/29! = (30*29!)/29! = 30
+
(30!)/((30-2)!*2!) = (30*29*28!)/(28!*2!) = (30*29)/2 = 435
+
4060
+
...
+
30
+
(30!)/((30-30)!*30!) = (30!)/(0!*30!) = 30!/30! = 1

(25) Там самое большое количество вариантов получается при 15 из 30 = 155117520

https://indorsoft.ru/books/2002/SkvortsovAV-2002-01.Book(Trn).pdf

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

(25) Можете предложить алгоритм, который в общем случае не сведется к полному (почти) перебору? Рюкзак и в теоретическом и в практическом отношении изъезжен.
(27) Вы про полное число вариантов? Так оно известно - 2^N. Для Вашего примера есть известное простое тождество СУММА(C(n,k))=2^N.

(31) Пример для 30. Это не так много.
(30) "Казалось бы, причем тут тут графы" - что бы никто не догадался.

(29) Из книги по Вашей ссылке:
"В [37,39] обосновано, что задача построения такой триангуляции, видимо, является NP-полной. Поэтому для большинства реальных задач существующие алгоритмы построения оптимальной триангуляции неприемлемы ввиду слишком высокой трудоёмкости."
Не знаю, является ли задача оптимальной триангуляции NP-полной (странно, что автор написал "видимо"), но место рюкзака в классификации переборных задач известно.
Практически рюкзак решается быстро, но можно придумать пример, когда решение сведется к "полному" перебору.
ТС, собственно, хотел код для перебора. Ему намекнули, что удобно сделать рекурсивно.

(32) 2^30 примерно 10^9.

2^3 = 8
А, Б, С, АБ, АС, БС, АБС = 7

Варианта когда 0 строк нет. Поэтому не 2^N. Чууууууть меньше. :-)

(35) Хотите сказать, что 2^N-1? (выбрасываем пустое подмножество. Ах, оно бедняжка).

(33) А как вы представляете рекурсивное решение на 1С? Интересно услышать ваше мнение.

Я видел такой вариант. Иметь массив вершин и в определенном алгоритме его перестраивать до тех пор пока не будет найдено решение.

(38) Это один вариант, а не все.

(37) Какое может быть мнение: пишешь процедуру (функцию) с рекурсивным вызовом. Классический пример - вычисление факториала:
Функция Факториал(N)
  Если N = 1 Тогда Возврат 1 Иначе Возврат N*Факториал(N-1) КонецЕсли;
КонецФункции

(38) Если могут быть отрицательные числа в вершинах, то всё равно перебирать придется все варианты, на сколько я понимаю.

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

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

(41) Все числа можно сделать положительными, прибавив к каждому одно и то же достаточно большое число. Задача не изменится.
(0) Попробуйте сначала жадный алгоритм:
- упорядочить числа по убыванию;
- в цикле: если накопленная сумма меньше нужной - добавляете к этой сумме текущее число, иначе продолжить цикл.

(43) Распараллеливание фоновыми на сервере где?

Задачу сбора определенной суммы и определенного количества из массива сумм писал на Си.
Но уже при кодичестве 8 задача уходит в очень долгий перебор вариантов.

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

(43) "Все числа можно сделать положительными, прибавив к каждому одно и то же достаточно большое число." - у вас вычитание поменяется на сложение.
Т.е. прибавив отрицательное, вы даёте "зазор" для большего следующего положительного или большего количества положительных чисел.
Если же вы ко всем числам прибавите какое-то большое положительное число, то вы меняете направление. Прибавляя каждый раз число - вы будите прибавлять каждый раз и ваше заведомо большое число. Заведомо большое число умноженное на количество раз. Результат будет другим.

100 можно получить складывая два числа и три числа и пять чисел. А если вы прибавили ко всем заведомо большое число, то как какому числу надо идти к 100 + 2*(ваше число) или 100 + 3*(ваше число) или 100 + 5*(ваше число).

Если мы ранее шли к известному числу 100, то тут получается от количества слагаемых зависит к какому числу надо идти.

страдал похожей херней (попроще) без всякой математики ;-)
https://infostart.ru/public/14526/

(46), (47) Что я Вас не понял. Попробую формально объяснить.
Есть задача: найти решение уравнения СУММА(Ai*Xi)=B и некоторые Ai<0. Рассмотрим задачу СУММА((Ai+C)*Xi)=B+N*C. Все решения 2-ой задачи являются решениями 1-ой и наоборот.

(49) Кажется, поторопился.

(50)+ Можно выкрутиться, но "некрасиво": решить N задач СУММА((Ai+C)*Xi)=B+к*C (к = 1,2,...,N) и выбрать ту, где к = числу переменных равных 1.

Все зависит от того,ограниченное ли количество Ai.
Если неограниченное,то можно набрать сочетаний положительное+отрицательное,которое больше ноля и решить задачу для них.
Если же количество ограничено,то положительные сочетания будут зависимыми.

Случайным методом - через 4 массива.
Два массива - это сумма.
Первый положительные,второй - отрицательные.
Два других массива - это то,что не вошло в сумму.
Сначала,заполнены два последних.
Если сумма меньше,чем надо,то мы должны добавить значение - для этого,случайно выбираем число из двух иассивов - если выбрали отрицательное,то добираем из положительного массива случайные числа,чтобы итог был положительный.
Если сумма больше,то точно также выкидываем из двух первых массивов,и если попался второй,то добавляем к нему из первого.
И гоняем алгоритм,пока не получим нужную сумму.

Можно использовать всего два массива,просто сдвигая границу разделения и переставляч на нее числа.

(0) если бы требовалось найти сумму по условию не больше, то это было бы очень похоже на какую-нибудь оптимизацию остатка. А если же нужно найти сумму точно равную, то это скорей всего расчет бухгалтерии от обратного.

(0) выбрось графы, делай как можно проще, стандартными возможностяит 1с. 1сники как правило не умеют в декомпозицию, инкапсуляцию и вот это всё. Твоим последователям придётся долго и мучительно разбираться, что за наркоманию ты там нагородил

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

(0) Лучше всего написать за 1-2 часа на пайтоне сервис. Опубликовать его и использовать для своих задач. На пайтоне библиотек море.

(8) та не одна статья по этой теме... и вообще мозги размять норм задачка

(58) Прошу помочь: пробовал на инфостарте поискать Ильдарович - выдал 2 статьи других авторов. Как правильно искать на инфостарте? Или киньте ссылку на одну из статей.

(0) задача о рюкзаке.

(59) ildarovich нужно искать. Вылезет кучка статей, где будут его упоминания и ссылка на профиль, заходите в профиль - получаете список публикаций.

(59) ну так... навскидку...
https://infostart.ru/1c/articles/158512/
https://infostart.ru/1c/articles/160707/
https://infostart.ru/1c/articles/1105799/
https://infostart.ru/public/271270/
https://infostart.ru/1c/articles/163662/

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

Спасибо, почитаю.

(62) Оказывается, я их уже видел. Это все на тему, как запросом (обычно генерируемым динамически) решать "классические простые" задачи теории графов.
Кажется у него же (может путаю) было и про метод наименьших квадратов запросом.
Думаю, что это интересно, правда, не уверен, что так следует поступать: перекладывать на скуль решение математических задач. К тема ТС это отношения не имеет.
В любом случае, спасибо.