delphi 循环所有项目组合的算法,其中一些项目组合在处理过程中被删除?

2w3kk1z5  于 2023-04-20  发布在  其他
关注(0)|答案(3)|浏览(125)

我正在寻找一个好的算法/数据结构来做以下事情:
循环所有项目组合:
例如,对于A, B, C, D, E

AB, AC, AD, AE
BC, BD, BE
CD, CE
DE

(对称,即ABBA相等)
计算组合很容易,但是在循环过程中会删除一些项,所以如果处理AC的结果是删除了C项,那么现在的问题是有效地删除所有其他涉及C的组合(尚未处理),在本例中是BCCDCE
除了创建一个矩阵(这应该很容易使用,但在这种情况下需要5x 5 =25而不是只有10个实际组合)之外,什么是一个好的数据结构/算法解决方案?

gtlvzcf8

gtlvzcf81#

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

这种方法的好处是,如果删除了一个元素,您甚至可以停止尝试构造包含它的子集。

55ooxyrt

55ooxyrt2#

我发现用代码思考更容易。算法应该很容易扩展到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的序列,从前一个值的后继值开始,到(end-limit-depth)结束。将有效标志加在一起,如果与eliminate进行AND运算时结果发生变化,则包含了一个被删除的元素,因此我们可以跳过处理。
eliminate := eliminate and not(flags[p_2]);可能会更好地代替eliminate := eliminate xor flags[p_2];,以防处理过程多次尝试消除相同的元素。

q43xntqr

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 for ABCDE (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:

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;

相关问题