Optimizing for maximum number of options to show customer given collection of their existing selections

I think there are a couple of things that need to be considered before you're able to fully tackle this problem.

1. SKUs and stock

In an E-Commerce system, as was pointed out correctly in a comment, there's usually a concept of SKUs which uniquely describe a single product. So each of your unique apple types would be a separate SKU. In your simplified examples, the SKUs are for small, medium and large apples; in your "fully" example, you'd have separate SKUs for "small red apple", "medium red apple", "small green apple", "large green apple" etc. The fact that all of these are "apples" and the possible combinations of various attributes don't matter in terms of SKUs – these categorizations based on attributes is an arbitrary grouping criterion that is put on top of the list of all SKUs to make them more approachable to users of the system (be it customers, employees, tax advisors etc.).

Subsequently, each SKU has a quantity >= 0 in stock. Again, these quantities are completely independent of each other and the fact that you might say "we have 20 apples in stock" (where 5 of them are S, 11 M and 4 L) is a grouping approach that you put on top, not one that actually exists from a stock keeping perspective.

2. SKU/category assignment/locking

The 2nd issue to understand is the concept of article assignment/locking. That is, when someone adds an article to their cart, you temporarily mark the article as if it were already purchased so that it can't get sold twice. This approach is usually referred to as locking. Depending on order frequency, you then set a timeout of that lock, e.g. 30 minutes, meaning, if a purchase doesn't happen within 30 minutes, you release the lock and allow another customer to lock it (and ideally purchase it).

In a normal E-Commerce context, you would create such locks on a SKU level, but it sound like this is not the right approach in your case since you also allow users to add non-specific articles to their carts. So what you probably want is a kind of multi-level lock:

• When a user adds a non-specific article to their cart, you lock the selected quantity of all categories that the article is assigned to.
• When a user adds a specific SKU to their cart, you lock the selected quantity of the specific SKU for that user.
• You add constraints that doesn't allow any category and any specific SKU to exceed their individual current stock.

3. Distribution

The last step then is actual distribution. Here, you go from most to least specific, i.e. you start by alotting the specific SKUs, followed by articles assigned to most categories all the way to the "I don't care, I just want any apple" customers.

I hope this makes sense to you. I'm aware that it's highly conceptual. But it's hard to give specific answers to a somewhat generic and (apparently) theoretical use case.

I took a stab, please see below.

You can play around with the code by copying the entire code below into a single file (say, test.rb) and then running it from the command line (ie, ruby test.rb)

The design is based off the idea that the problem of "maximizing the options that remain in-basket" is logically equivalent to "removing options from the basket in order of most common to least common".

# test.rb
require 'minitest/autorun'

class Basket
  attr_accessor :basket
  def initialize(opts={})
    @basket = opts[:basket]
  end


  def remaining_options(selected_options=[])
    return {} if @basket.empty?

    selected_options.each do |option_criteria|
      select_option(option_criteria)
    end

    print_basket
  end

  def select_option(option_criteria)
    selectable_options = @basket.select { |opt| matches?(opt, option_criteria) }
    option_to_select = most_common_option(selectable_options)
    remove_from_basket option_to_select
  end

  def most_common_option( selectable_options )
    max_matches = 0
    max_matches_idx = nil

    selectable_options.each_with_index do |option, i|
      option_matches = 0
      option.keys.each do |k|
        selectable_options.each do |opt, i|
          option_matches += 1 if option[k] == opt[k]
        end

        if option_matches > max_matches
          max_matches = option_matches
          max_matches_idx = i
        end
      end
    end

    selectable_options[max_matches_idx]
  end

  def remove_from_basket( option_to_select )
    idx_to_remove = @basket.index { |i| matches?(i, option_to_select)}
    @basket.delete_at idx_to_remove
  end

  def matches?(opt, selected)
    selected.keys.all? { |k| selected[k] == opt[k] }
  end

  def print_basket
    hsh = Hash.new { |h,k| h[k] = [] }

    @basket.each do |item_hsh|
      item_hsh.each do |k, v|
        hsh[k] << v unless hsh[k].include?(v)
      end
    end

    hsh
  end
end

