Generate character combinations based on arbitrary string and length - similar to permutations

Question

This question was asked before in other languages but not delphi after searching SO. see this question:How to Generate Permutations With Repeated Characters and this question: Generate all combinations of arbitrary alphabet up to arbitrary length and this one: How to generate combination of fix length strings using a set of characters? so the question is not new but I am having a hard time translating any of this to delphi.

What I'm trying to do is generate combinations that does include repeats of characters such as this: if we have a string of characters (specified by user): ABC and we want to generate length of three characters (also length specified by user) I would get: AAA AAB AAC ABA ABB ABC ACA ACB ACC BAA BAB BAC etc...

This code seems to do this but in C++:

int N_LETTERS = 4;
char alphabet[] = {'a', 'b', 'c', 'd'};

std::vector<std::string> get_all_words(int length)
{
  std::vector<int> index(length, 0);
  std::vector<std::string> words;

  while(true)
  {
    std::string word(length);
    for (int i = 0; i < length; ++i)
      word[i] = alphabet[index[i]];
    words.push_back(word);

for (int i = length-1; ; --i)
{ 
  if (i < 0) return words;
  index[i]++;
  if (index[i] == N_LETTERS)
    index[i] = 0;
  else
    break;
    }
  }
}

This also seems to do this:

    #include <iostream>
    #include <string>
    #include <math.h>
    #include <stdio.h>
    #include <stdlib.h>
    using namespace std;

void displayPermutation(string permutation[], int length){
    int i;
    for (i=0;i<length;i++){
        cout<<permutation[i];
    }
    cout << endl;
}

void getPermutations(string operatorBank[], int operatorCount, 
        string permutation[],int permutationLength, int curIndex){
    int i;
    //stop recursion condition
    if(curIndex == permutationLength){
        displayPermutation(permutation,permutationLength);
    }
    else{
        for(i = 0; i < operatorCount; i++){
            permutation[curIndex] = operatorBank[i];
            getPermutations(operatorBank,operatorCount,permutation,
                permutationLength,curIndex+1);
        }
    }
}

int main ()
   {
       int operatorCount = 4;
       int permutationLength = 3;
       string operatorBank[] = {"+","-","*","/"};
       string permutation[] = {"","","",""}; //empty string
       int curIndex = 0;
       getPermutations(operatorBank,operatorCount,permutation,
                               permutationLength,curIndex);
   return 0;
   }

closest to what I want in delphi is found here but does not allow AAA for example: http://www.swissdelphicenter.ch/torry/showcode.php?id=1032

And no this is not homework in case you are guessing. No other motive but just learning.

EDIT3: Removed all irrelevant code from question to make it easier for other people to read it and get to the answers below. Look under answers for 2 different methods to accomplish this: one using recursion and the other by using a counter function.

Answer 1

Not exactly following your sequence of output, but following a sequence similar to the way binary numbers add up...

0001 
0010 
0011 
0100 
...

The idea is simple: loop index values in an array indicating which character to use at the respective position to compose the output combination string. No recursion required.

NextCombination updates the index array so the next combination is defined, it returns true as long as not all combinations are formed. False when back to all 0's.

DefineCombinations accepts a string with chars to use (for example 'ABC') and a size of the combined string (eg: 3): this adds the following sequence to a memo:

AAA, AAB, AAC, ABA, ABB, ABC, ACA, ACB, ACC, BAA, BAB, BAC, BBA, BBB, BBC, BCA, BCB, BCC, CAA, CAB, CAC, CBA, CBB, CBC, CCA, CCB, CCC

Adapt as you wish.

function TForm1.NextCombination(var aIndices: array of Integer; const MaxValue: Integer): Boolean;

var Index : Integer;

begin
  Result:=False;
  Index:=High(aIndices);

  while not(Result) and (Index >= Low(aIndices)) do
  begin
    if (aIndices[Index] < MaxValue) then
    begin
      { inc current index }
      aIndices[Index]:=aIndices[Index] + 1;
      Result:=True;
    end
    else
    begin
      { reset current index, process next }
      aIndices[Index]:=0;
      Dec(Index);
    end;
  end;
end;

procedure TForm1.DefineCombinations(const Chars: String; const Size: Integer);

var aIndices     : array of Integer;

    Index        : Integer;
    sData        : String;

begin
     try
        SetLength(sData, Size);
        SetLength(aIndices, Size);

        repeat
           for Index:=Low(aIndices) to High(aIndices) do
             sData[Index + 1]:=Chars[aIndices[Index] + 1];

           memo1.Lines.Add(sData);
        until not(NextCombination(aIndices, Length(Chars) - 1));

     finally
        SetLength(aIndices, 0);
        SetLength(sData, 0);
     end;
end;

Let me know if I missed something from the original question.

Answer 2

Here it is done with Recursion (Credit to this post's accepted answer:How to Generate Permutations With Repeated Characters

program Combinations;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils;

procedure displayPermutation(const permutation : array of char; ilength: integer);
var
  i: integer;
begin
  for i := 0 to ilength - 1 do
    begin
      if i mod iLength = 0 then
        writeln('')
      else write(permutation[i]);
    end;
end;

procedure getPermutations(const operatorBank: array of char; operatorCount: integer;
            permutation: array of char; permutationLength, curIndex: integer);
var
  i : integer;
begin
  //stop recursion condition
  if(curIndex = permutationLength)then
    displayPermutation(permutation, permutationLength)
  else
    for i := 0 to operatorCount - 1 do
      begin
        permutation[curIndex] := operatorBank[i];
        getPermutations(operatorBank,operatorCount,permutation,
                     permutationLength,curIndex+1);
      end;
 end;

var
  operatorBank,permutation : array of char;
  i, permutationLength, curIndex, operatorCount: integer;
  Q, S : String;
begin
  try

    Q  := ' ';
    S  := ' ';
    while (Q <> '') and (S <> '') do
      begin
        Writeln('');
        Write('P(N,R)  N=? : ');
        ReadLn(Q);

        operatorCount := Length(Q);
        setLength(operatorBank,operatorCount);


        for i  := 0 to operatorCount - 1 do
          operatorBank[i] := Q[i+1];

        Write('P(N,R)  R=? : ');
        ReadLn(S);
        if S <> '' then permutationLength := StrToInt(S) + 1;

        SetLength(permutation,operatorCount);
        curIndex := 0;
        Writeln('');

        getPermutations(operatorBank, operatorCount, permutation,
                      permutationLength, curIndex );
      end;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;

end.

Answer 3

The examples you show make this considerably more complex than necessary, at least IMO.

What you're really looking at is a 3 digit, base 3 number. You can just count from 0 to 3³ = 27, then convert each number to base 3 (using 'A', 'B' and 'C' as your digits instead of '0', '1' and '2').

In C++, the conversion could look something like this:

std::string cvt(int in) {
    static const int base = 3;
    static const int digits = 3;
    std::string ret;

    for (int i = 0; i<digits; i++) {
        ret.push_back('A' + in % base);
        in /= base;
    }
    return std::string(ret.rbegin(), ret.rend());
}

With the conversion in place, producing all the combinations becomes utterly trivial:

for (int i = 0; i < 27; i++)
    std::cout << cvt(i) << "\t";

I believe converting that to Delphi should be barely short of purely mechanical -- assignments change from = to :=, % becomes mod, the integer division changes to div, the for loop changes to something like for i = 0 to 27 do, and so on. The most tedious (but ultimately quite simple) part will probably be dealing with the fact that in C++, char is simply a small integer type, on which you can do normal integer math. At least if memory serves, in Pascal (or a derivative like Delphi) you'll need ord to convert from a character to an ordinal, and chr to convert back from ordinal to character. So the 'A' + in % base; will end up something more like chr(ord('A') + in mod base);

Like I said though, it seems like nearly the entire translation could/should end up almost completely mechanical, with no requirement for real changes in how the basic algorithms work, or anything like that.