Множества как алгебра: пересечение, разность, подмножество

IO.println(orders(42, 300, 30).get(0));

Order[number=1, day=1, guest=2, items=[Item[name=чай, price=120, qty=1], Item[name=какао, price=200, qty=2]]]

/** Что брал гость с дня from по день to включительно: названия позиций без повторов, по алфавиту. */
Set<String> itemsOf(List<Order> orders, int guest, int from, int to) {
    return orders.stream()
            .filter(order -> order.guest() == guest && order.day() >= from && order.day() <= to)
            .flatMap(order -> order.items().stream())
            .map(Item::name)
            .collect(Collectors.toCollection(TreeSet::new));
}

Set<String> before = itemsOf(orders, 17, 1, 15);
Set<String> after = itemsOf(orders, 17, 16, 30);
IO.println("дни 1–15: " + before + ", дни 16–30: " + after);

дни 1–15: [капучино, эклер, эспрессо], дни 16–30: [какао, капучино, эспрессо]

/** Напитки меню, остальное — десерты. Set.of — неизменяемое множество. */
static final Set<String> DRINKS = Set.of("латте", "капучино", "эспрессо", "американо", "раф", "какао", "матча", "чай");

[капучино, американо, матча, раф, какао, чай, латте, эспрессо]
[латте, чай, какао, раф, матча, американо, капучино, эспрессо]

/** Пересечение: что есть и в a, и в b. Ответ — новое множество, a и b не меняются. */
Set<String> intersection(Set<String> a, Set<String> b) {
    Set<String> result = new TreeSet<>(a);   // копия: retainAll меняет множество, у которого вызван
    result.retainAll(b);
    return result;
}

IO.println("осталось:        " + intersection(before, after));
IO.println("осталось, стрим: " + before.stream().filter(after::contains).toList());

осталось:        [капучино, эспрессо]
осталось, стрим: [капучино, эспрессо]

/** Объединение: что есть хотя бы в одном из двух. */
Set<String> union(Set<String> a, Set<String> b) {
    Set<String> result = new TreeSet<>(a);
    result.addAll(b);
    return result;
}

/** Разность: что есть в a, но нет в b. */
Set<String> difference(Set<String> a, Set<String> b) {
    Set<String> result = new TreeSet<>(a);
    result.removeAll(b);
    return result;
}

IO.println("всё за месяц:    " + union(before, after));
IO.println("перестал брать:  " + difference(before, after));
IO.println("начал брать:     " + difference(after, before));

всё за месяц:    [какао, капучино, эклер, эспрессо]
перестал брать:  [эклер]
начал брать:     [какао]

IO.println("сменилось:       " + difference(union(before, after), intersection(before, after)));

сменилось:       [какао, эклер]

before.retainAll(after);                       // без копии — меняем само before
IO.println("осталось:       " + before);
IO.println("перестал брать: " + difference(before, after));

осталось:       [капучино, эспрессо]
перестал брать: []

DRINKS.retainAll(before);   // UnsupportedOperationException

Exception in thread "main" java.lang.UnsupportedOperationException

IO.println("гость 2 — только напитки:  " + DRINKS.containsAll(itemsOf(orders, 2, 1, 30)));
IO.println("гость 17 — только напитки: " + DRINKS.containsAll(itemsOf(orders, 17, 1, 30)));

гость 2 — только напитки:  true
гость 17 — только напитки: false

IO.println("HashSet и TreeSet: " + new HashSet<>(before).equals(before));
IO.println("до и после:        " + before.equals(after));
IO.println("два списка:        " + List.of("капучино", "эспрессо").equals(List.of("эспрессо", "капучино")));

HashSet и TreeSet: true
до и после:        false
два списка:        false

Set<String> month17 = itemsOf(orders, 17, 1, 30);
IO.println("у 17 и 7 общего нет: " + Collections.disjoint(month17, itemsOf(orders, 7, 1, 30)));
IO.println("у 17 и 2 общего нет: " + Collections.disjoint(month17, itemsOf(orders, 2, 1, 30)));

