Delphi中嵌套for循环的替代方法

Question

我遇到了以下概念上非常简单的问题，想要编写代码来解决它，但是我很困难。假设我们有两行长度相等的k个元素。每一行的每个单元格都可以是0或1。

例如，考虑以下行对，其中k = 5：01011、00110

现在，如果两行可以自由交换每个单元格的值，则会产生2^5种可能的行对组合（其中一些可能不唯一）。例如，我们可以从上述数据中得到00010、01111作为一个可能的行对。我想用Delphi编写代码列出所有可能的行对。使用一组嵌套的for循环很容易做到这一点。然而，如果只有在运行时才知道k的值，我不知道应该使用多少索引变量来采用这种方法。我无法看出case语句将如何有所帮助，因为我不知道k的值。

我希望有一种替代嵌套for循环的方法，但是任何想法都将不胜感激。谢谢。

- Serge

---

我没明白你想做什么 - 一些代码会帮助我理解。 - Jerry Dodge

你能展示一下针对“固定”的 k 的代码吗？ - lurker

这听起来像是一个计算机科学问题。我猜这两行是“测试集”的一部分，对吗？ - Cosmin Prund

对不起 - 我有点过早了。让我再多做一些工作，然后再发布问题。谢谢你的时间。 - Serge

@user1505202没有回答你所问的问题吗？ - David Heffernan

Answer 1

给定两个长度为k的向量A和B，我们可以通过有选择地从A或B中选择元素来生成新的向量对A1和B1。让我们的选择从A或B中选择由一个长度为k的位向量S决定。对于i在[0..k)范围内，当Si为0时，将Ai存储在A1i中，并将Bi存储在B1i中。如果Si为1，则反之亦然。

我们可以使用Delphi中的一个函数定义如下：

procedure GeneratePair(const A, B: string; S: Cardinal; out A1, B1: string);
var
  k: Cardinal;
  i: Cardinal;
begin
  Assert(Length(A) = Length(B));
  k := Length(A);
  Assert(k <= 32);

  SetLength(A1, k);
  SetLength(B1, k);
  for i := 1 to k do
    if (S and (1 shl Pred(i))) = 0 then begin
      A1[i] := A[i];
      B1[i] := B[i];
    end else begin
      A1[i] := B[i];
      B1[i] := A[i];
    end;
end;

如果我们从0到2的k次幂-1使用二进制计数，那么将给我们一个位向量序列，表示在A和B之间交换或不交换字符的所有可能组合。

我们可以编写一个循环并使用上述函数生成所有2的k次幂个组合：

A := '01011';
B := '00110';
for S := 0 to Pred(Round(IntPower(2, Length(A)))) do begin
  GeneratePair(A, B, S, A1, B1);
  writeln(A1, ', ', B1);
end;

这个函数有效地使用了一组嵌套循环。外层循环是从0到31的。内部循环是函数内的循环，从1到k。正如您所看到的，我们不需要事先知道k的值。

- Rob Kennedy

Answer 2

现在，感谢 Rob 的帮助，我理解了这个问题，我提供这个递归解决方案：

{$APPTYPE CONSOLE}

procedure Swap(var A, B: Char);
var
  temp: Char;
begin
  temp := A;
  A := B;
  B := temp;
end;

procedure Generate(const A, B: string; Index: Integer);
var
  A1, B1: string;
begin
  Assert(Length(A)=Length(B));
  inc(Index);
  if Index>Length(A) then // termination
    Writeln(A, ', ', B)
  else
  begin // recurse
    // no swap
    Generate(A, B, Index);

    //swap
    A1 := A;
    B1 := B;
    Swap(A1[Index], B1[Index]);
    Generate(A1, B1, Index);
  end;
end;

begin
  Generate('01011', '00110', 0);
  Readln;
end.

- David Heffernan