Задача о системе скидок в магазине

[Фома]

В магазине существует некоторое количество процентных скидок на товар. К каждому товару возможно применение нескольких скидок одновременно. Две конкретные скидки взаимодействуют между собой одним из двух способов: либо как произведение, либо как MAX из двух (т.е. одна скидка исключает другую). Попарное взаимодействие скидок задано заранее. Вопрос: как проверить на противоречивость заданную систему взаимодействия скидок? Т.е. независимость результата от порядка применеия скидок. Хотелось бы иметь что-либо лучше полного перебора.
Очень нужно для реальной системы.

[Фома]

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

[er]

Задача до конца не формализованна. Нет корректной постановки.

Одна из главных проблем написания ПО под заказ, люди сами не знают, что хотят и что делают. Формализовать задачу - 95% работы. По большей части люди хотят чтоб все было хорошо. Мир во всем мире, электричество в квартирах и т.п.

[bot]

Лучше сказать - совсем не формализована. Поясню предыдущее сообщение для Фомы.
Пусть на один и тот же товар у покупателя есть несколько ДК (дисконтных карт) из фиксированного множества всех возможных ДК: $\{d_1, d_2, ... , d_n \}$. В правилах сказано о применимости только двух любых ДК.
Это задаётся матрицей, можно даже предположить несимметричной - одно дело если покупатель достал из кармана сначала одну карту, а потом другую, то это не обязательно даст ему ту же скидку, если он вытащит их в другом порядке.
Какие числа будут стоять в этой матрице, произведения, максимумы, минимумы, или что-то иное - наплевать. Скидку считаем, заглянув матрицу и будет покупателю щастье.
А теперь пусть пришёл покупатель с тремя ДК. Как считать скидку должно быть оговорено заранее. О какой противоречивости речь, если о способе подсчёта скидки в этом случае ничего не сказано? К примеру, если в этом случае предоставлять покупателю самому выбрать из трёх ДК две, то приходим к двумерному случаю и никаких проблем. Однако тут сказано про порядок применения скидок? Это типа коммутативности, что ли, то есть допустима (или обязательна) ли перестановка ДК, как написано выше? А ведь ещё и ассоциативность есть: если покупатель достал две ДК: a и b, а потом порылся в кармане и достал ещё c, а другой покупатель сначала достал a, потом, подумавши, ещё две, одну за другой b и c, кто же кроме продавца должен установить правило примения скидки? Тут уже и трёхмерной матрицей не обойдёшься, если этим покупателям разные скидки будут.

Чуть подумавши, предложу, что можно устроить.
Рассмотрим свободный группоид над алфавитом $\{d_1, d_2, ... , d_n \}$ - то есть множество всех слов в этом алфавите, неассоциативных в общем случае, то есть корректная расстановка скобок в слове обязательна. Задаём определяющие соотношения (иначе говоря факторизуем его по некоторой конгруенции) так, чтобы фактор получился конечным (впрочем это и необязательно). В каждом смежном классе по этой конгруенции выбираем представителя, не имеющего в своей записи повторений букв, назовём их правильными. На множестве этих правильных представителей задаём числовую функцию f, принимающую значения на отрезке [0,1]. Это будет коээффициент (а не скидка, так как произведение скидок противоестественно - чем больше ДК предъявишь, тем меньшую скидку получишь), на который множится цена товара. В роли продавца мне выступать не приходилось, а как покупатель я буду в восторге от тех r, для которых f(r)=0.
Непротиворечивость тогда будет означать, что функция f имеет одно и то же значение на всех правильных представителях, принадлежащих одному и тому же классу смежности.
И так на каждый товар - свой группоид, это не исключат возможности, что он один все или на группу товаров или на определённые дни (распродажи). Случай, когда группоид на данный товар вырождается в одноэлементный тоже не исключается - на этот товар постоянная скидка независимо от набора имеющихся у покупателя ДК. Можно группоид считать с единицей - для этого допускаем возможность пустого набора ДК.
С определяющими соотношениями работать можно, наличие ассоциативности и/или коммутативности (наличие которых всё же естественно предполагать) значительно упростит дело. Кроме того эту уже коммутативную полугруппу естественно считать идемпотентной, то есть среди определяющих соотношений будут все $d_id_i=d_i$. В этом случае даже и без других определяющих соотношений полугруппа будет конечной.
Уф-ф-ф ... , вытираю пот со лба.

[er]

Скидка характерезуется числом, на которое умножается цена товара. Например, 5% процентная скидка - умножение цены на 0.95. Тогда умножение скидок - нормальная ситуация.

Так из исходного текста непонятно, что о ДК речь. Я подумал, речь про внутримагазинные скидки. Например, сезонные скидки, по случаю памятных дат. Для комплектов товаров (набор нескольких товаров) тоже часто устанавливают скидку, цена комплекта считается по формуле, скида*(сумму цен в комплекте).

Ну, тут с терминалогией запутаешься..

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

При некотором алгоритме "перемножения" нескольких скидок, задача имеет смысл и сводится к:
есть конечный ориентированный граф, надо выяснить есть ли в нем циклы.

Вроде стандартная задача. Для небольших множеств (а скидок не милион), легко считается перебором.

Какая формализация. Пусть $A$ множество скидок, на этом множестве введено бинарное отношение $\to$, ($a_1\to a_2$ означает, что $a_1$ анулирует $a_2$). Аксиомы введем:
1) не бывает $a\to a$
2) если $a_1\to a_2$, то неверно что $a_2\to a_1$

Теперь, когда есть отношение, пробуем из множества скидок \{a_1,a_2,a_3,\cdots,a_n\} выбрать подмножество, по которому будем считать результирующию скидку.
1) Если в \{a_1,a_2,a_3,\cdots,a_n\} нет анулирующих пар, то оно само годится.
2) Если есть, то анулируюшию пару a_i\to a_j заменяем на a_i и дальше по индукции дальше пытаемся сократить наше множество.

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

Интересны хорошие $\to$, для которых не важна схема сокращений, в процессе ужимания множества скидок.

Тут это $\to$ задает граф, $\to$ хорошая, если граф без циклов. Искать циклы не сложно..

[er]

Вот еще, еще должно выполятся
4) из $a\to b\to c$ вытекает $a\to c$.

Тут достаточно рассмотреть множество $\{a, b, c\}$

То есть отношение $\to$ является отношением частичного порядка.

Вот и все, пожалуй.