Недавно на Тостере прозвучал вопрос, который не на шутку меня задел. Корнями он уходит в задачу, которую я приведу здесь в немного другой интерпретации:

Сдали как-то программисты проект в срок и получили премии. На радостях, прямо в ПН скинулись и на все деньги купили пива. В тот же день всё выпили, а во ВТ решили продолжить, но денег больше не осталось. Тогда они сдали бутылки, добавили вчерашнюю сдачу и снова затарились на все, как и вчера. То же проделали в СР и ЧТ. А в ПТ денег оказалось ровно на одну бутылку. Задумались — вспомнили цену одной бутылки, почём у них принимали тару (цены были без копеек), а сколько было денег изначально, никто назвать не смог. Проект был масштабный, премии большие — так что перебором не стоит. Каким же был минимальный бюджет в ПН, чтобы события сложились именно таким образом?

Рассуждая над ней следующим образом


я пришёл к уравнению, которое в абстрактном виде выгядит так (1):

$$

Пытаясь найти подход без перебора к решению такого рода уравнений я потратил не один час, но в итоге нашёл поистине чудесное решение, но поля книги слишком узки ;)

Без иллюзий на счёт первенства в этом вопросе, хочу лишь поделиться удовольствием, полученным в процессе. Если кто знает альтернативный метод или название этого, просветите меня; подобных мне призываю к обсуждению, а нетерпеливых – приглашаю под кат.

Сразу оговорюсь, эта статья тематически похожа на опубликованную около года назад автором SemenovVV «Нерекурсивный алгоритм генерации перестановок», но подход тут, на мой взгляд, принципиально иной.

Я столкнулся с необходимостью составления списка всех перестановок из n элементов. Для n = 4 или даже 5, задача решается вручную в считанные минуты, но для 6! = 720 и выше исписывать страницы мне уже было лень – нужна была автоматизация. Я был уверен, что этот «велосипед» уже изобретён многократно и в различных вариациях, но было интересно разобраться самостоятельно – поэтому, намеренно не заглядывая в профильную литературу, я засел за создание алгоритма.