у 17 и 7 общего нет: true
у 17 и 2 общего нет: false

Map<Integer, Long> visits = orders.stream()
        .collect(Collectors.groupingBy(Order::guest, Collectors.counting()));
Set<String> menu = MENU.stream().map(Item::name).collect(Collectors.toCollection(TreeSet::new));
Set<String> frequentCommon = visits.entrySet().stream()
        .filter(entry -> entry.getValue() >= 22)
        .map(entry -> itemsOf(orders, entry.getKey(), 1, 30))
        .reduce(menu, (common, items) -> intersection(common, items));
IO.println("общее у самых частых: " + frequentCommon);

общее у самых частых: [какао]

/** Гости, которые заходили с дня from по день to: номера карт без повторов, в порядке первого визита. */
List<Integer> visitors(List<Order> orders, int from, int to) {
    return orders.stream()
            .filter(order -> order.day() >= from && order.day() <= to)
            .map(Order::guest)
            .distinct()
            .toList();
}

List<Integer> early = visitors(orders, 1, 10);
List<Integer> late = visitors(orders, 21, 30);
Set<Integer> lateSet = new HashSet<>(late);
List<Integer> backByList = early.stream().filter(late::contains).toList();      // contains списка
List<Integer> backBySet = early.stream().filter(lateSet::contains).toList();    // contains множества
IO.println("вернулись " + backBySet.size() + " из " + early.size() + ", ответы равны: " + backByList.equals(backBySet));

вернулись 233 из 254, ответы равны: true

/** Сколько всего сравнений сделает contains списка list, если спросить его о каждом госте из who. */
long listComparisons(List<Integer> who, List<Integer> list) {
    return who.stream()
            .mapToLong(guest -> {
                int index = list.indexOf(guest);               // contains ищет так же: с начала списка
                return index >= 0 ? index + 1 : list.size();   // нашёл на месте index — index + 1 сравнений
            })
            .sum();
}

IO.println("список: сравнений " + listComparisons(early, late)
        + "; множество: добавлений " + late.size() + ", обращений " + early.size());

список: сравнений 34252; множество: добавлений 262, обращений 254

for (int guests : List.of(1000, 2000, 4000, 8000)) {
    List<Order> month = orders(42, guests, 30);
    List<Integer> first = visitors(month, 1, 10);
    List<Integer> last = visitors(month, 21, 30);
    IO.println(guests + " гостей: список " + listComparisons(first, last)
            + ", множество " + (last.size() + first.size()));
}

1000 гостей: список 425976, множество 1794
2000 гостей: список 1674660, множество 3564
4000 гостей: список 6640572, множество 7107
8000 гостей: список 26485356, множество 14193

java Coffee.java

// Coffee.java — учебный пример статьи 1 серии «Алгоритмы на стримах».
// Запуск: java Coffee.java (нужен JDK 25)

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
import java.util.stream.Collectors;

/** Позиция заказа: название, цена за штуку в рублях, сколько штук. */
record Item(String name, int price, int qty) {}

/** Заказ: номер, день месяца, номер карты гостя, позиции. */
record Order(int number, int day, int guest, List<Item> items) {

    /** Сумма заказа в рублях. */
    int total() {
        return items.stream().mapToInt(item -> item.price() * item.qty()).sum();
    }
}

/** Меню кофейни «Наковальня»: название и цена в рублях, по одной штуке. */
static final List<Item> MENU = List.of(
        new Item("латте", 250, 1), new Item("капучино", 220, 1), new Item("эспрессо", 150, 1),
        new Item("американо", 170, 1), new Item("раф", 290, 1), new Item("какао", 200, 1),
        new Item("матча", 280, 1), new Item("чай", 120, 1), new Item("круассан", 180, 1),
        new Item("чизкейк", 320, 1), new Item("сырник", 210, 1), new Item("эклер", 190, 1));

