0

文字列といくつかのスペースがあります。たとえば、文字列は「accttgagattcagt」で、挿入するスペースは10個あります。

その文字列とスペースのすべての組み合わせをどのように繰り返すことができますか？文字列内の文字を並べ替えることはできず、すべてのスペースを挿入する必要があります。

また、再配置の数を（反復せずに）どのように計算できますか？

そして、これの適切な言葉は何ですか？順列、組み合わせ、または他の何か？

（私はこれを1と0の文字列として視覚化します。ここで、1は文字列によって使用され、0はスペースです。

したがって、3文字と2スペースの短い文字列は、3つの1と2つの0を持つ5つのビット番号すべてを要求します（例：11100、11010、11001、10110、10101、10011、01110、01101、01011、00111？

しかし、短いシーケンスを紙に作成するのは簡単なので、それを実行するためのforループを作成するのに苦労しています:(。このシーケンスを作成するための素晴らしい擬似コード、そしてそれがどれくらいの長さになるかを数えてください。

再帰は理解しやすくなりますが、何らかの方法で再帰を回避すると、より速くなる可能性がありますか？）

4

3 に答える 3

1

それは組み合わせです。

したがって、3 つの文字と 2 つのスペースの短い文字列は、3 つの 1 と 2 つの 0 を含むすべての 5 ビット数を要求することになります。

5 つのインデックスの 1 つに 3 つの '1' を配置し、順序は関係ありません。したがって、3 に対する 5 は次のようになります。

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

wikipedia.orgの記事には、3 つの赤と 2 つの白の正方形のランダムなシーケンスを示す画像があります。

これは役に立つかもしれません: 統計: Python での組み合わせ

于 2012-06-24T13:07:55.480 に答える
1

n - 文字数 m - スペースの数

カウンティング

1 番目と 2 番目の文字の間のスペースの数を a_1、2 番目と 3 番目の間のスペースを a_2 のように表します。あなたの質問は次のように述べることができます: a_1、a_2 ..a_n-1 を選択して、各数値が 0 以上であり、それらの合計が a_1 + a_2 .... + a_(n-1) を満たす方法はいくつありますか? ＝メートル？この質問に対する答えは n + m over n です (over とは、ニュートン記号を意味します)。

なぜそうなのですか？この問題を 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 に答える
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 に答える