优化选项的最大数量，以显示客户现有选择的给定集合

Question

这是一个旧问题(链接如下)的变体，我的措辞很差，所以没有充分解决我的问题。

背景

假设有一个包含苹果的苹果篮，每个苹果都是一个具有size属性的object，在这个特定的篮中，我们有3个苹果：[{size:'S'}, {size:'M'}, {size:'L'}]

在购物过程中，每次顾客在购物车中添加苹果时，他们都可以选择尺寸，但重要的是，他们不必选择尺寸，这是一个可选的选择器。

我正在尝试编写一种方法remaining_options，根据客户过去的选择历史，最大限度地增加客户在购物车中添加苹果时显示的最大选项数。尺寸选择是可选的这一事实非常重要。考虑以下两个例子：

示例A：客户选择一个选项

1. 客户将第一个苹果添加到购物车
2. 客户看到提示Please make a size selection (optional): [S, M, L]
3. 客户决定选择S
4. 顾客将第二个苹果添加到购物车
5. 客户看到提示Please make a size selection (optional): [M, L]

示例B:客户未选择选项

1. 客户将第一个苹果添加到购物车
2. 客户看到提示Please make a size selection (optional): [S, M, L]
3. 客户跳过此步骤
4. 顾客将第二个苹果添加到购物车
5. 客户看到提示Please make a size selection (optional): [S, M, L]

在示例B中，由于客户没有选择一个选项，因此仍显示可用的全套选项。该代码不是任意地"；删除"；选项集中的一个苹果。换句话说，此方法remaining_options不负责计算剩余数量，只负责计算剩余的选项。

注意：当然，即使这种方法不计算数量，但在现实世界结账时，库存会再次通过不同的方法为下一位客户进行调整。也就是说，假设在上面的例子中，顾客没有为第二个苹果选择尺寸，那么在结账时

• 示例A，客户将收到由其他代码随机选择的1个S苹果和第二个M或L苹果。如果客户收到[S,M]，那么下一个订购苹果的客户将只能添加1个苹果，而remaining_options将只能返回[L]
• 示例B，客户将收到2个随机的苹果，可以是[S,M]、[M,L]、[S,L]，由其他代码随机选择。如果客户收到[S,L]，那么下一个订购苹果的客户将只能添加1个苹果，而remaining_options将只返回[M]

复杂性

挑战在于，我希望remaining_options适用于苹果对象上任何给定数量的可能属性(size、color、price等)，以及这些属性的任何数量的选项。由于选择是可选的，用户可以拒绝选择size、color、price等。，或者选择1(例如，仅size)或2(例如，size和price)等等。

鉴于这种复杂性，重要的是代码而不是将向购物车添加苹果的过程视为一个独立的过程，其中remaining_options是通过购物篮中的选项减去最后选择的选项来计算的。

相反，代码应该查看客户购物车中的所有苹果，无论是否为每个苹果选择了一个选项，然后计算remaining_options的最大数量

之前发布的问题中的解决方案不起作用，因为他们做了前者，即将添加每个苹果视为一个独立的过程，从篮子中删除了一个选项。

下面是一个需要澄清的例子。假设3个苹果的篮子是这样的：

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

步骤1-添加第一个苹果

假设remaining_options对客户的现有进行了论证。因此，当客户将他们的第一个苹果添加到购物车中时，购物车中没有任何内容，因此所有选项都会返回

basket.remaining_options([])
=> {size:['S','M','L'], price: [1,2]}

步骤2-添加第二个苹果

为了完成第一笔苹果交易，客户决定选择一个price:2的苹果。然后他们把第二个苹果加入购物车。由于有不止一个苹果的price:2，客户的第一个选择没有造成容量限制，因此再次显示所有选项。

basket.remaining_options([{price:2}])
=> {size:['S','M','L'], price: [1,2]}

注意：@obiruby敏锐地观察到，尽管{size:['S','M','L'], price: [1,2]}在技术上是所有剩余的选项，但它们并不都是可选的。对于第二个苹果，如果客户选择M，则第一个苹果必须自动指定为L，因此不再可选择。这是通过我已经在使用的另一种方法来处理的。这么多方法。。。所有这些都让这个最大选项优化工作

步骤3-添加第三个苹果

为了完成第二笔苹果交易，客户决定再次选择一个price:2的苹果。然后他们把第三个苹果加入购物车。现在很棘手。如果这个代码只是减去选择的选项，那么在面值上，remaining_options可能会返回这个：{size:['S','M','L'], price: [1]}。但这并不准确，因为当所有price:2苹果都被拿走时，默认情况下所有M和L苹果也是如此。这就是为什么正确的代码需要集中查看现有的购物车。也就是说，这应该是结果：

basket.remaining_options([{price:2}, {price:2}])
=> {size:['S'], price: [1]}

还要注意的是，由于容量限制是如何工作的，该方法还应该正确返回以下内容：

