Как реализовать определение доступных значений атрибутов сущностей в фильтре, в зависимости от уже выбранных значений?
Есть массив сущностей одного вида:
Entity
-attr1
-attr2
-...
-attrN
Каждый атрибут может иметь от 0 до n значений.
Пример:
Футболка 1:
- Цвет: синий
- Принт: null
Футболка 2:
- Цвет: синий, желтый
- Принт: на спине
Футболка 3:
- Цвет: красный
- Принт: на груди
Есть фильтр со всеми доступными значениями:
Цвет:
- синий
- желтый
- красный
Принт:
- на груди
- на спине
Требуется: при изменении одного из параметров фильтра убрать недостижимые варианты значений фильтра. Пример: Выбрали "Цвет: красный", фильтр должен изменить свои доступные значения на:
Цвет:
- синий (выводится, так как при изменении цвета - вывод не будет нулевым)
- желтый (выводится, так как при изменении цвета - вывод не будет нулевым)
- красный (выбран)
Принт:
- на груди
- на спине (значение исчезло, так как таких свойств у оставшегося товара нет)
Буду благодарен за любые подсказки, направления. Сам вижу 1 вариант: построить автомат, в который занести перестановки доступных атрибутов товаров. (+) - слово входит в автомат. Пример слов автомата для "футболка 2":
синий (+)
желтый (+)
на спине(+)
синий, на спине(+)
на спине, синий (+)
желтый, на спине(+)
на спине, желтый (+)
Тогда для проверки доступности атрибута - в автомат будет достаточно подать слово из выбранных значений фильтра, с заменой проверяемого значения атрибута в нем. В данном варианте - смущает сложность построения автомата, так как для получения всех перестановок атрибутов товара, понадобится до n! итераций, что показывает большую сложность алгоритма.
Ответы (1 шт):
А нельзя это сделать в лоб?
Проходим по всем атрибутам, для каждого:
- отфильтровываем список сущностей по остальным атрибутам, указанным в фильтре;
- собираем все возможные значения атрибута из отфильтрованного списка.
Например, для атрибута «принт»:
- фильтруем по оставшимся атрибутам (цвет=красный) — остается одна сущность №3;
- собираем у оставшихся сущностей значение «принт» — «на груди».
Если список хранится в памяти, то это все выполнится за O(M*N), где M — количество атрибутов, а N — количество сущностей. Если в БД, то при желании можно все доступные значения собрать одним громоздким запросом. Возможно, это можно сделать эффективнее, но этот вариант первым пришел в голову.