групповые блюда из общих ингредиентов

Question

Я работаю над вопросом ниже:

Предположим, у вас есть список блюд, где каждое блюдо связано с список ингредиентов. Сгруппируйте блюда из общих ингредиентов.

Например:

Введите:

"Pasta" -> ["Tomato Sauce", "Onions", "Garlic"] 
"Chicken Curry" --> ["Chicken", "Curry Sauce"] 
"Fried Rice" --> ["Rice", "Onions", "Nuts"] 
"Salad" --> ["Spinach", "Nuts"] 
"Sandwich" --> ["Cheese", "Bread"] 
"Quesadilla" --> ["Chicken", "Cheese"] 

Выход:

("Pasta", "Fried Rice") 
("Fried Rice, "Salad")
("Chicken Curry", "Quesadilla")
("Sandwich", "Quesadilla") 

Также, какова сложность времени и пространства?

Я пришел с кодом ниже. Есть ли лучший способ решить эту проблему? Похоже, алгоритм связан компонент из теории графов.

public static void main(String[] args) {
    List<String> ing1 = Arrays.asList("Tomato Sauce", "Onions", "Garlic");
    List<String> ing2 = Arrays.asList("Chicken", "Curry Sauce");
    List<String> ing3 = Arrays.asList("Rice", "Onions", "Nuts");
    List<String> ing4 = Arrays.asList("Spinach", "Nuts");
    List<String> ing5 = Arrays.asList("Cheese", "Bread");
    List<String> ing6 = Arrays.asList("Chicken", "Cheese");

    Map<String, List<String>> map = new HashMap<>();
    map.put("Pasta", ing1);
    map.put("Chicken Curry", ing2);
    map.put("Fried Rice", ing3);
    map.put("Salad", ing4);
    map.put("Sandwich", ing5);
    map.put("Quesadilla", ing6);

    System.out.println(group(map));
}

private static List<List<String>> group(Map<String, List<String>> map) {
    List<List<String>> output = new ArrayList<>();

    if (map == null || map.isEmpty()) {
        return output;
    }

    Map<String, List<String>> holder = new HashMap<>();

    for (Map.Entry<String, List<String>> entry : map.entrySet()) {
        String key = entry.getKey();
        List<String> value = entry.getValue();
        for (String v : value) {
            if (!holder.containsKey(v)) {
                holder.put(v, new ArrayList<String>());
            }
            holder.get(v).add(key);
        }
    }
    return new ArrayList<List<String>>(holder.values());
}

Answer 1

Мы можем получить реальную оценку сложности этого подхода, используя теорию графов.Подход «связанных компонентов» будет иметь O(|V| + |E|) сложность, где V - это набор всех ингредиентов и блюд , а E - этонабор, содержащий все отношения (a, b), где каждый a является блюдом, а b является ингредиентом блюда b.(т. е. при условии, что вы сохраняете этот график G = (V, E) в списке смежности, а не в матрице смежности)

В любом алгоритме, который должен найти все ингредиенты каждого блюда, чтобы найти результат, выпридется исследовать каждое блюдо и все их ингредиентов.Это приведет к расследованию (т.е. обходу), которое займет O(|V| + |E|) времени, что будет означать, что никакой такой алгоритм не может быть лучше, чем ваш подход.

Answer 2

Давайте сначала превратим эту проблему в проблему с графиками.Каждое блюдо и каждый ингредиент будут vertex.Каждое соотношение между блюдом и ингредиентом будет edge.

. Давайте проанализируем максимальный размер раствора.Если предположить, что в общей сложности имеется N блюд и M ингредиентов, максимальный выходной результат определяется, когда каждое блюдо связано.В этом случае выходные данные имеют размер N^2, так что это нижняя граница сложности времени, которую вы можете достичь.Мы можем довольно легко создать входные данные, для которых мы должны выполнить итерацию по всем вершинам и ребрам, поэтому еще одна нижняя граница сложности времени - N * M.Также мы должны сохранить все вершины и ребра, чтобы M * N являлось нижней границей сложности пространства.

Теперь давайте проанализируем ваше решение.Вы перебираете все блюда = N, и для каждого из блюд вы перебираете все значения = M, и с помощью O(1) вы проверяете, есть ли в словаре итого O(N * M).Ваша сложность пространства также O(M * N).Я бы сказал, что ваше решение хорошее.

Answer 3

Вам просто нужно построить обратную карту здесь.

Я думаю, что вы можете написать код более выразительным образом, используя Stream API, представленный в Java8.

Основные шаги:

• Извлеките все ингредиенты с карты
• Для каждого ингредиента получите набор блюд, и у вас будет много таких наборов - соберите все такие наборы в набор - и поэтому возвращаемым типом метода будет Set<Set<String>>

Ниже приведена реализация:

private static Set<Set<String>> buildReverseMap(Map<String, Set<String>> map) {
    // extracting all the values of map in a Set
    Set<String> ingredients = map.values()
            .stream()
            .flatMap(Set::stream)
            .collect(Collectors.toSet());


    return ingredients.stream()
            // map each ingredient to a set
            .map(s ->
                    map.entrySet()
                            .stream()
                            .filter(entry -> entry.getValue().contains(s))
                            .map(Map.Entry::getKey)
                            .collect(Collectors.toSet())
            ).collect(Collectors.toSet());
}

Анализ сложности времени:

Если у вас есть N блюд и M ингредиентов, и в худшем случае каждый дистрибутив может иметь каждый ингредиент. Для каждого ингредиента вам нужно пройтись по каждому блюду и проверить, содержит ли он текущий ингредиент или нет. Эта проверка может быть сделана в амортизированном O(1), поскольку у нас может быть ингредиенты HashSet<String> для каждого блюда.

Таким образом, для каждого ингредиента вы будете перебирать каждое блюдо и проверять, содержит ли это блюдо этот ингредиент или нет в амортизированном O(1). Это дает временную сложность амортизации O(M*N).

Анализ сложности пространства:

Просто O(M*N), так как в худшем случае вы можете создать каждый дистрибутив из каждого доступного ингредиента.

Примечание:

Вы можете вернуть List<Set<String>> вместо Set<Set<String>>, просто изменив .collect(Collectors.toSet()) на .collect(Collectors.toList())