Альтернатива вложенному for-loop в Delphi

Question

Я столкнулся с следующей (концептуально очень простой) проблемой и хочу написать код, чтобы сделать это, но боюсь. Скажем, у нас есть две строки равной длины, k. Каждая ячейка каждой строки может быть либо 0 или 1.

Для например, рассмотрим следующую строку-пару, с к = 5: 01011, 00110

Теперь, если две строки могли свободно обмениваться значения в в каждой ячейке было бы 2^5 возможных комбинаций пар строк (некоторые из которых могут быть не единственными). Например, мы могли бы иметь 00010, 01111 как одну возможную пару строк из приведенных выше данных. Я хочу написать код в Delphi, чтобы указать все возможные пары строк. Это достаточно легко сделать с набором вложенных циклов. Однако, если значение k известно только во время выполнения, я не уверен, как я могу использовать этот подход, потому что я не знаю, сколько индексов мне нужно. Я не могу понять, как справки case помогут либо потому, что я не знаю значения k.

Я надеюсь, что есть альтернатива вложенному циклу, но любые мысли будут оценены. Благодарю.

Answer 1

Указанные два вектора и B длины к, мы можем генерировать новую пару векторов А1 и В1 путем селективного выбирающих элементов из или B. Пусть наше решение выбрать из или B диктоваться битового вектора S, а также длины к. Для я в [0 .. к), когда S _я равно 0, магазин _я в A1 _я и В _я в В1 _я. Если S _i - 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 ^к:

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.

Answer 2

Теперь, благодаря Робу, я понимаю эту проблему, я предлагаю это рекурсивное решение:

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