/**
 * Заказы {@code guests} гостей за {@code days} дней. Одно и то же зерно —
 * одни и те же заказы на любом компьютере. Генератор — не тема статьи:
 * читать его не обязательно.
 */
List<Order> orders(long seed, int guests, int days) {
    Random random = new Random(seed);
    List<List<Item>> liked = new ArrayList<>();          // у каждого гостя три любимые позиции
    List<Double> chance = new ArrayList<>();             // и своя вероятность зайти в день
    for (int guest = 0; guest < guests; guest++) {
        List<Item> three = new ArrayList<>();
        while (three.size() < 3) {
            Item item = MENU.get(random.nextInt(MENU.size()));
            if (!three.contains(item)) {
                three.add(item);
            }
        }
        liked.add(List.copyOf(three));
        chance.add(0.05 + random.nextInt(12) * 0.05);
    }
    List<Order> orders = new ArrayList<>();
    for (int day = 1; day <= days; day++) {
        for (int guest = 0; guest < guests; guest++) {
            if (random.nextDouble() >= chance.get(guest)) {
                continue;                                 // сегодня этот гость не пришёл
            }
            List<Item> items = new ArrayList<>();
            int positions = 1 + random.nextInt(3);
            for (int i = 0; i < positions; i++) {
                Item pick = random.nextInt(4) < 3
                        ? liked.get(guest).get(random.nextInt(3))       // обычно — любимое
                        : MENU.get(random.nextInt(MENU.size()));       // иногда — что-то ещё
                int qty = random.nextInt(10) == 0 ? 2 : 1;
                if (items.stream().noneMatch(item -> item.name().equals(pick.name()))) {
                    items.add(new Item(pick.name(), pick.price(), qty));
                }
            }
            orders.add(new Order(orders.size() + 1, day, guest + 1, List.copyOf(items)));
        }
    }
    return List.copyOf(orders);
}

/** Напитки меню, остальное — десерты. Set.of — неизменяемое множество. */
static final Set<String> DRINKS = Set.of("латте", "капучино", "эспрессо", "американо", "раф", "какао", "матча", "чай");

/** Что брал гость с дня from по день to включительно: названия позиций без повторов, по алфавиту. */
Set<String> itemsOf(List<Order> orders, int guest, int from, int to) {
    return orders.stream()
            .filter(order -> order.guest() == guest && order.day() >= from && order.day() <= to)
            .flatMap(order -> order.items().stream())
            .map(Item::name)
            .collect(Collectors.toCollection(TreeSet::new));
}

/** Пересечение: что есть и в a, и в b. Ответ — новое множество, a и b не меняются. */
Set<String> intersection(Set<String> a, Set<String> b) {
    Set<String> result = new TreeSet<>(a);   // копия: retainAll меняет множество, у которого вызван
    result.retainAll(b);
    return result;
}

/** Объединение: что есть хотя бы в одном из двух. */
Set<String> union(Set<String> a, Set<String> b) {
    Set<String> result = new TreeSet<>(a);
    result.addAll(b);
    return result;
}

/** Разность: что есть в a, но нет в b. */
Set<String> difference(Set<String> a, Set<String> b) {
    Set<String> result = new TreeSet<>(a);
    result.removeAll(b);
    return result;
}

/** Гости, которые заходили с дня from по день to: номера карт без повторов, в порядке первого визита. */
List<Integer> visitors(List<Order> orders, int from, int to) {
    return orders.stream()
            .filter(order -> order.day() >= from && order.day() <= to)
            .map(Order::guest)
            .distinct()
            .toList();
}

/** Сколько всего сравнений сделает contains списка list, если спросить его о каждом госте из who. */
long listComparisons(List<Integer> who, List<Integer> list) {
    return who.stream()
            .mapToLong(guest -> {
                int index = list.indexOf(guest);               // contains ищет так же: с начала списка
                return index >= 0 ? index + 1 : list.size();   // нашёл на месте index — index + 1 сравнений
            })
            .sum();
}

