首页 文章

使用n个字符生成长度为l的所有可能字符串

提问于
浏览 次
-1

我希望在给定n个字符的情况下生成一定长度的所有可能字符串 .

因此，例如，如果l = 2且字符为[a，b，c]，则结果应为：'aa'，'ab'，'ac'，'ba'，'bb'，'bc'，'ca' ，'cb'和'cc' .

最初我使用递归算法完成了这项工作 . 但是，我得到了很多重复，而且非常耗时 .

此外，我想到了一个在基数n中“计数”的算法 . 因此，在上面的示例中，如果我替换a-> 0，b-> 1和c-> 2，我实际上计数到'cc' - >基数为3的22 . 但是，这也使我觉得效率低下 .

有什么建议 ？

string algorithm permutation

2 回答

  • 0

    是的，您可以使用除法表示“计数基数n” .

    替代实施 - 使用旧电动车轮等方法遍历所有 n^m 值：

    src = "abc";
n = len(src)
m = 2
l = [0]*m
i = 0
while i < m:
    print([src[x] for x in l])
    i = 0
    l[i] += 1
    while (i < m) and l[i] >= n:
        l[i] = 0
        i += 1
        if i < m:
            l[i] += 1

['a', 'a']
['b', 'a']
['c', 'a']
['a', 'b']
['b', 'b']
['c', 'b']
['a', 'c']
['b', 'c']
['c', 'c']
    回复于
  • 0

    您不必实施任何后续行动 . 您所要做的就是从上一个项目中获取下一个项目

    aa -> ab -> ac -> : we can't add 1 to c so why reset the last 'c' to 'a' 
                     but add 1 to previous 'a': 'ba'
                     now we keep on adding one to the last 'a':
 ba -> bb -> bc -> : again we reset 'c' to 'a' and increment previous b
 ca -> ...

    Code (C#) ;让我们概括解决方案（任何 alphabet 没必要 string ）

    // alphabet should contain distinct items
private static IEnumerable<T[]> Solution<T>(IEnumerable<T> alphabet, int length) {
  if (null == alphabet)
    throw new ArgumentNullException(nameof(alphabet));

  var chars = alphabet.Distinct().ToArray();

  if (length <= 0 || chars.Length <= 0)
    yield break;

  int[] result = new int[length];

  do {
    yield return result
      .Select(i => chars[i])
      .ToArray();

    for (int i = result.Length - 1; i >=0 ; --i)
      if (result[i] == chars.Length - 1) 
        result[i] = 0;
      else {
        result[i] += 1;
        break;
      }
  }
  while (!result.All(item => item == 0));
}

    Demo:

    // Or     var test = Solution("abc", 2);
var test = Solution(new char[] { 'a', 'b', 'c' }, 2);

var report = string.Join(", ", test
  .Select(item => string.Concat(item)));

    Outcome:

    aa, ab, ac, ba, bb, bc, ca, cb, cc
    回复于

相关问题