class BasketTest < Minitest::Test
  def setup_basket
    Basket.new basket: [
      {size:'S', price:1},
      {size:'M', price:2},
      {size:'L', price:2},
    ]
  end

  def test_initial_basket_case
    basket = setup_basket
    assert basket.remaining_options == {size:['S','M','L'], price: [1,2]}
  end

  def test_returns_empty_if_basket_empty
    basket = Basket.new basket: []
    assert basket.remaining_options([{price:2}]) == {}
  end

  def test_one_pick
    basket = setup_basket
    assert basket.remaining_options([{price:2}]) == {size:['S', 'L'], price: [1,2]}
  end

  def test_two_picks
    basket = setup_basket
    assert basket.remaining_options([{price:2}, {price:2}]) == {size:['S'], price: [1]}
  end

  def test_maximizes_options
    larger_basket = Basket.new basket: [
      {size:'S', price:1},
      {size:'L', price:2},
      {size:'M', price:2},
      {size:'M', price:2}
    ]
    assert larger_basket.remaining_options([{price:2}]) == {size:['S', 'L', 'M'], price: [1,2]}
  end

  def test_maximizes_options_complex
    larger_basket = Basket.new basket: [
      {size:'S', price:1, color: 'red'},
      {size:'L', price:2, color: 'red'},
      {size:'M', price:2, color: 'purple'},
      {size:'M', price:2, color: 'green'},
      {size:'M', price:2, color: 'green'},
      {size:'M', price:2, color: 'green'}
    ]
    assert larger_basket.remaining_options([{price:2}, {color: 'green'}]) == {size:['S', 'L', 'M'], price: [1,2], color: ['red', 'purple', 'green']}
  end
end

Your question seams like a NP-complete problem to me, I can't prove it though ^^

The following code is only a proof of concept for you to test.

Edit: What the code does is: Given the "abstract items" in the client's cart and the "real items" stock in the basket, generate all the combinations of "real items" (let's call these combinations "virtual carts") that satisfy both the client's cart and the stock in the basket. Then, for each "virtual cart", simulate the remaining stock in the basket. Finally, make the union of the remaining choices of each "virtual basket".

require 'set'

def extract_options(basket)
  basket.each_with_object( {} ) do |item, options|
    item.each do |attr,value|
      options[attr] = Set.new unless options.has_key?(attr)
      options[attr] << value
    end
  end
end

def expand_item(item, options)
  expanded = [[]]
  item.each do |attr,value|
    opts = value.nil? ? options[attr] : [value]
    expanded = expanded.each_with_object( [] ) do |path,exp|
      opts.each { |val| exp << ( path.dup << [attr, val] ) }
    end
  end
  expanded.map(&:to_h)
end

def remaining_options(basket, cart)
  options = extract_options(basket)
  return [options] if cart.empty?
  remaining = []
  f,*r = *cart.map { |item| expand_item(item, options) }
  f.product(*r) do |cart|
    b = cart.each_with_object( basket.dup ) do |item,bask|
      break unless index = bask.index(item)
      bask.delete_at(index)
    end
    remaining << extract_options(b) if b
  end
  remaining.uniq
end

def remaining_options_union(basket,cart)
  remaining_options(basket,cart).each_with_object( {} ) do |remain,union|
    remain.each do |attr,set|
      union[attr] = Set.new unless union[attr]
      union[attr] += set
    end
  end
end

Your test-case is small so the calculation is quick:

basket = [
  {size:'S', price:1},
  {size:'M', price:2},
  {size:'L', price:2},
]

cart = []
remaining_options_union(basket,cart)
# => {:size=>#<Set: {"S", "M", "L"}>, :price=>#<Set: {1, 2}>}

cart << {size: nil, price: 2} # all attributes need to be populated
remaining_options(basket,cart)
# => [{:size=>#<Set: {"S", "L"}>, :price=>#<Set: {1, 2}>}, {:size=>#<Set: {"S", "M"}>, :price=>#<Set: {1, 2}>}]
remaining_options_union(basket,cart)
# => => {:size=>#<Set: {"S", "L", "M"}>, :price=>#<Set: {1, 2}>}


cart << {size: nil, price: 2} 
remaining_options(basket,cart)
# => [{:size=>#<Set: {"S"}>, :price=>#<Set: {1}>}]
remaining_options_union(basket,cart)
# => {:size=>#<Set: {"S"}>, :price=>#<Set: {1}>}