basket.remaining_options([{price:2}, {size:'M'}])
=> {size:['S'], price: [1]}
# user's 1st ordered apple has a price request
# user's 2nd ordered apple has a size request
# COMBO of the 2 only work if...
# user's 1st ordered apple is the {price:2, size:'L'} apple in basket
# user's 2nd ordered apple is the {size:'M', price:'2'} apple in basket
# therefore if user is looking at remaining options for a 3rd apple, there's only the {size:'S', price:'1'} apple left in basket

所以。。。是的，非常感谢帮助写这个方法！我在旧职位上有一些不实用的想法。在查看所提出的解决方案(唉，它也没有集中查看现有的购物车)时，我意识到一个解决方案可以是在篮中列出所有可能的苹果组合，这些组合可以被分配来满足购物车中每个苹果的要求，并选择产生最多剩余选项的分配组合。但我觉得这个解决方案会非常低效，因为篮子、手推车和可能的选项都会增加。

Answer 1

我认为在您能够完全解决这个问题之前，需要考虑几件事。

1. SKU和库存

在电子商务系统中，正如评论中正确指出的那样，通常有一个SKU的概念，它唯一地描述了单个产品。因此，您的每一种独特的苹果类型都将是一个单独的SKU。在您的简化示例中，SKU适用于小型、中型和大型苹果；在您的"；完全"；例如，对于"；小红苹果"中红苹果""小青苹果"大绿苹果"；等等。事实上，所有这些都是"；苹果"；各种属性的可能组合对SKU来说并不重要——这些基于属性的分类是一个任意的分组标准，它被放在所有SKU列表的顶部，以使系统用户(无论是客户、员工、税务顾问等)更容易接近它们

随后，每个SKU都有一个数量>=0库存。同样，这些数量是完全相互独立的，而且事实上，你可能会说"；我们有20个苹果存货；(其中5个是S，11个M和4个L)是一种你放在首位的分组方法，而不是从库存角度来看实际存在的方法。

2. SKU/类别分配/锁定

要理解的第二个问题是文章分配/锁定的概念。也就是说，当有人将一件物品添加到他们的购物车中时，你会临时将该物品标记为已经购买，这样它就不会卖出两次。这种方法通常被称为锁定。根据订单频率，您可以设置锁定的超时时间，例如30分钟，这意味着，如果在30分钟内没有进行购买，您可以解除锁定并允许另一位客户锁定(理想情况下是购买)。

在正常的电子商务环境中，你会在SKU级别上创建这样的锁，但在你的情况下，这听起来不是正确的方法，因为你还允许用户将非特定的文章添加到他们的购物车中。所以你可能想要的是一种多级锁：

• 当用户将非特定物品添加到他们的购物车时，您会锁定物品分配到的所有类别的选定数量
• 当用户将特定SKU添加到其购物车时，您会锁定该用户的特定SKU的选定数量
• 您添加了不允许任何类别和任何特定SKU超过其单个当前库存的限制

3. 分发

最后一步是实际分配。在这里，你从最具体到最不具体，即你从列出特定的SKU开始，然后是分配给大多数类别的文章，一直到"；我不在乎，我只想要一个苹果；客户。

---

我希望这对你有意义。我知道这是高度概念化的。但是，对于一个有点通用(显然)理论性的用例，很难给出具体的答案。

Answer 2

你的问题对我来说就像一个NP完全问题，尽管我无法证明^^

下面的代码只是一个概念验证，供您进行测试。

编辑：代码所做的是：给定"抽象项目"；在客户的购物车中；真实物品"；篮子中的股票；真实物品"；(让我们把这些组合称为"虚拟购物车")，既满足客户的购物车又满足购物篮中的库存。然后，对于每个"；虚拟购物车"；，模拟篮子里剩下的存货。最后，使每个"；虚拟篮子"；。

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

您的测试用例很小，因此计算很快：

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}>}

更新：以下代码保留了之前计算的"；虚拟篮子"；用于加速向购物车添加新物品。

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

你可以这样使用它：

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}>}

可能的改进：通过添加"；数量；对于篮子里的物品，你应该能够减少"篮子"的大小和数量；虚拟篮子"；。此外，如果价格是一个强制性字段(这是有意义的)，那么你可以"；有点"；按价格划分问题，使代码更快。

备注：另一种表达你想要的东西的方式是：对于每个属性中的每个可能的选择(例如，:size是一个属性，它的一个可能的选择是'S')，购物车中是否存在不会耗尽它的物品组合？除非有一个数学公式可以快速找到它，否则你几乎必须遍历所有可能的组合，才能对这个问题做出"否"的回答。。。

在某种程度上，我的第二个建议让人记住了有效的"；虚拟篮子"；上一次迭代的是解决这个问题的明智方法。

Answer 3

我捅了一刀，请看下面。

您可以通过将下面的整个代码复制到一个文件(比如test.rb)中，然后从命令行(即ruby test.rb)运行它来处理代码

该设计基于这样的想法；最大化保留在篮子中的选项"；在逻辑上等同于"；按照最常见到最不常见的顺序从篮子中移除选项"；。

# 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