Alternative to nested for-loop in Delphi

Question

I came across the following (conceptually very simple) problem, and want to write code to do it, but am struggling. Let's say we have two rows of equal length, k. Each cell of each row can be either a 0 or a 1.

For e.g., consider the following row-pair, with k = 5: 01011, 00110

Now if the two rows could freely exchange values at each cell, there would be 2^5 possible combinations of row-pairs (some of which may not be unique). For instance, we could have 00010, 01111 as one possible row-pair from the above data. I want to write code in Delphi to list all the possible row-pairs. This is easy enough to do with a set of nested for-loops. However, if the value of k is known only at run-time, I'm not sure how I can use this approach for I don't know how many index variables I would need. I can't see how case statements will help either because I don't know the value of k.

I am hoping that there is an alternative to a nested for-loop, but any thoughts would be appreciated. Thanks.

I'm not understanding what you're looking to do - some code would help me understand — Jerry Dodge
– Jerry Dodge, Commented Sep 6, 2013 at 17:49
Not knowing k until runtime is not an issue at all, as long as the rows are of equal length. Can you post what you've tried so far that you're having difficulty with? (Questions asking for code should at least include some sort of effort on your part to find a solution.) — Ken White
– Ken White, Commented Sep 6, 2013 at 17:56
This sounds like a Computer Science problem. I assume the two rows are part of the "test set", aren't they. — Cosmin Prund
– Cosmin Prund, Commented Sep 6, 2013 at 18:56
I'm sorry - it was a bit premature of me. Let me work on this a bit more and post the question again. Thank you for your time. — Serge
– Serge, Commented Sep 6, 2013 at 22:13

David Heffernan · Accepted Answer · 2013-09-06 20:34:42Z

Given two vectors A and B of length k, we can generate a new pair of vectors A1 and B1 by selectively choosing elements from A or B. Let our decision to choose from A or B be dictated by a bit vector S, also of length k. For i in [0..k), when S_i is 0, store A_i in A1_i and B_i in B1_i. If S_i is 1, then vice versa.

We can define that in Delphi with a function like this:

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;

If we count in binary from 0 to 2^k−1, that will give us a sequence of bit vectors representing all the possible combinations of exchanging or not-exchanging characters between A and B.

We can write a loop and use the above function to generate all 2^k combinations:

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;

That effectively uses one set of nested loops. The outer loop is the one from 0 to 31. The inner loop is the one inside the function from 1 to k. As you can see, we don't need to know the value of k in advance.

David Heffernan · Accepted Answer · 2013-09-06 20:47:40Z

1

Now that, thanks to Rob, I understand the problem, I offer this recursive solution:

{$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.

answered Sep 6, 2013 at 20:47

David Heffernan

616k46 gold badges1.1k silver badges1.5k bronze badges

Collectives™ on Stack Overflow

Alternative to nested for-loop in Delphi

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related