給定一個字符串，計算沒有重複（和禁止字符）的字符串排列的數目

現在幾個小時我一直在對付算法問題。給定一個字符串，計算沒有重複（和禁止字符）的字符串排列的數目

問題的（花式）聲明如下：

我們的花園有flowers.You單一行中給出該行的當前內容在String花園。花園裏的每個角色代表一朵花。不同的字符代表不同的顏色。相同顏色的花朵看起來都一樣。你可以按你喜歡的順序重新排列花園裏的花朵。（正式的，你可以在你的花園裏換掉任何兩朵花，而且你可以任意多次這樣做）。你還得到一個和花園一樣長的字符串禁止。你想把花園重新排列成一個新的字符串G，以下條件：

沒有兩個相鄰的花會有相同的顏色。正常情況下，對於每個有效的i，G [i]和G [i + 1]必須不同。對於每個有效的i，G [i]不能等於禁止[i]。設X是滿足上述所有條件的不同字符串G的數量。計算並返回數字（X取模1,000,000,0007）。

只是爲了用一個例子闡明：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，所以它真的在複雜度上爆炸。

我並不是真的在尋找一個完整的解決方案。只有，如果您對我應該解決問題的方式有任何建議，我會非常感謝！

來源

2016-04-30 Giuseppe Rossini

你想*計算*這樣的安排的數量，或者你想*生成*他們？前者更容易。 –

我正在努力計算，但我仍然無法考慮一個好的（性能明智的）解決方案：/ –

http://stackoverflow.com/questions/25285792/generate-all-permutations-ofa-a- list-without-adjacent-equal-elements/32366585＃32366585 – m69

我會按如下方式處理：'禁止'字符串與'花園'一樣長。這意味着給定一個N個字符的字母表，每個位置G [i]最多可以有N-1個可能的字符（因爲其中一個將被禁止）。這給了你一個僅受N限制的上界。如果這個界限小於模數，它可能會引起一些有趣的考慮，但讓我們繼續前進。

現在一個非常基本的方法是計算組合：如果花園長度爲K個字符，則第一個項目G [0]將具有N-1個可能性;如果禁止[1]與G [0]不同，則第二個G [1]將具有N-2個可能性，如果禁止[1] == G [0]則N-1可能。取決於禁止的[2]和G [1]，第三個字符G [2]也將具有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有多大，即花園有多大:)

也就是說，假設我正確地理解了問題。

來源

2016-04-30 22:54:35 lorenzog

如果我的理解正確，那麼您認爲禁止在字母表中包含字符，但情況並非總是如此。在我給出的例子中，G =「aaabbb」和forbid =「cccccc」。 –

而且，我無法爲我的字母表插入無限制的字母。例如，在同一個例子中，字母表是「ab」，但是我可以處理3個「a」和3個「b」s –

@GiuseppeRossini那麼你如何驗證'對於每個有效的i，G [i]不能等於禁止[i]'？而且，有限數量的字母進一步降低了可能性（將其視爲無重複的組合） – lorenzog

給定一個字符串，計算沒有重複（和禁止字符）的字符串排列的數目

回答

相關問題