循环遍历所有项目组合的算法，其中一些在过程中被删除？

Question

我正在为以下内容寻找一个好的算法/数据结构：

遍历所有项目组合：

例如，对于 A、B、C、D、E：

AB、AC、AD、AE

BC、BD、BE

CD, CE

德

（对称——即 AB 和 BA 是等价的）

计算组合很容易，但是在循环中一些项目被删除，所以如果作为处理 AC 项目 C 的结果被删除，现在的问题是有效地删除涉及 C 的所有其他组合（尚未处理），在这种情况下，BC、CD、CE

什么是好的数据结构/算法解决方案？除了创建矩阵（这应该很容易使用，但在这种情况下需要 5x5=25 而不是仅 10 个实际组合）

Answer 1

从 https://wiki.freepascal.org/for-in_loop 来看，您在 Delphi 中有枚举器的概念，但我不确定它有多灵活。

我建议容器在双向链表中包含其元素。这使得删除列表中间的元素变得容易。它还保留了一个已删除元素的列表，并带有指向下一个元素的指针。子集枚举器保存的信息包括：

the size of current subsets
an array of the current subset
pointer to the last deleted element

获取下一个子集现在是：

if more elements got deleted and one of my elements was one of them
    find the earliest one in my list deleted
    advance along the pointers in the deletion list until I find myself in the values list
    construct the next subset to return
    return it
else
    if the last element can be advanced:
        advance that, and return it
    else:
        find how many elements at the end can't be advanced
        if only some:
            advance the first that can
            construct the next subset to return
            return it
        else:
            try to increase the size of the subset and start from scratch

这种方法的好处是，如果一个元素被删除，你甚至会停止尝试构建包含它的子集。

Answer 2

我发现用代码思考更容易。该算法应该很容易扩展到 3 个或更多元素的组合，扩展到超过 64 个对其他人来说是个问题。

type
  sometype = integer;{for demo}

const
  first_element = 1;last_element = 5;
  flags : array [first_element..last_element] of int64 = (
          1 shl 0, 1 shl 1, 1 shl 2, 1 shl 3, 1 shl 4);
  human_interface : array [first_element..last_element] of char = (
          'A', 'B', 'C', 'D', 'E');

var
  eliminate : int64;
  select1,select2 : integer;

  data_array  : array [first_element..last_element] of sometype;

procedure process(p_1,p_2 : integer);
begin
  writeln('processing ',human_interface[p_1],human_interface[p_2]);
  {Here we process the data in 'data array'}
  (* When we process AC, we decide to eliminate C*)
  if (human_interface[p_1]='A') and (human_interface[p_2]='C') then
    eliminate := eliminate xor flags[p_2];
end;

begin
  eliminate := -1;
  for select1 := first_element to pred(last_element) do
    if (flags[select1]) and eliminate = flags[select1] then
      for select2 := succ(select1) to last_element do
        if (flags[select1] + flags[select2]) and eliminate = flags[select1] + flags[Select2] then
          process(select1,select2);
  writeln('done');readln;
end.

所以，每个被处理的数据元素都有一个位标识符，

eliminate

中的第0位到第63位，初始化为全1位。

然后是一系列下一个

for

s，从前一个值的后继开始，到（结束限制-深度）结束。将重要标志加在一起，如果与

eliminate

AND 运算时结果发生变化，则说明已经包含了一个被淘汰的元素，因此我们可以跳过处理。

可能

eliminate := eliminate and not(flags[p_2]);

会比

eliminate := eliminate xor flags[p_2];

更好，以防万一处理正在尝试多次消除相同的元素。

Answer 3

有点受到布赖恩评论的启发，我正在考虑以下实施：

添加一个数组

Deleted

对应于项目，即

00000

for

ABCDE

（选择 Process 而不是 Deleted 可能更直观，但默认情况下数组为 0，因此这种方式节省了遍历数组并初始化它到 1)

所以在删除 C 之后，数组是

00100

逻辑是只有两个item都没有被删除才进行处理

这样做的好处是实际移除 C 不会影响任何进一步的处理，并且可以简单地检查是否执行处理

这里是一些代码摘录：

var
  Deleted: TArray<Boolean>;

      SetLength(Deleted, Count);
      // loop over TList
      for I := 0 to Count - 2 do
        for J := I + 1 to Count - 1 do
          if not Deleted[I] and not Deleted[J] then
            // process
            // if deleting I:   Deleted[I] := True;
            // if deleting J:   Deleted[J] := True;
            // (the above are mutually exclusive)
            ;
      for I := High(Deleted) downto Low(Deleted) do
        if Deleted[I] then begin
          // delete
        end;