Given a dictionary of recipes {item: [ingredient_1, ingredient_2], ...} how can I sort the item keys efficiently such that we would never have item_n appear after another item_(n-m), m > 1, that used item_n as an ingredient.

for example:

{"cake" : ["egg", "sugar", "flour"], "flour": ["wheat", "titanium_dioxide"]}

should be sorted to

{"flour": ["wheat", "titanium_dioxide"], "cake" : ["egg", "sugar", "flour"]}

CodePudding user response：

Use this simple algorithm:

1. For each ingredient in an item, if the ingredient has it's own entry in the dictionary (as a separate item_2), define an edge where ingredient is the source and item is the destination. When you do that for all ingredients/items, you basically get a directed graph.
2. If the graph is cyclic, no such valid ordering exists.
3. If the graph is acyclic (that is, a DAG), use topological sort to get a valid ordering of items that need to be completed first (as a pre-requisite to some following item).

CodePudding user response：

Initialize an empty result list.

Initialize an empty hash table (or map or whatever) and call it references. Iterate through all the recipes, and every time you come across a recipe name or ingredient name, set references[name] = 0.

Iterate through all the recipes again. Every time you come across an ingredient, increment references[ingredient] in the hash table.

Now a loop.

If `references` is empty, you have completed successfully.
Create an empty string array called `zeroes`.  
For each key `k` in `references`:
    if `references[k] == 0`:
        Remove `references[k]`
        Append k to `zeroes`
If `zeroes` is empty, there is a cyclic dependency, so fail.
For each key `k` in `zeroes`:
    If there is a recipe for `k`:
        In the recipe for `k`, for each ingredient `i`:
            decrement `references[i]`
        Add the recipe for `k` to the result list.
Restart the loop
    

If the loop completes successfully, the sorted recipes will be in the result list.