给定一个字符串的所有可能组合

Question

给定一个字符串的所有可能组合

3

我需要找到给定字符串的所有可能组合，从最小长度到最大长度。

interface allCombos(string: String, min: Number, max:Number): Array {}

如果我的输入字符串为'abcde'，并且我的最小长度为3，则期望的结果是：
对于长度为3：

[‘abc’, ‘abd’, ‘abe’, ‘acd’, ..., ‘bcd’, ‘bce’, ..., ‘eda’, ...]

连接长度为4：

[‘abcd’, ‘abdc’, ‘acdb’, ‘acbd’, …etc]

将所有长度最长为max参数的可能组合连接起来。max参数不应该高于输入单词长度。

我开始认为所有可能的组合将是∑(3! + 4! + … + n!)。但后来我发现我错了，因为对于每个长度子集，整个单词有许多组合（例如6个字母字符串的3个长度组合）。

社区能帮我解决这个问题吗？

解决方案可以是JavaScript、Python甚至伪代码。

编辑

出于知识的缘故。有人能回答我这种情况下描述结果大小的公式吗？我知道这不是∑(3! + 4! + … + n!)。

- weisk

1

如果字符串有重复的字母，每个字母是否应该被独立考虑？（如果你有“bb”，你会得到“b”还是“bb”或者[“bb”，“bb”]？） - user70585

1

这个问题与Python还是JavaScript相关？ - guest271314

嗯，我认为是这样的，因为我更愿意用那些语言编写代码解决问题。 - weisk

John Doe，是的，即使有重复项，我也想计算它们。 - weisk

“那些语言”是什么意思？问题的主题是排列，而不是组合，对吗？ - guest271314

如果我在某些方面有错误，请指出来，因为我对理论有点生疏。 - weisk

4个回答

1

我很高兴向您介绍神奇的Python标准库itertools！您需要使用组合函数。这个库的优点是它几乎可以解决所有组合循环问题。

 import itertools

 min_length = 2
 max_length = 5

 s = 'ABCDEF'
 for i in range(min_length, max_length):
     print('length', i, 'cominations')
     print([_ for _ in itertools.combinations(s, i)])

- costrouc

1

其他人给你展示了一些有关组合/排列的好选项，但我认为你期望得到的完整输出结果是这样的：

from itertools import combinations

def allCombos(str, min_length, max_length):
    str_combinations = []
    for length in range(min_length, max_length):
        combinations = [''.join(c) for c in combinations(str, length)]
        str_combinations.append(combinations)
    return str_combinations

- jack6e

是的！我认为你很接近了，但是出现了以下错误：UnboundLocalError: local variable 'combinations' referenced before assignment。 - weisk

哎呀，我导入了一个选项却使用了另一个，哈哈。当时我快速离开工作时匆忙写的，等会儿我会修改的。 - jack6e

1

[编辑]: 仅供知识参考。有人能回答我这种情况下描述结果大小的公式吗？我知道它不是∑（3！+4！+...+n！）。

以下是三种数学方法，使用JavaScript提供相同的最终结果。有关该过程的进一步说明，请参见

主题内其他感兴趣的内容

const n = 4;

{
  console.log("multiplication in loop:\n");
  let l = 1,
    k;

  for (let i = k = n; l < i; k *= l++);

  console.log({
    [`${n}!`]: k
  });
}

{
  console.log("single multiplication 4 * 3 * 2 * 1:\n");
  console.log({
    [`${n}!`]: 4 * 3 * 2 * 1
  });

}

{
  console.log("multiplication in steps:\n");
  
  let curr = n;
  
  let acc = {};
  
  acc[`${curr} * ${curr - 1}`] = curr * --curr;
  
  console.log(acc);
  
  acc[`${Object.keys(acc).pop()} * ${--curr}`] = curr * +acc[Object.keys(acc).pop()];
  
  console.log(acc);
  
  acc[`${Object.keys(acc).pop()} * ${--curr}`] = curr * +acc[Object.keys(acc).pop()];
  
  console.log(acc);

}

- guest271314

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cleb · Accepted Answer

你可以使用 itertools.combinations 来实现此功能：

from itertools import combinations

["".join(li) for li in combinations('abcde', 3)]

这将提供：

['abc', 'abd', 'abe', 'acd', 'ace', 'ade', 'bcd', 'bce', 'bde', 'cde']

简要说明：

list(combinations('abcde', 3))

将会给予

[('a', 'b', 'c'),
 ('a', 'b', 'd'),
 ('a', 'b', 'e'),
 ('a', 'c', 'd'),
 ('a', 'c', 'e'),
 ('a', 'd', 'e'),
 ('b', 'c', 'd'),
 ('b', 'c', 'e'),
 ('b', 'd', 'e'),
 ('c', 'd', 'e')]

所有三个字母的组合，您可以将单独元组连接在列表推导式中。

当然，如果您愿意，也可以轻松地将其放入循环中：

min_length = 3
max_length = 5

res = {str(i): ["".join(li) for li in combinations('abcde', i)] for i in range(min_length, max_length + 1)}

这会给予

{'3': ['abc', 'abd', 'abe', 'acd', 'ace', 'ade', 'bcd', 'bce', 'bde', 'cde'],
 '4': ['abcd', 'abce', 'abde', 'acde', 'bcde'],
 '5': ['abcde']}

如果你想将它们放在一个列表中：

import numpy as np
final_list = np.concatenate(res.values())

这会产生

array(['abc', 'abd', 'abe', 'acd', 'ace', 'ade', 'bcd', 'bce', 'bde',
       'cde', 'abcde', 'abcd', 'abce', 'abde', 'acde', 'bcde'],
      dtype='|S5')