Is there a way how we can make this code less memory consuming?

Final cleaned up edit. I tested 1e6 orders with 500 unique products and got results in about 3 minutes.

I did filter by requiring a minimum number of orders and by stopping after 3-product groups. These can be changed in the function call:

memo = find_product_groups(df, min_unique_orders=10, max_group_size=3)

Output

testing 500 products in 1000000.0 orders where there are between 1 and 10 products per order
made test data in 72.29691982269287 seconds
counted_groups in 199.78216004371643 seconds
showing first five 3-member group sorted by decreasing number of orders
('product_259', 'product_263', 'product_435') 11
('product_252', 'product_432', 'product_63') 11
('product_114', 'product_139', 'product_156') 11
('product_101', 'product_11', 'product_179') 11
('product_115', 'product_301', 'product_45') 11

Code

import pandas as pd
import collections

import time #just for timing
import numpy as np #just for creating the test data
np.random.seed(1)

def init_data():
    #Initialize test data
    start_create_data = time.time()
    num_products = 500
    num_orders = 1e6
    max_order_size = 10

    print('testing',num_products,'products in',num_orders,'orders where there are between 1 and',max_order_size,'products per order')

    products = ['product_'+str(p) for p in range(num_products)]

    order_sizes = np.round(np.random.uniform(low=1,high=max_order_size,size=int(num_orders)))

    order_list = []
    for order_size in order_sizes:
        order = np.random.choice(products,int(order_size),replace=False)
        order_list.append(order)
    
    # Create pandas DataFrame
    df = pd.DataFrame({'Product':order_list})
    print('made test data in',time.time()-start_create_data,'seconds')
    return df

def find_product_groups(df, min_unique_orders=1, max_group_size=None):
    
    #Initialize the memo with single-product groups
    memo = collections.defaultdict(set)
    for ind,order in df['Product'].items():
        for product in order:
            memo[(product,)].add(ind)

    #Build up the groups from 1-smaller groups, updating the memo
    unique_prods = sorted(p[0] for p in memo.keys())
    groups = list(memo.keys())
    
    while groups:
        group = groups.pop()
        
        #Skip if the max_group_size is set and this group is already max size
        if max_group_size and len(group) == max_group_size:
            continue
        
        last_prod = group[-1]
        last_prod_ind = unique_prods.index(last_prod)
        for prod in unique_prods[last_prod_ind+1:]:
            new_inds = memo[group].intersection(memo[(prod,)])

            #Only add the new group if there are enough orders
            if len(new_inds) >= min_unique_orders:
                new_group = (*group,prod)
                memo[new_group] = new_inds
                groups.append(new_group)
                
    return memo


df = init_data()

start_count_groups = time.time()
memo = find_product_groups(df, min_unique_orders=10, max_group_size=3)
print('counted_groups in',time.time()-start_count_groups,'seconds')


print('showing first five 3-member group sorted by decreasing number of orders')
filt_memo = {group:order_inds for group,order_inds in memo.items() if len(group) >= 3}
filt_memo = dict(sorted(filt_memo.items(),key=lambda kv: -len(kv[1]))[:5])

for group,order_inds in filt_memo.items():
    print(group,len(order_inds))