I want to sort a shopping list based on the order items were checked off in previous shopping trips. For example I go to the store and shop Apples, Bananas and Eggs.

Next I go to the store I shop Avocados and Tomatos and Apples. For my next trip the application sorts Avocados, Tomatos and Apples all before Eggs f.e.

I found this post talking about topological sorting: How to sort a shopping list based on previous pick order?.

However I am not sure how this should work since in theory I could have cycles (A user could theoretically check off apples and then bananas and the next time bananas are checked off before apples).

Could you guide me on how to tackle this problem?

Kind regards

CodePudding user response：

I assume:

1. Past item orderings should guide ordering the current order.
2. Any new items appear after any items ordered historically.
3. Orderings further back in time should have less impact than more recent orderings.

My idea is to assign weights to items seen in past orders based on:

1. Their position in a historic ordering.
2. How old that odering is.

The weightings might need adjusting, but, using data from that other question you link to, the Python code below does create orderings based on historic orderings:

from collections import defaultdict

shop = [['Toothpaste', 'Bread', 'Meat', 'Vegetables', 'Milk', 'Ice cream'],      # last
        ['CDs', 'Bread', 'Fruit', 'Vegetables', 'Juice', 'Sugar', 'Chocolates'], # last-but-1
        ['Meat', 'Juice', 'Milk', 'Sugar']]  # last-but-2

def weight_from_index(idx: int) -> float | int:
    "Items to the left are of LOwer wt and will sort first."
    return idx   1

def historic_multiplier(idy: int) -> float:
    "Older rows have larger multipliers and so are of lower overall weight."
    return (idy   1)**1

def shopping_weights(history: list[list[str]]) -> dict[str, int | float]:
    "Weight for items from historic shops."
    item2weight = defaultdict(float)
    for y, hist in enumerate(history):
        for x, item in enumerate(hist):
            item2weight[item]  = historic_multiplier(y) * weight_from_index(x)
    return dict(item2weight)

def order_items(items: list[str], weights) -> list[str]:
    wts = weights.copy()
    new_items = set(items) - set(wts)

    # New items last, but in given order otherwise
    max_wt = max(wts.values())
    for itm in new_items:
        wts[itm] = max_wt   1   items.index(itm)

    return sorted(items, key = lambda i: wts[i])


item_weights = shopping_weights(shop)
new_shop = ['Curry', 'Vegetables', 'Eggs', 'Milk', 'CDs', 'Meat']

new_order = order_items(new_shop, item_weights)
print(new_order)
# ['CDs', 'Meat', 'Vegetables', 'Milk', 'Curry', 'Eggs']


# Update the historic item orders
shop.insert(0, new_order)