Update: The following code keeps the previously calculated "virtual baskets" in memory for speeding up the addition of a new item to the cart.

require 'set'

class Cart

  def self.extract_choices basket
    basket.each_with_object( {} ) do |item, attrs|
      item.each do |key,value|
        raise "Null valued item attribute in basket" if value.nil?
        attrs[key] = Set.new unless attrs.has_key?(key)
        attrs[key] << value
      end
    end
  end

  attr_reader :remaining_options

  def initialize basket
    choices = self.class.extract_choices basket
    
    @globs = choices # needed to unglob a null valued attribute in an item
    @attrs = choices.keys # attributes found in the items of the basket

    # The items in the basket shall have all the possible attributes populated and not null
    basket.each do |item|
      @attrs.each do |attr|
        raise "Invalid item in basket" unless item[attr]
      end
    end

    @virtual_baskets = [ basket ]
    @remaining_options = choices
  end

  def <<(item)
    # As we're using the 'Hash#==' method, each item must have all its
    # attributes set (the same ones as in the basket), no more, no less.
    item = @attrs.each_with_object( {} ) do |attr,obj|
      obj[attr] = item[attr]
    end

    # NOTE: an item with globs will multiply the number of virtual baskets
    update_virtual_baskets item

    choices = @virtual_baskets.map{|b| self.class.extract_choices b}

    @remaining_options = choices.each_with_object( {} ) do |choice, union|
      choice.each do |attr,set|
        union[attr] = Set.new unless union[attr]
        union[attr] += set
      end
    end
  end

  private

  def unglob item
    expanded_items = [[]]
    item.each do |attr, value|
      choices = value.nil? ? @globs[attr] : [value]
      expanded_items = expanded_items.each_with_object( [] ) do |pre, obj|
        choices.each { |val| obj << ( pre.dup << [attr, val] ) }
      end
    end
    expanded_items.map(&:to_h)
  end

  def update_virtual_baskets formated_item
    expanded_items = unglob formated_item
    valid_baskets = []
    @virtual_baskets.each do |basket|
      expanded_items.each do |item|
        basket.each_index do |idx|
          next unless basket[idx] == item
          bsk = basket.dup
          bsk.delete_at(idx)
          valid_baskets << bsk
        end
      end
    end
    raise "Error while adding item to cart - no stock" if valid_baskets.empty?
    @virtual_baskets = valid_baskets.uniq
  end
end

You can use it like this:

basket = [
  {origin:'IL', size:'S', color:'G', price:1},
  {origin:'SP', size:'M', color:'G', price:2},
  {origin:'SP', size:'M', color:'R', price:2},
  {origin:'SP', size:'M', color:'Y', price:3},
  {origin:'CA', size:'L', color:'G', price:1},
  {origin:'SP', size:'L', color:'G', price:4},
  {origin:'CA', size:'L', color:'R', price:4},
]

cart = Cart.new basket

cart << {price:2}
cart << {size:'M'}
cart << {origin:'SP'}
cart.remaining_options
# => {:origin=>#<Set: {"IL", "CA", "SP"}>, :size=>#<Set: {"S", "L", "M"}>, :color=>#<Set: {"G", "R", "Y"}>, :price=>#<Set: {1, 4, 3, 2}>}
cart << {price:2}
cart.remaining_options 
# => {:origin=>#<Set: {"IL", "CA"}>, :size=>#<Set: {"S", "L"}>, :color=>#<Set: {"G", "R"}>, :price=>#<Set: {1, 4}>}

Possible improvements: By adding a "quantity" to the items in the basket you should be able to reduce the size and the number of "virtual baskets". Also, if the price is a mandatory field (which makes sense) then you can "kind of" split the problem by price and make the code faster.

Remark: Another way to phrase what you're looking for would be: For each possible choice in each attribute (ex. :size is an attribute and one of its possible choices is 'S'), does it exist a combination of items in the cart that doesn't deplete it ? Unless there exists a mathematical formula to find it quickly, you'll have to almost walk through all the possible combinations in order to be able to respond 'no' to that question...

To a certain extent, my second proposal that keeps in memory the valid "virtual baskets" of the previous iteration is a sensible way to tackle the problem.