产生任意字母可达任意长度的所有组合 [英] Generate all combinations of arbitrary alphabet up to arbitrary length

问题描述

说我有一个任意大小持有单个字符数组。我想计算这些字符的所有可能组合到任意长度。

Say I have an array of arbitrary size holding single characters. I want to compute all possible combinations of those characters up to an arbitrary length.

因此​​，可以说我的数组为[1，2，3]。用户指定的长度是2。然后可能的组合是[11，22，33，12，13，23，21，31，32]。

So lets say my array is [1, 2, 3]. The user-specified length is 2. Then the possible combinations are [11, 22, 33, 12, 13, 23, 21, 31, 32].

我有真正的麻烦找到一个合适的算法，允许任意长度，而不是仅仅的进行置换阵。呵呵，虽然速度不是绝对关键的，它应该是相当快的了。

I'm having real trouble finding a suitable algorithm that allows arbitrary lengths and not just permutates the array. Oh and while speed is not absolutely critical, it should be reasonably fast too.

推荐答案

只是做一个有进位加。

假设你的数组包含4个符号，你想一个长度为3的。

Say your array contained 4 symbols and you want ones of length 3.

开始用000（即你的字每一个符号=字母[0]）

Start with 000 (i.e. each symbol on your word = alphabet[0])

然后添加了：

000 001 002 003 010 011 ......

000 001 002 003 010 011 ...

该算法（考虑到这些指数）只是以增加最低的数字。如果达到在字母表的符号的数目，增加了previous数（以下相同的规则），并设置当前为0

The algorithm (given these indices) is just to increase the lowest number. If it reaches the number of symbols in your alphabet, increase the previous number (following the same rule) and set the current to 0.

C ++ code：

C++ code:

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

code是未经测试，但应该可以解决问题。

Code is untested, but should do the trick.

这篇关于产生任意字母可达任意长度的所有组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！