我正在寻找一个好的算法/数据结构来做以下事情:
循环所有项目组合:
例如,对于A, B, C, D, E
:
AB, AC, AD, AE
BC, BD, BE
CD, CE
DE
(对称,即AB
和BA
相等)
计算组合很容易,但是在循环过程中会删除一些项,所以如果处理AC
的结果是删除了C
项,那么现在的问题是有效地删除所有其他涉及C
的组合(尚未处理),在本例中是BC
,CD
和CE
。
除了创建一个矩阵(这应该很容易使用,但在这种情况下需要5x 5 =25而不是只有10个实际组合)之外,什么是一个好的数据结构/算法解决方案?
3条答案
按热度按时间gtlvzcf81#
从https://wiki.freepascal.org/for-in_loop判断,您在 Delphi 中有枚举器的概念,尽管我不确定它有多灵活。
我建议容器将其元素放在一个双向链表中。这样可以很容易地删除列表中间的元素。它还保留了一个已删除元素的列表,其中包含指向下一个内容的指针。子集枚举器保存的信息包括:
现在获取下一个子集的问题是:
这种方法的好处是,如果删除了一个元素,您甚至可以停止尝试构造包含它的子集。
55ooxyrt2#
我发现用代码思考更容易。算法应该很容易扩展到3个或更多元素的组合,扩展到64个以上对别人来说是个问题。
因此,正在处理的每个数据元素都有一个位标识符,
eliminate
中的位0到位63,初始化为全1位。然后它是一个下一个
for
s的序列,从前一个值的后继值开始,到(end-limit-depth)结束。将有效标志加在一起,如果与eliminate
进行AND运算时结果发生变化,则包含了一个被删除的元素,因此我们可以跳过处理。eliminate := eliminate and not(flags[p_2]);
可能会更好地代替eliminate := eliminate xor flags[p_2];
,以防处理过程多次尝试消除相同的元素。q43xntqr3#
somewhat inspired by the comment from Brian, i'm considering the following implementation:
add an array
Deleted
corresponding to the items, i.e.00000
forABCDE
(choosing Process rather than Deleted may have been more intuitive, but arrays are 0 by default, so this way saves looping over the array and initializing it to 1)so after removing C the array is
00100
the logic is to perform processing only if both items are not Deleted
this has the benefits of the actual removal of C not affecting any further processing and having a simple check on whether to perform processing
here is some code excerpt: