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.

If you want to learn, then try to translate one of the implementations you found to Delphi. It should not be too hard. If you have specific problems, ask specific questions. — jpfollenius, Dec 04 '13 at 07:45
The C++ code is simple. What don't you understand? What have you tried so far. Please show your workings. Your motivation is learning, so let's do some. Writing a Delphi translation for you won't help. — David Heffernan, Dec 04 '13 at 07:47

score 4 · Answer 1 · edited Dec 04 '13 at 08:21

4

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.

edited Dec 04 '13 at 08:21

David Heffernan

601,492
42
1,072
1,490

answered Dec 04 '13 at 08:11

Jerry Coffin

476,176
80
629
1,111

Thanks Jerry and it is interesting approach. Would this work for an arbitrary character set with arbitrary number of desired length of the generated set? – Merlin W. Dec 07 '13 at 22:19
This works for arbitrary character set. For arbitrary length you'd need arbitrary precision integer arithmetic. But you can't run a for loop over a 64 bit integer in meaningful time anyway, so that doesn't matter. – David Heffernan Dec 07 '13 at 22:27
@DavidHeffernan for length of character set of 4 say `ABCD` and desired length of `2` it should be trivial generated set. Even with character set of `26` and desired length of `4` it shouldn't be a long process to generate `4^26`, likely many hours but still can be done within our lifetime. – Merlin W. Dec 07 '13 at 22:37
`4^26` is `2^27`. Try and see how long `2^64` takes. – David Heffernan Dec 07 '13 at 22:40
4^26 (or 2^27) won't take very long at all. For reference, counting through 2^32 only takes a few seconds. 2^64, however, takes about 4 billion *times* as long as 2^32. – Jerry Coffin Dec 07 '13 at 22:50
@JerryCoffin how is this part `ret.push_back` translated to Delphi? – Merlin W. Dec 07 '13 at 23:00
@MerlinW.: It's just concatenating a character to the string. – Jerry Coffin Dec 07 '13 at 23:01
In Delphi you would probably allocate the string up front to avoid repeated heap allocations. But that's optimisation detail. Semantically it comes to the same thing. – David Heffernan Dec 07 '13 at 23:12
So far I was unable to do this but I like your idea though – Merlin W. Dec 09 '13 at 01:19

KoenKawa · Accepted Answer · 2013-12-10T07:07:39.637

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

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.

This is perfect as it uses a concept like a digital counter. I like it better than recursion and IMHO more elegant. — Merlin W., Dec 10 '13 at 02:23

score 0 · Answer 3 · edited May 23 '17 at 12:08

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.

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

3 Answers3