Эта публикация — реализация идей моей статьи
Обработка работает в любой конфигурации. Формируем таблицу задолженностей (построчно. Прикручивать импорт из файла я не стал, о причинах этого — ниже), кнопкой «Создать списки…» преобразуем ее (результат не отображается), затем распечатываем все варианты распределения задолженностей. В примере на скрине получилось два кредитора и три дебитора, что дало 2!*3! = 12 распределений. После (автоматического) удаления дублей(каждый вариант присутствует дважды, в прямом и обратном порядке перечисления дебиторов и кредиторов) вариантов для печати осталось шесть.
При увеличении количества участников количество вариантов растет очень сильно, что делает ситуацию необозримой. Поэтому я и не стал заботиться об обработке длинных таблиц.
06.06.2011 Добавил контроль повтора вариантов (когда результирующие таблицы различаются порядком колонок).
24.06.2011 Вынес текст (рекурсивной) комбинаторной функции «ВсеПерестановки» на скрин
Related Posts
Получение логина и пароля техподдержки 1С из базы
Класс для вывода отчета в Excel
Счет-фактура для УПП
Библиотека классов для создания внешней компоненты 1С на C#- Акт об оказании услуг (со скидками) — внешняя печатная форма для Управление торговлей 11.1.10.86
Прайс-лист с артикулом в отдельной колонке
Вот так ! На всякие козни, «происки и бредни» ответить делом.
При любом последующем исходе :
Знай наших ! Арчибальд — молодца.
Вот еще интересный скрин
(1) А где запросно-восмерное решение?
(3) Спокойно. Моя роль — оппонент.
Работаю на отскоке , вторым номером — исследую и критикую то, что предлагают Машков и Арчибальд.
Своих идей, альтернатив в отличие от тебя не предлагал и не предлагаю.
(4)
😮
(5) Пусть так.
(2)»Интересный скрин», приведенный в (2), не должен существовать.
В том смысле, что, по результатам предыдущих обсуждений, строки (1,2) и (3,4) начальной таблицы задолженностей образуют две области связанности.
Строки (1,2) — по контрагентам (а, б, в).
Строки (3,4) — по контрагентам (г, д, е).
Поэтому задача распадается на две части, и получающиеся таблицы взаимозачетов не должны порождать задолженности между контрагентами из разных областей связности.
Или это тест на внимательность участников обсуждения? 😉
(7) Это не тест на внимательность и не прикол.
В вольной трактовке задачи от Арчибальда и в его выражениях :
Раз все контрагенты согласились на «договор -групповуху», то они должны быть готовы к любому (возможному по Арчибальду) распрежеделению.
Причем может быть выдано несколько равноправных вариантов, а некто должен выбрать один подходящий.
Предстоит грустный анализ с грустным финалом : Что это означает и к каким последствиям приводит в его же обработке ?
Вообщем всю дальнейшую грязную работу готов Вам уступить.
Моё заключение по обсуждению «канвы доказательств» и практической обработки Арчибальда.
1. Твоя постановка задачи — немыслима.
Подход : навалим лицу принимающему решения побольше вариантов , а он пусть разбирается — ошибочен.
2. Твоя обработка НЕ РАБОТОСПОСОБНА.
Ниже приведены два скриншота по п.1 и п.2.
(8), (9) Думаю, такую трактовку нужно подкорректировать, даже если бы вариантов получалось мало и не приходилось снимать процесс диспетчером.
По чисто практическим соображениям:
— Если в результате расчета формируется задолженность контрагента тому контрагенту, с которым у него вообще не было договорных отношений, то прежде чем согласиться на это, они должны заключить друг с другом договор. А это проверки и согласования по всем инстанциям в двух фирмах. И…каков предмет договора? Затруднительно будет сформулировать.
Конечно, в таких простых примерах, как приведены в (2) и (9), можно сказать по-простому — сами виноваты, нечего было такие таблицы на вход давать. И так видно, что они должны быть отдельными. Но в реальных условиях, возможно, это будет сложнее увидеть.
Мне не хочется так уж сильно ругать представленную реализацию.
Всего-то и нужно — добавить в начало процедуру разбиения на области связности.
…
Правда, даже и в одной области связности можно прийти к такому решению (исходные: А должен Б 10, Б должен В 10, В должен Г 10. Результат: А должен Г 10). Если по практическим соображениям, которые я выше изложил, и это решение отбросить, то тогда вообще непонятно, какие решения оставлять. Так что, получается, сначала разбить на области, затем выдать все варианты для каждой области. Может, и родятся критерии отбора/сортировки этих вариантов — но я пока не готов.
(10) Так дело -то в том , что суть и соль «альтернативы» Арчибальда в том , что НЕ НУЖНО разбивать исходный граф на односвязные. И так сойдёт.
Если Арчибальд откажется от этой идеи , то вся его «альтернатива» рухнет — останется идея Машкова.
А тогда какой смысл исправлять и «подкручивать» что-то в обработке Арчибальда , если сама идея заложенная в обработку порочна ?
Всего-то и нужно — добавить в начало процедуру разбиения на области связности.
А мне хочется. И вот почему.
Если даже Арчибальд добавит процедуру деления на односвязные графы (кстати , что и предполагает алгоритм Машкова), то после получения односвязных графов для получения итоговой таблицы алгоритм Машкова гораздо проще,быстрее, изящнее , чем у Арчибальда. Арчибальду и его перенять ? Но тогда где окажется исходная «альтернатива» Арчибальда (см. начало поста)?
(7) Добавим к таблице задолженностей из 2 поста
а б 10
а в 20
г д 20
е д 10
еще три строки
а г 1
г в 1
в а 1
Область стала односвязной, есть цепочки — первоначальные условия выполнены.
(9) Вариантов вля 1-го случая в самом деле 18. Во втором — 7200. При этом, добавив циклическую задолженность, как в моем 12 посте, мы останемся в «корректной по-вашему» области определения условий.
Касательно разницы моего алгоритма и алгоритма Машкова. У Машкова получается какое-нибудь решение. У меня — все решения. Конечно же, я могу после нахождения первого решения прервать цикл — получим решение Машкова. Так что мое решение не альтернативное, а общее.
(14) Ну-ну
15) Ты ничего не понял ?
Ты сам найдешь простенький вариант с тем же количеством строк , который в очередной раз обрушит твою подлатанную обработку.
Пыль улеглась. Можно тихо , спокойно и конструтивно завершить .
Новую тему заводить «стрёмно»
На мой вгляд :
1. Твоя мысль о том , что НЕ нужно вначале разбивать на односвязные — правильная.
Мне никак не удавалось отодрать эту мысль от последующей твоей интерпретации ,т.е. текущей обработки.
Отодрал и всё встало на свои места.
Подход Машкова (предварительного разбиения на односвязные) не продуктивен и мало чего дает.
2. Решение должно быть таким.
————————————————————————————————-
На входе имеем ТаблицаДолга0. Применяем алгоритм Мащкова. Получаем ТаблицаРаспределения0 , например
А Р N1
Б Р N2
В Р N3
————
Р С R1
Р Д R2
Р Е R3
Составляем список Дебиторов( А,Б,В) и выбираем первый элемент А. Все строки в исходной таблице ТаблицаДолгов0 , содержащие Дебитор = А, умножаем на 2.
Получили ТаблицаДолгов1.
Запускаем теперь алгоритм Машкова. Получаем некоторую ТаблицуРаспределения1
Например,
А Р (N1 + N1)
Б Р N2
В Р N3
————
Р С (R1 + d1)
Р Д (R2 + d2)
Р Е R3
Разность двух таблиц равна
ТаблицаА = ТаблицаРаспределния1- ТаблицаРаспределения0
, и есть итоговое распределение для А.
А Р N1
————
Р С d1
Р Д d2
И далее очевидно для Б.. Исходной для следующего цикла будет считаться ТаблицаДолгов1 (с увеличенным вдвое дебетом для предыдуещго элемента А)
———————————————————————————
Во — первых , никакого честного распределения , которое может приводить к удивительным гримасам (резкое увеличение количества связей)
Во — вторых , Доказать не смогу , но по-видимому обеспечивается минимум количества связей.
В отличие от твоего подхода и Машкова — Такой алгоритм годится для очень больших произвольных графов .Например , граф произвольного уровня и произвольной связности с количеством узлов не более 100 000 на среднеофисном компьютере и среднеофисном SQL-сервере должен занять не более 40 мин.
Понятна и слабость алгоритма. Чем больше связность графа тем хуже для быстродействия.
Действительно , если исходная таблица распределения содержит 25000 дебиторов , то алгоритм Машкова будет запущен 25 000 раз.
(вот откуда 40 мин)
(17) Обсуждаемый конструктив! 🙂 Начнем.
1. Моя мысль несколько не такая. Моя мысль: способ разбиения графа на части по признаку «односвязности» подграфов — только один из многих возможных, и останавливаясь на этом единственном способе неоправданно сужает пространство решений. С другой стороны, если тупо перебирать все решения (как в моей обработке), то при увеличении количества дебиторов/кредиторов слишком быстро растет время расчетов (количество вариантов).
Т.о., разбивать граф все-таки нужно. Например, для 4 дебиторов и 6 кредиторов количество вариантов 4!*6!/2 = 8640, а при разбиении на две группы по 2 дебитора и 3 кредитора даст по 6 вариантов в каждой группе, а всего 36 вариантов.
2. ТаблицаРаспределения0 по Машкову отличается от ТаблицыРаспределения0 по Арчибальду тем, что вместо символа «Р» Арчибальд использует символ » » (пробел). Так что исходные данные совпадают. Далее Машков и ты произвольным образом отделяете подтаблицу — одного дебитора с его произвольно выбранным кредитором (кредиторами) и двигаетесь дальше. Я же рассматриваю все варианты выбора первого дебитора и все варианты отнесения его долгов на различных кредиторов. И получается у меня очень много вариантов.
Резюме. Для того, чтобы перебор вариантов занимал обозримое время, надо пользоваться некими дополнительными критериями для дробления множества контрагентов на подмножества и проводить взаимозачеты внутри подмножеств. Вполне достаточным может оказаться (а может и не оказаться) крителий «односвязности». Возможен вариант (внутрихолдингового) разбиения по направлениям бизнеса. По нахождению расчетных счетов в одном банке… Словом, это тема отдельная.
Отличие в подходах очевидно.
Ты настаиваешь на переборе вариантов и ищещь способы по некоему критерию лишь уменьшить их количество
Я же совершенно убежден , что это тупик.
Количество вариантов может быть настолько велико при любом критерии,
что в игре «кошки-мышки» я тебя всегда поймаю. На твой придуманный критерий я всегда придумаю такой начальный граф , который даст огромное количество вариантов.
В таких случаях , лучше надежный предсказуемый вариант с заранее известным количеством итераций (17),
предположительно обеспечивающий минимум количества связей.
Что значит «с заранее известным» ?
Это значит , что запустив один раз алгоритм Машкова.
1. Мы сразу узнаем количество итераций
2. По размеру таблицы достаточно точно можно оценить время выполнения алгоритма.
Т.е. алгоритм при практическом использовании — предсказуем.
Думаю , это очень существенно.
(20) В алгоритме Машкова (вернее, твоем) нет никаких итераций. Это произвольный выбор одного из путей в дереве (точнее, лесу) вариантов. То есть: после того, как появилась ТаблицаРаспределения0, вариант у вас остается только один (см. восьмой скрин во взаимозачете из графина). Вариант — это как раз вариант расположения (нумерации) дебиторов и кредиторов в соответствующих перечнях. Для моей обработки это означает прерывание цикла после нахождения первого варианта.
Вопрос в том, кому интересен безальтернативный выбор варианта.
(21) Под итерацией понимается — процедура построения таблицы распределения для одного дебитора.
Действительно, алгоритм предусматривающий безальтернативный выбор одного аварианта оправдан тогда , когда он обладает каким-то существенным преимуществом.
1. Обеспечивает минимальное количество связей (думаю , что это действительно так).
2. Дает предсказумость по быстродействию.
3. Даёт возможность обрабатывать очень большие произвольные графы. (что немыслимо при твоём подходе или Машкова).
Ты же предлагаешь некую абстрактную альтернативу : а давайте найдем некий критерий , по которому распределение будет — всех устраивающее ( честное). Хм .. я не возражаю против таких поисков.
Вынужден дополнить о безальтернативности.
Никто же не запрещает в (17) менять порядок в спике дебиторов.
И тогда , получим столько вариантов распределения сколько нужно. Только зачем ?
(22) Количество твоих «итераций» , т.е. уменьшений перечня дебиторов/кредиторов на 1, дает формула Д+К-1.
Что в сухом остатке.
1. Формируем список дебиторов и список кредиторов. Это один проход по исходному списку.
2. Сортируем списки дебироров и кредиторов по некоторому принципу. Например, кредиторов по убыванию задолженности, а дебиторов по возрастанию. Или обе по возрастанию. Или обе по региональной принадлежности. Можно никак не сортировать — будет твой алгоритм. Можно тупо сортировать всеми возможными способами — это в моей обработке.
3. Моделируем мой восьмой скрин — сливаем списки дебиторов и кредиторов в одну таблицу.
4. За один проход по этой таблице получаем итоговое решение
Общий объем вычислений существенно зависит от действий на втором шаге. Шаги 3 и 4 имеют объем вычислений пропорциональный количеству вершин, а шаг 1 — количеству дуг. При «нормальном» количестве участников (несколько десятков) время вычислений составит (милли)секунды. А вот второй шаг — поле для оптимизации.
Если я тебя правильно понял , то получается вырождение задачи.
Из таблицы долгов сразу получаем
список только дебиторов
список только кредиторов
И распределяем все долги дебиторов между кредиторами. Точка.
Но тогда исходный граф и анализ его вообще НЕ нужен ? Так ?
Допустим , фирма А имела только один долг (связь) перед фирмой В.
Всего во взаимозачете участвует 1000 фирм.
И возможен вариант, что после проведения взаиморасчета фирма А может иметь долг раздробленный на 500-600 контрагентов.
Если ты допускаешь такой вариант , то конечно анализ графа задолженностей НЕ НУЖЕН. Задача вырождается.
Если такой вариант признать недопустимым , то анализ графа необходим.
Если Мы говорим про алгоритм (17) , то после проведения взаимозачета фирма А будет иметь один долг перед В.
Черт возьми !
Слушай , но тогда получается , что «чисто» метод Машкова приводящий к таблице
А Р N1
Б Р N2
В Р N3
————
Р С R1
Р Д R2
Р Е R3
Как раз и есть вырождение задачи ?
Действительно такую таблицу можно определить за один проход по таблице долгов просто сложив
для каждого контрагента всего дебиторкие и кредиторские задолженности.
Без всяких там графов , подстановок «Р» и т.д.
Боже мой.. Я поглупел.
Машков нам предложил всего лишь тривиальный метод подсчета финансового результата для каждого контрагента в таблице долгов.
Но продолжаем дальше. Вся его метода имеет смысл всего лишь в одном случае , в (17) :
Подстановки с «Р» дают нам возможность узнать на кого конкретно упадет добавленный долг.
(25) Так общее количество получившикся задолженностей все равно ограничено задолженностей все равно ограничено числом Д+К-1.
Нормальный вариант. Количество задолженностей на 1 сократолось, сумма сократилась вдвое…
(27) Ничего не понял. Ты про что ?
(28) Так понятнее? У В был один должник, а стало четверо. Твой пример.
(29) Конечно , Нет.
Смотри
А — Б 1000р
С — Д 1р
Д — К 2р
….
и т.д
1000 строк и нигде не встречается А и Б
….
Тогда долг 1000р. при распределении может распределиться на 500 и более контргаентов,
откуда мы узнаем что этот долг принадлежит только Б ? Если мы не анализируем граф. ?
(29) У меня в (17) никаких вариантов нет. Долг 1000 р. останется за парой А — Б без всяких вариантов.
И это правильно !
У тебя же возможны различные распределения , потому что ты не анализируешь граф !
И у тебя, если А будет в начале списка, а В — в конце, будет то же самое. Граф-то ты тоже не анализируешь.
И на то, что без сортировки они попадут оба в первые строчки, не сошлешься. Если изначально они не в первой строчке исходной таблицы, а в 400-й.
(31) Давай не перепрыгивать. Из (30) следует , что у тебя возможно распределение долга на 500 контргаентов, т.е. резкое увеличение количества связей ? Так или нет ?
Теперь у меня . Что-то я не понял .
Расссатриваем тот же пример.
Неважно где стоит связь А-Б 100 р — после распределения мы увидим только
А- Б 1000р. И никак иначе.
Смотри
А Б 1000
С Д 1
Д к 2
Получаем по Машкову Таблицу0
А Р 1000
С Р 1
Д Р 1
——-
Р К 2
Р Б 1000
теперь умножаем связь А-Б на 2 в исходнйо таблице долгов и получаем по Машкову Таблицу1
А Р 2000
С Р 1
Д Р 1
——-
Р К 2
Р Б 2000
Теперь вычитаем Таблицу0 из Таблицы1
получим
А Р 1000
———
Р Б 1000
Т.е. ни от кого порядка расположения правильность связь А-Б остается в первоначальном виде.
Черт возьми, еще раз. А алгоритм -то у меня в (17) неверный.
И опровергается просто.
Допустим,
В первоначальном списке только кредиторов фирма В отсутствует.
Если мы увеличиваем связи фирма А
А Б 10*2
А В 10*2
вполне может получиться так , что появится новый кредитор В.
Т.е. предполагалось , что увеличение Дебета фирмы вызовет соответсвующее увеличение сумм первоначальных кредиторов.
Но возможна ситуация , что такое увеличение дебета фирмы А парируется возникновением нового кредитора.
А это нас не устраивает.
И получается, что всё гораздо сложнее .
Прием в (17) дает лишь информацию о том какие кредиты изменились и по этому изменению можно судить о том ,
что эти фирмы МОГУТ, но не более того, быть кредиторами фирмы А.
Надо что-то придумать.
Впрочем ,Может быть правильно обнулить все связи и кредитовые и дебетовые для фирмы А.
Вопрос?
Какие документы необходимо представить Налоговым компаниям по данным операциям? ( В бух. учете любая операция документируется ).
Любой учет по 60 и 62 счету ведется в разрезе договоров, банковских счетов и выписок, счетов-фактуры и т.д., а с ними что делать при таком маразме? ( Сливать воду. ) Чтобы все это обосновать академику зарплаты не хватит (займет), а ВАС посадят и надолго.
Народ читайте бух. учет там ВСЕ написано.
Выстрел в (17) оказался ложным. Задача сложнее, как оказалось.
(34) Ох и долго же до тебя доходит 😀
(37) Спасибо за сочувствие, добрый человек.
(35) Ответ!
1. Акт сверки взаиморасчетов (эквивалент таблицы задолженностей). Не двусторонний, а многосторонний.
2. Договор о реструктуризации взаимных задолженностей. Многосторонний.
3. Бухгалтерские справки об отражении условий оного договора в учете.
То, что в конфигурациях 1С отсутствуют соответствующие документы/обработки, к делу не относится. Там и двустороннего акта сверки первые лет 12 не было, а валютного акта до сих пор нет (если, конечно, не считать ).
Что делать с НДС, Который мы пр оплатили при получении аванса? ( 76.АВ )
Как это отразится в Декларации по НДС ( примитивный контроль 62.2 — 76.АВ) ?
Акт сверки — Взаиморасчеты, а не взаимозачёт.
Договора фиксируется по любой сделке.
Бух. справка — не документ, а основания для проведения операции ( Для налоговиков, с нее начинается раскрутка этих схем).
Автор путает понятия ВЗАИМОРАСЧЕТЫ — Это нормально и ВЗАИМОЗАЧЕТ — Это черный Нал. ( Уход от налогов (НДС))
Обратитесь к Гл. Буху, или к налоговикам.
Давай разберемся с постановкой задачи. Кто и как её понимает.
В твоем представлении :
1. получили информацию от фирм , участвующих во взаимозачете
2. слили в одну таблицу с колонками Д-р,К-р,Долг
3. Нашли список только дебеторов и список только кредиторов
4. И пошли распрелять долги ВСЕХ дебеторов среди ВСЕХ кредиторов. (здесь неважно каким образом).
При таком подходе к задаче (распределение ВСЕХ на ВСЕХ) выясняется что фирма,
имеющая одного должника вполне может получить после рапределения 100 должников.
Т.е. не достигается минимум количества связей.
Это происходит, потому что не анализируется граф (таблица долгов).
Лишь только пройдя граф , мы можем определить для каждого дебитора список всех его возможных кредиторов.
И распределение долгов будет тогда не «ВСЕХ на ВСЕХ» , а «всех на своих строго определенных».
Анализируя граф мы получаем более осмысленную картину взаимозачетов. Долги дебеторов распределяются среди «понятных», «знакомых» кредиторов.
Почему это важно ?
Представим себе «какой-то клиринговый» центр, который постоянно проводит взаимозачеты среди своих 10 000 клиентов, и где рассматриваемая задача имеет смысл.
Клиенты регулярно предоставляют информацию о ВСЕХ своих кредиторах и дебиторах, а не только тех , кто является клиентом клирингового центра. При твоей постановке задачи они получат распределение долгов для неклиентов, что неприемлемо. Можно конечно , поставить ограничения . Центр фильтрует из представленной только своих контрагентов , созванивается с клиентами , предупреждает, исправляет и т.д.
Но лучше , перспективнее, надежнее вообще снять какие либо ограничения при расчетах.
Даешь решение графа !
(41)
Достигается. Д+К-1. Всегда.
Другое дело, что, как мы вроде уже выяснили, нужно учитывать некие дополнительные обстоятельства/критерии. Одним из таких критериев может быть, в том числе, взаимное знакомство участников.