algorithm - 根据任意字符串和长度生成字符组合——类似于排列

Question

这个问题以前用其他语言问过，但在搜索SO后没有用delphi问过。看到这个问题:How to Generate Permutations With Repeated Characters这个问题:Generate all combinations of arbitrary alphabet up to arbitrary length还有这个:How to generate combination of fix length strings using a set of characters?所以这个问题并不新鲜，但我很难将其中任何一个翻译成德尔福。

我想做的是生成包含重复字符的组合，例如:如果我们有一串字符(由用户指定):ABC 并且我们想要生成三个字符的长度(也是由用户指定的长度)，我会得到:AAA AAB AAC ABA ABB ABC ACA ACB ACC BAA BAB BAC 等...

这段代码似乎是这样做的，但在 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;
    }
  }
}

这似乎也是这样做的:

    #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;
   }

最接近我在 delphi 中想要的是在这里找到的，但不允许 AAA 例如: http://www.swissdelphicenter.ch/torry/showcode.php?id=1032

不，如果您在猜测，这不是家庭作业。没有其他动机，只是学习。

编辑 3:从问题中删除了所有不相关的代码，以便其他人更容易阅读并获得以下答案。在答案下查找 2 种不同的方法来实现此目的:一种使用递归，另一种使用计数器函数。

Answer 1

您展示的示例使这比必要的复杂得多，至少在我看来是这样。

您真正看到的是一个以 3 为基数的 3 位数字。您可以从 0 数到 3³ = 27，然后将每个数字转换为基数 3(使用 'A'、'B' 和 'C' 作为您的数字而不是 '0'、'1 ' 和 '2')。

在 C++ 中，转换看起来像这样:

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());
}

有了适当的转换，生成所有组合变得非常简单:

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

我认为将其转换为 Delphi 应该几乎不存在纯粹的机械问题——分配从 = 更改为 :=，% 变为 mod，整数除法变为 div，for 循环变为类似 for i = 0 to 27 do ， 等等。最乏味(但最终非常简单)的部分可能是处理这样一个事实，即在 C++ 中，char 只是一个小整数类型，您可以在其上进行普通整数数学运算。至少如果没有记错的话，在 Pascal(或像 Delphi 这样的衍生产品)中，你需要 ord 将字符转换为序数，并需要 chr 从序数转换回来性格。所以 'A' + in % base; 最终会变成更像 chr(ord('A') + in mod base);

不过正如我所说，似乎几乎整个翻译可以/应该几乎完全机械化，不需要对基本算法的工作方式或类似的方式进行真正的更改。