0

我有一个字符串和一些空格，例如字符串是“accttgagattcagt”，我有 10 个空格要插入。

您如何遍历该字符串和空格的所有组合？字符串中的字母不能重新排序，必须插入所有空格。

你怎么能计算重排的数量（不迭代它们）？

什么是合适的词？排列、组合还是其他？

（我将其想象为 1 和 0 的字符串，其中 1 由字符串使用，0 是空格。

因此，一个由 3 个字母和 2 个空格组成的短字符串将要求所有 5 位数字包含 3 个 1 和 2 个 0，例如 11100、11010、11001、10110、10101、10011、01110、01101、01011、00111？

但是在纸上制作短序列很容易，我正在努力制作一个 for 循环来做到这一点:(。创建这个序列的伪代码非常好，请计算一下它会有多长时间？

递归会更容易理解，但如果以某种方式避免递归，它会更快吗？）

4

3 回答 3

1

嗯，有点伪代码，但你应该明白

list doThat(string, spaces){
    returnList
    spacesTemp = spaces;
    for(c = 0; c < string.length; c++){
        subString = string.getSubString(c, string.length);
        tmpString = string.insertStringAtPosition(c, createSpaceString(spacesTemp);
        retSubStringList = doThat(subString, spaces - spacesTemp);
        retCombinedList = addStringInFrontOfAllStringsInList(tmpString, retSubStringList);
        returnList.addList(retCombinedList);
        spacesTemp--;
    }
    return returnList;
}
于 2012-06-24T13:02:44.667 回答
1

那是组合。

因此，一个由 3 个字母和 2 个空格组成的短字符串将要求所有 5 位数字包含 3 个 1 和 2 个 0，例如 11100、11010、11001、10110、10101、10011、01110、01101、01011、00111？

您将三个 '1' 放在 5 个索引之一上，顺序无关紧要。所以它的 5 比 3：

5!/((5-3)!3!) = 5*4/(2*1) = 10

wikipedia.org上的文章有一张图片，展示了 3 个红色和 2 个白色方块的随机序列。

这可能有用： 统计：Python 中的组合

于 2012-06-24T13:07:55.480 回答
1

n - 字母数 m - 空格数

数数

将第一个和第二个字母之间的空格数表示为 a_1，将第二个和第三个字母之间的空格数表示为 a_2，依此类推。你的问题现在可以表述为：有多少种不同的方式可以选择 a_1, a_2 ..a_n-1 ，每个数字不小于 0 并且它们的和满足 a_1 + a_2 .... + a_(n-1) = 米？这个问题的答案是 n + m over n（我的意思是牛顿符号）。

为什么会这样？将此问题可视化为连续 n + m 个空箱。如果我们用沙子填充其中的 n 个，填充的距离将满足我们对 a_1 ... a_n-1 总和的要求。

一代

def generate(s, num_spaces):
  ans = generate_aux("_" + s, num_spaces)
  return [x[1:] for x in ans]


def generate_aux(s, num_spaces) : # returns list of arrangements
  if num_spaces == 0:
    return [s]
  if s == "":
    return []
  val = []
  for i in range(0, num_spaces + 1):
    tmp = generate_aux(s[1:], num_spaces - i)
    pref = s[0] + (" " * i)
    val.extend([pref + x for x in tmp])
  return val

print generate("abc", 2)
于 2012-06-24T13:11:46.243 回答