void main() {
    List<Order> orders = orders(42, 300, 30);

    // 1. Что брал гость 17 в дни 1–15 и в дни 16–30
    Set<String> before = itemsOf(orders, 17, 1, 15);
    Set<String> after = itemsOf(orders, 17, 16, 30);
    IO.println("дни 1–15: " + before + ", дни 16–30: " + after);

    // 2. Пересечение, объединение, разность — новые множества, before и after целы
    IO.println("осталось:        " + intersection(before, after));
    IO.println("осталось, стрим: " + before.stream().filter(after::contains).toList());
    IO.println("всё за месяц:    " + union(before, after));
    IO.println("перестал брать:  " + difference(before, after));
    IO.println("начал брать:     " + difference(after, before));
    IO.println("сменилось:       " + difference(union(before, after), intersection(before, after)));

    // 3. Подмножество: брал ли гость за месяц только напитки
    IO.println("гость 2 — только напитки:  " + DRINKS.containsAll(itemsOf(orders, 2, 1, 30)));
    IO.println("гость 17 — только напитки: " + DRINKS.containsAll(itemsOf(orders, 17, 1, 30)));

    // 4. Равенство: множества равны по содержимому, списки — ещё и по порядку
    IO.println("HashSet и TreeSet: " + new HashSet<>(before).equals(before));
    IO.println("до и после:        " + before.equals(after));
    IO.println("два списка:        " + List.of("капучино", "эспрессо").equals(List.of("эспрессо", "капучино")));

    // 5. Не пересекаются: есть ли у двух гостей хоть одна общая позиция
    Set<String> month17 = itemsOf(orders, 17, 1, 30);
    IO.println("у 17 и 7 общего нет: " + Collections.disjoint(month17, itemsOf(orders, 7, 1, 30)));
    IO.println("у 17 и 2 общего нет: " + Collections.disjoint(month17, itemsOf(orders, 2, 1, 30)));

    // 6. Пересечение многих: что брали все самые частые гости — 22 визита и больше
    Map<Integer, Long> visits = orders.stream()
            .collect(Collectors.groupingBy(Order::guest, Collectors.counting()));
    Set<String> menu = MENU.stream().map(Item::name).collect(Collectors.toCollection(TreeSet::new));
    Set<String> frequentCommon = visits.entrySet().stream()
            .filter(entry -> entry.getValue() >= 22)
            .map(entry -> itemsOf(orders, entry.getKey(), 1, 30))
            .reduce(menu, (common, items) -> intersection(common, items));
    IO.println("общее у самых частых: " + frequentCommon);

    // 7. Цена: кто из гостей первых десяти дней вернулся в последние десять
    List<Integer> early = visitors(orders, 1, 10);
    List<Integer> late = visitors(orders, 21, 30);
    Set<Integer> lateSet = new HashSet<>(late);
    List<Integer> backByList = early.stream().filter(late::contains).toList();      // contains списка
    List<Integer> backBySet = early.stream().filter(lateSet::contains).toList();    // contains множества
    IO.println("вернулись " + backBySet.size() + " из " + early.size() + ", ответы равны: " + backByList.equals(backBySet));
    IO.println("список: сравнений " + listComparisons(early, late)
            + "; множество: добавлений " + late.size() + ", обращений " + early.size());

    // 8. Рост: гостей вдвое больше — у списка работы вчетверо больше, у множества вдвое
    for (int guests : List.of(1000, 2000, 4000, 8000)) {
        List<Order> month = orders(42, guests, 30);
        List<Integer> first = visitors(month, 1, 10);
        List<Integer> last = visitors(month, 21, 30);
        IO.println(guests + " гостей: список " + listComparisons(first, last)
                + ", множество " + (last.size() + first.size()));
    }

    // Сделай руками — раскомментируй и запусти:
    // DRINKS.retainAll(before);   // UnsupportedOperationException
}