文字列を指定すると、繰り返しのない文字列（および禁止文字）の並びの数を数えます。

Question

私はアルゴリズムの問​​題に対して頭を打っています。次のように

問題の（空想）文は次のとおりです。

私たちの庭には、文字列の庭で、行の現在の内容を与えられているflowers.Youの単一の行が含まれています。庭の各キャラクターは一つの花を表しています。異なる文字は異なる色を表します。同じ色の花はすべて同じに見えます。庭の花を好きな順番に並べ替えることができます。 （正式には、あなたの庭に2本の花を入れ替えることができます。何回も何度でもやることができます）また、庭と同じ長さの弦を禁じられています。庭を新しい弦Gに再配置したい

2つの隣接花は同じ色を持たない。形式上、各有効iについて、G [i]とG [i + 1]は異なる必要があります。 有効な各iについて、G [i]はforbid [i]と等しくてはならない。 Xを上のすべての条件を満たす異なる文字列Gの数とする。数を計算して返す（Xモジュロ1、000、000、007）。

は一例で明確にする：Xを、私は数えることによりしようとしている

（ "AAABBB"、 "CCCCCC"）= 2（ "ABABAB" と "BABABA"）は、文字列にどのように多くの文字です（この例では 'a' - > 3、 'b' - > 4）、次に異なる可能性を再帰的に数えます（繰返しまたは禁止された文字がある場合はスキップします）。これらの行の何か：

using Map = std::map < char, size_t > ; 
Map hist; 
std::string forbid; 

size_t countRecursive(std::string s, size_t len) 
{ 
    if (len == 0) 
     return 1; 

    size_t curPos = s.size() ; 
    size_t count(0); 

    for (auto &p : hist) { 
     auto key = p.first; 

     if (hist[key] == 0) continue; 
     if (forbid[curPos] == key) continue; 
     if (curPos > 0 && s[curPos - 1] == key) continue; 

     hist[key]--;    
     count += countRecursive(s + key, len - 1); 
     hist[key]++; 
    } 


    return count; 
} 

histおよびforbidは、事前に初期化されています。しかし、これはnと思われる！ nは< = 15になる可能性があるため、実際には複雑になります。

私は本当に完全な解決策を探していません。あなたが問題に近づくべき方法について何か提案があった場合にのみ、私は非常に感謝しています！

Answer 1

私は次のようにアプローチします：あなたの '禁じられた'文字列は '庭'と同じです。これは、N文字のアルファベットが与えられると、各位置G [i]は最大でN-1個の可能な文字を持つことができることを意味する（1つは禁止されるため）。これは、Nだけに制限された上限を与えます。その範囲がモジュロよりも小さい場合、いくつかの興味深い考慮事項につながる可能性がありますが、前進してください。

非常に基本的なアプローチは、組み合わせを数えることです：ガーデンがK文字の長さである場合、最初のアイテムG [0]はN-1個の可能性を持ちます。禁則[1] == G [0]の場合、禁止[1]がG [0]、N-1と異なる場合、第2のG [1]はN-2個の可能性を有する。 3番目の文字G [2]も、禁止[2]とG [1]などによってN-2個の可能性を持ちます。

N-2は、N-1個の可能性のうち、文字の中の文字の前にある文字の値である別の文字を取り除かなければならないという事実から来ます。ポジション。

禁止されている[i + 1]が常にG [i]と異なる場合は、N-1 * N-2 * N-2 * ... * N-2、K回あります。これがあなたの下限です。

ここで、上限と下限の間に、いくつかの文字列があります。禁止された[i + 1]はG [i]に等しい。第二と第三のために;等だから、文字列のあなたの番号は次のとおりです。

N-1 * N-2 * N-2 * N-2 ... K 
N-1 * N-1 * N-2 * N-2 ... K 
N-1 * N-1 * N-1 * N-2 ... K 

というように、各文字はN-1の可能性を持つことができる文字列を持っているまで。言い換えれば

、

N-1 * (N-2)^K-1 
(N-1)^2 * (N-2)^K-2 
(N-1)^3 * (N-2)^K-3 

あなたはどのように多くのこれらの文字列のを持つことができますか？それはKの大きさ、つまりあなたの庭の大きさによって決まります。

つまり、私は問題を正しく理解していると仮定します。