Мультимножество в данном случае состоит из нескольких комбинаций пунктов меню, которые вписываются в определенный бюджет. Пункты меню могут повторяться, а перестановки комбинаций считаются одинаковыми, например [a,a,b,c]
и [c,a,b,a]
одинаковые. Такое мультимножество можно реализовать и сохранить с использованием Map<String[],Integer>
с дополнительными методами фильтрации для представления его в виде List<String>
.
Map
подготовка потока карт Stream<Map>
.
Подсчитаем, сколько раз минимальная сумма из карты вписывается в бюджет, это будет количество итераций IntStream
.
Подготовим карту комбинаций: key - String[]
массив пунктов меню, value - Integer
сумма заказа, в копейках.
Получаем поток карт Stream<Map<String[],Integer>>
.
Reduce
сводим поток карт в одну карту.
Последовательно суммируем пары карт в одну карту, добавляя более дешевые пункты меню к более дорогим, т. е. последовательно суммируем записи двух карт Map.Entry
.
Будем использовать отсортированные массивы String[]
и TreeMap
с компаратором Arrays::compare
, чтобы исключить дубликаты, т. е. перестановки комбинаций.
Используем целочисленные суммы в копейках Integer
вместо дробных Double
, чтобы исключить неточности при сложении сумм, например 7.949999999999999
или 7.550000000000001
.
Получаем карту комбинаций Map<String[],Integer>
.
Методы фильтрации и представления результирующей карты в виде List<String>
.
quantity(min,max)
по количеству пунктов меню в заказе.
contains(items)
по присутствию определенных элементов меню.
minAmount(min)
по нижней границе суммы заказа.
get()
строковое представление карты комбинаций.
Try it online!
class MenuCombinations {
// комбинации пунктов меню, которые вписывается в выделенный бюджет
private Map<String[], Integer> combinations = Collections.emptyMap();
/**
* @param menu карта пунктов меню
* @param aBudget выделенный бюджет, double
*/
public MenuCombinations(Map<String, Double> menu, double aBudget) {
// некорректные входящие данные
if (menu == null || menu.size() == 0 || aBudget <= 0) return;
// выделенный бюджет, в копейках
int budget = (int) (aBudget * 100);
// самый дешевый ункт меню, в копейках
int min = menu.values().stream()
.mapToInt(val -> (int) (val * 100)).min().orElse(0);
// некорректные входящие данные
if (min <= 0) return;
// заготовка карты комбинаций
Map<String[], Integer> map = menu.entrySet().stream()
.collect(Collectors.toMap(
// ключ - массив пунктов меню
e -> new String[]{e.getKey()},
// значение - сумма заказа, в копейках
e -> (int) (e.getValue() * 100)));
// карта комбинаций
this.combinations = IntStream.rangeClosed(0, budget / min)
// Stream<Map<String[],Integer>>
.mapToObj(i -> map)
// добавляем более дешевые пункты меню к более дорогим
.reduce((map1, map2) -> map1.entrySet().stream()
.flatMap(entry1 -> {
// сумма выбранных пунктов меню
int sum = entry1.getValue();
// если выделенный бюджет превышен
if (sum > budget) return Stream.empty();
// если выделенный бюджет достигнут
if (sum + min > budget)
return Stream.of(Map.ofEntries(entry1));
// иначе продолжаем добавлять пункты меню
return map2.entrySet().stream()
// пропускаем пункты меню, которые больше
.filter(entry2 -> entry2.getValue() + sum <= budget)
// суммируем записи двух карт, и добавляем предыдущую
.map(entry2 -> Map.of(
// новый ключ - отсортированный массив пунктов меню
Stream.of(entry1, entry2)
.map(Map.Entry::getKey)
.flatMap(Arrays::stream)
.sorted() // для компаратора
.toArray(String[]::new),
// новое значение - сумма заказа, в копейках
entry1.getValue() + entry2.getValue(),
// добавляем предыдущую комбинацию к новой
entry1.getKey(), entry1.getValue()));
}) // карта без дубликатов, т. е. без перестановок
.collect(() -> new TreeMap<>(Arrays::compare),
TreeMap::putAll, TreeMap::putAll))
// иначе пустая карта
.orElse(Collections.emptyMap());
}
/**
* @param min минимальное количество пунктов меню в заказе, включительно
* @param max максимальное количество пунктов меню в заказе, включительно
* @return представление отобранных комбинаций
*/
public List<String> quantity(int min, int max) {
return combinations.entrySet().stream()
.filter(entry -> entry.getKey().length >= min
&& entry.getKey().length <= max)
.map(MenuCombinations::entryToString)
.collect(Collectors.toList());
}
/**
* @param items пункты меню, которые должны присутствовать
* @return представление отобранных комбинаций
*/
public List<String> contains(Set<String> items) {
return combinations.entrySet().stream()
.filter(entry -> Arrays.asList(entry.getKey())
.containsAll(items))
.map(MenuCombinations::entryToString)
.collect(Collectors.toList());
}
/**
* @param min нижняя граница суммы заказа, включительно
* @return представление отобранных комбинаций
*/
public List<String> minAmount(double min) {
return combinations.entrySet().stream()
.filter(entry -> entry.getValue() >= (int) (min * 100))
.map(MenuCombinations::entryToString)
.collect(Collectors.toList());
}
/**
* @return строковое представление карты комбинаций.
*/
public List<String> get() {
return combinations.entrySet().stream()
.map(MenuCombinations::entryToString)
.collect(Collectors.toList());
}
@Override
public String toString() {
return combinations.entrySet().stream()
.map(MenuCombinations::entryToString)
.collect(Collectors.joining(", ", "[", "]"));
}
// вспомогательный метод, возвращает отформатированную строку
private static String entryToString(Map.Entry<String[], Integer> e) {
return String.format("%s=%d.%s", Arrays.toString(e.getKey()),
e.getValue() / 100, (e.getValue() % 100 + "00").substring(0, 2));
}
}
public static void main(String[] args) {
Map<String, Double> menu = Map.of(
"Fruit", 2.15, "Fries", 2.75, "Salad", 3.35,
"Wings", 3.55, "Mozzarella", 4.20, "Plate", 5.80);
System.out.println(new MenuCombinations(menu, 4.30).quantity(2, 2));
System.out.println(new MenuCombinations(menu, 5.5).minAmount(5.5));
System.out.println(new MenuCombinations(menu, 2.15));
System.out.println(new MenuCombinations(menu, 8.60).quantity(4, 4));
System.out.println(new MenuCombinations(menu, 9.2).contains(Set.of("Plate")));
System.out.println("Карта комбинаций для бюджета: 8.50");
new MenuCombinations(menu, 8.5).get().forEach(System.out::println);
}
Вывод:
[[Fruit, Fruit]=4.30]
[[Fries, Fries]=5.50, [Fruit, Salad]=5.50]
[[Fruit]=2.15]
[[Fruit, Fruit, Fruit, Fruit]=8.60]
[[Fries, Plate]=8.55, [Fruit, Plate]=7.95, [Plate]=5.80, [Plate, Salad]=9.15]
Карта комбинаций для бюджета: 8.50
[Fries]=2.75
[Fries, Fries]=5.50
[Fries, Fries, Fries]=8.25
[Fries, Fries, Fruit]=7.65
[Fries, Fruit]=4.90
[Fries, Fruit, Fruit]=7.50
[Fries, Fruit, Salad]=8.25
[Fries, Fruit, Wings]=8.45
[Fries, Mozzarella]=6.95
[Fries, Salad]=6.10
[Fries, Wings]=6.30
[Fruit]=2.15
[Fruit, Fruit]=4.30
[Fruit, Fruit, Fruit]=6.45
[Fruit, Fruit, Mozzarella]=8.50
[Fruit, Fruit, Salad]=7.65
[Fruit, Fruit, Wings]=7.85
[Fruit, Mozzarella]=6.35
[Fruit, Plate]=7.95
[Fruit, Salad]=5.50
[Fruit, Wings]=5.70
[Mozzarella]=4.20
[Mozzarella, Mozzarella]=8.40
[Mozzarella, Salad]=7.55
[Mozzarella, Wings]=7.75
[Plate]=5.80
[Salad]=3.35
[Salad, Salad]=6.70
[Salad, Wings]=6.90
[Wings]=3.55
[Wings, Wings]=7.10
См. The map-and-reduce approach to build a multiset