过滤列表受限制

Question

描述

输入List<Item>按分数排序,Item如下所示:

class Item {
    double score;
    String category; 
    String author;    
    String poi;   
}

现在我需要在这些限制下从数组中选择10个得分最高的元素:

• 他们应该有所不同 poi
• 他们应该有所不同 author
• 最多有3个相同的项目category.并且来自同一子序列的任何子序列的长度category不应超过2.

如果没有满足上述规则的子序列,只需返回前10个元素.

我试过了什么

现在,我直接迭代List,并用三个HashMap<String, Integer>来存储每个的外观cagetory/poi/author.我List<Item> selected用来存储结果.

• 如果已经有一个具有此元素的选定元素,poi则将丢弃新元素.
• 如果已经有一个具有此元素的选定元素,author则将丢弃新元素.
• 如果已经有三个具有此元素的选定元素,category则将丢弃新元素.
• 如果已经在尾部两个元素selected具有此category,那么新元素将被丢弃.

问题

它在输入很大时有效,但是当输入相对较小时,它不起作用.例如,输入时

1. 第1项(A类,作者1)
2. 第2项(A类,作者2)
3. 第3项(A类,作者3)
4. 第4项(B类,作者2)
5. 第5项(C类,作者5)
6. 第6项(D类,作者6)
7. 第7项(E类,作者7)
8. 第8项(F类,作者8)
9. 第9项(G类,作者9)
10. Item10(H类,作者10)
11. 第11项(第I类,作者11)

那我的解决方案就是

• Item3丢弃,因为它具有相同category的Item1和Item2
• Item4丢弃,因为它有相同author的Item2
• 剩下的9个其他元素.

而这并不满足select top 10 elements.正确的解决方案是丢弃Item2,只剩下10个元素.

题

我认为我的解决方案只是方向错误.所以我正在寻找其他解决方案来解决这个问题.任何解决方案产生所需的输出表示赞赏.

Answer 1

您使用的原始算法将始终倾向于最小化结果的数量,因为在项目之间的任何互斥选择中,得分最高的项目获胜.这样算法就像筛子一样运行,消除了许多低分项.

为了支持从长度为Y的原始项集(在您的示例中为11)中选择至少大小为X的集合(在这种情况下为10),您将需要收集决策集列表,而不是仅通过分数来消除项目.决策集(m,n)是一组m个项目,您必须从中选择保留n个项目并消除其余项目.由于系统中的大多数规则都是属性x的单项,因此列表中的大多数决策集都将被设置(m,1) - 选择m项中的1项,消除其余项.

完整项目集的第一次传递将填充决策集列表,第二次传递将遍历该列表,并从每个决策集中选择要从原始集中消除的项目.一旦做出决定并且从原始集合中删除项目,则从列表中移除决策集(已解决).清除决策集列表后,您的原始集合是合法的.

目标是在大多数YX抵消中清除决策集清单.由于项目可以出现在多个决策集中,您还可以为每个项目添加" 生存分数 ".存活分数表示如果保留此项目则必须消除的最大项目数.通过遍历每个决策集(m,n)并将包含mn的每个项目添加到其累积分数来计算每个项目.

让我们看看你的例子,并构建它的决策集:

• 第1项(A类,作者1)
• 第2项(A类,作者2)
• 第3项(A类,作者3)
• 第4项(B类,作者2)
• 第5项(C类,作者5)
• 第6项(D类,作者6)
• 第7项(E类,作者7)
• 第8项(F类,作者8)
• 第9项(G类,作者9)
• Item10(H类,作者10)
• 第11项(第I类,作者11)

我们编译的决策集是(注意括号中的生存分数):

• 作者决定集(2,1)= {项目2(2),项目4(1)}
• 类别决定集(3,2)= {项目1(1),项目2(2),项目3(1)}

我们的目标是最多解决1个决策集清单.您可以看到所有项目的生存分数为1(意味着保留它们将导致最多1个其他项目被淘汰),除了项目2的生存分数为2(保持最多2个项目).我们买不起2件物品,因此无论其得分如何,我们都无法保留第2项.消除它将解决两个决策集,是唯一的选择.

更通用的算法可能更复杂:在每次迭代中,您都会消除您无法承受的生存分数的项目,如果您没有接近该限制,请使用分数和生存分数的组合来决定哪一项必须去.