3

我遇到了以下（概念上非常简单）的问题，并想编写代码来做到这一点，但我很挣扎。假设我们有两行等长，k。每行的每个单元格可以是 0 或 1。

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

现在，如果两行可以在每个单元格处自由交换值，则行对的可能组合有 2^5 种（其中一些可能不是唯一的）。例如，我们可以将 00010、01111 作为上述数据中的一个可能的行对。我想在 Delphi 中编写代码来列出所有可能的行对。使用一组嵌套的 for 循环很容易做到这一点。但是，如果 k 的值仅在运行时已知，我不确定如何使用这种方法，因为我不知道需要多少索引变量。我也看不出 case 语句有什么帮助，因为我不知道 k 的值。

我希望有嵌套 for 循环的替代方案，但任何想法都会受到赞赏。谢谢。

4

2 回答 2

4

给定两个长度为k的向量A和B ，我们可以通过选择性地从A或B中选择元素来生成一对新的向量A1和B1。让我们从A或B中选择的决定由同样长度为k的位向量S决定。对于[0.. k ) 中的i，当S i为 0 时，将A i存储在A1 i中，将B i存储在B1 i中。如果S我为 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的值。

于 2013-09-06T19:29:02.593 回答
1

现在，多亏了 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.
于 2013-09-06T20:47:40.947 回答