Комментарии 18
Непонятна постановка задачи – а следовательно, и нужность/ненужность алгоритма для её решения.
Reverse engineering: Вы хотите случайно генерировать наборы, в которых не будут встречаться пары соседних по порядку продуктов? Зачем?
ЗЫ: Зато, если попробовать посчитать количество таких наборов – видно, откуда вылезают числа Фибоначчи. А там и сама теорема Цекендорфа вылезает.
Не совсем так, я хочу получить перечень продуктов по оси редкости
Понятно не стало.
Давайте вы понятно сформулируете задачу, а потом вместе придумаем для неё оптимальное решение и посмотрим, пригодится ли п.Ц.
ЗЫ: А реальное применение, не высосанное из пальца (не этого представления, но чего-то близкого) – EFM-кодирование при записи на CD.
А что вас собственно так не устраивает.
Мне не кажется что оно из пальца, решение достаточно прозрачное что бы его понять, писать было не очень сложно, читать занимательно.
Может быть применение алгоритма не совсем тривиальное, только это скорее не минус, а плюс :-)
Да и задачу я уже формулировал — заформулировал.
Но лично для вас, буду рад ещё раз это сделать:
У меня есть набор продуктов. Так же есть холодильник — условный класс для хранения продуктов. Холодильник наполняется продуктами по принципу, как можно больше вещей дешевых (которые имеют меньшую ценность), и что бы при этом оставался шанс на вещь подороже.
Если ранжировать продукты с помощью чисел Фибоначчи, то мы получим, что курица, как не крути, будет иметь ключ выше чем лаваш. А используя этот алгоритм мы почти всегда имеем предмет с весом 1, и с весом равным верхнему порогу числа rarity (см. статью) — а значит и дорогие, и недорогие продукты присутствуют, причём недорогих по идее должно быть больше.
Вообще непонятно, причём тут алгоритм.
И ещё раз: напишите постановку нормально. Так, чтобы вы могли дать задачу стороннему человеку.
Вот вы пишете – "как можно больше вещей дешёвых и чтобы оставался шанс на вещь подороже". Элементарно: положить в холодильник всё. Задача решена.
Если вы хотите получить определённое распределение вероятностей продуктов – напишите, какое. Если хотите наложить на список ограничения – опять же, скажите, какие. Я пока вижу "не предлагать одновременно лаваш и огурец, огурец и салат и т.п." – и то не из постановки, а из кода.
Пока я вижу, что вы пренебрегли постановкой задачи, потом натянули на неё алгоритм по принципу "надо его применить" – и решили непонятно какую задачу излишне усложнённым кодом.
И совсем не приятно если вы это делаете с целью показать: «что у меня не так — а у вас так»
По поводу распеределения — оно должно быть случайным, да таким что бы чаще попадались продукты Low cost, к примеру идея холодильника для конкретной задачи заключается в получении продуктов для закручивании шаурмы.
Бот нам отвечает что мы можем взять 1 продукт
В шаурме такой ингридиент как курица — очень важен, но мне бы хотелось что бы он выпадал не так часто как лаваш и огурец (и я не говорю что они менее важны, просто их проще получить и стоят они дешевле)
Эти продукты имеют ценность, как себестоимость так и ценность для конечного пользователя.
А те продукты которые "дорогие" в будущем можна будет поменять 2 к 1 на интересующий дорогой продукт или подешевле.
Недавняя статья с интересным и простым алгоритмом натолкнула меня на мысль что можно его тут использовать, и всё получилось в точности как я хотел.
Я не хочу сказать что делать нужно только так, а что сделать можно и вот так тоже и получится достаточно обьективный результат который хотя бы осознать можно не опытному разработчику, а потом уже использовать более сложные способы.
Ну, меня устроит любой из двух вариантов – качественная статья или никакой :-)
Я понимаю, что первый труднее, поэтому готов помогать. Но чтобы помогать – надо видеть, в чём.
Пример постановки:
Цена продуктов (массив)
Ценность продуктов для пользователя (массив)
Сумма, которой мы располагаем
Найти оптимальный (максимизирующий суммарную ценность для пользователя) набор продуктов.
Набор продуктов — массив из N элементов,
Редкость продуктов — массив из N элементов, для каждого продукта своя редкость,
Найти набор продуктов с такой редкостью продуктов внутри, которая бы на графике выглядил как парабола.
Набор с заданной вероятностью получения каждого продукта делается совсем просто: по одному случайному числу (равномерно распределённое от 0 до 1) на каждый продукт, если оно меньше требуемой вероятности – добавляем к набору. Тут хоть параболу можно сгенерировать, хоть синусоиду. При этом не будет странного ограничения "нельзя одновременно получить лаваш и огурец".
Найти набор продуктов с такой редкостью продуктов внутри, которая бы на графике выглядил как парабола.
На графике чего, уточните пожалуйста? Что по каким осям отложено? Откуда график линия? У вас же набор элементов — это просто множество редкостей, какие-то числа. Как из них получается порабола?
Это как раз понятная часть: автор взял свой алгоритм генерации и построил для него график — сколько раз каждый из продуктов попадает в набор. Единственное – построил в дурацких координатах, по оси X отложил не номер продукта, а значение соответствующего числа Фибоначчи, да ещё и отрисовал интерполированный (сплайнами или ещё чем) график между ними.
Update так как многие не могли осознать в чём состоит задача, я немного более подробно опишу её.
Пользователь должен в конечнем счете получить шаурму, набор продуктов из холодильника как промежуточный этап этого действия.
Набор продуктов из холодильника должен происходит постепенно, не больше 1 предмета за раз и когда все продукты кончатся, холодильник вновь заполняется.
Заполнять холодильник желательно таким способом, который бы включал как можно больше дешевых продуктов (Low cost) и как можно меньше High cost, но они должны точно быть, и быть должны разные, так как существует процедура обмена 2 дорогих продуктов на 1 любой другой.
А нужно это потому что холодильником будут пользоватса сразу несколько пользователей, соответствено продукты одни на всех, и что бы как-то наградить самого быстрого пользователся — ему дается возможность взять дорогой продукт и в последствии его поменять.
Кроме того курица заслужено дорогой продукт, но по прежднему важный ингридиент, и что бы его получить нужно «постаратся».
Остальные ингриденты, не являются мусором. Иногда пользователю будет попадатся спец-заказ где вместо курицы — говядина, а, к примеру, вместо огурца — яблоко.
Постановка, кажется, всё ещё не очень (очень большой простор для разного понимания) и "не бьётся" с вашим решением, но уже чуть понятнее.
Почему решение не позволяет положить в холодильник одновременно лаваш и огурец?
Почему вообще заполнение холодильника случайное? Разве нет какого-то оптимального заполнения? (вот в теории игр его зачастую нет и приходится вводить случайность – но там это связано с тем, что без этого второй игрок определит нашу стратегию и сыграет против нас)
Почему вообще заполнение холодильника случайное?
Тут случайность присутствует, что бы пользователь (пускай будет игрок), не знал какой набор будет следующим и от этого постоянно заходил что бы проверить следующий набор.
И для меня данное решение вполне оптимально с точки зрения постановки задачи.
Почему решение не позволяет положить в холодильник одновременно лаваш и огурец?
Лаваш и огурец в теории могли бы быть рядом но список продуктов именно такой. В разное время — разные ингриденты.
Цель получения ингридеентов разной "редкости" для пользователя в наборе с предметами "средней руки". Что бы самому активному пользователю доставалось самое ценное, но тем не менее нужно собрать все ингредиенты для успешной шаурмы.
В такой постановке задача решается гораздо проще и понятнее. Разбиваете ваши продукты на дорошие и дешевые. Случайным образом выбираете один из дорогих, потом случайно перемешиваете все дешевые и берете их, пока они помещаются в холодильник.
Очевидно же, что мне это решение не подходит, именно поэтому, я использовал этот алгоритм.
Мне не очевидно. Почему? Вы, наверно, какую-то важную для вас деталь в постановке задачи опустили.
Главное в чём оно лучше — это то, что был использован другой подход, раньше я такого никогда не использовал и мне показалось это достаточно интересным, настолько, что бы поделится этим с как можно большим количеством людей.
Но я рад что существуют люди, которые пробираются в суть проблемы и действительно пытаются найти решение даже лучше :)
Практическое применение алгоритма для представления Цекендорфа