幫助置換算法的一個特例（不是一般的）

Question

我一直感興趣的算法，分類，加密，二叉樹，數據壓縮，存儲操作等

，我讀過馬克·納爾遜的約排列文章在C++中使用STL函數next_perm（），非常有趣且有用，之後我編寫了一個類方法來獲得Delphi中的下一個排列，因爲這是我目前最常用的工具。這個函數適用於字典順序，我從另一個主題的答案中得到了算法思路，但現在我遇到了一個很大的問題。我正在用向量中的重複元素進行排列組合，並且有很多我不需要的排列組合。例如，我有在詞素文字順序7層的元件這個第一置換：

6667778（連續6 = 3倍，7 = 3連續次）

對於我的工作我考慮有效燙髮只有那些具有至多2元件連續地重複，例如：（連續6 = 2次，7 = 2連續次）

總之，我需要僅返回具有至多N個連續重複排列的功能，根據收到的參數。

有誰知道是否有一些算法已經這樣做？

對不起，在文中的任何錯誤，我仍然不會說英語很好。

太感謝你了， 卡洛斯

Answer 1

所以，在作業援助的一種方式，我能想到的兩種方法。

計算出包含3個或更多個連續重複的所有排列（通過將三個連續的行作爲一個假數字並將其提供給正常排列生成算法，您可以做到這一點）。製作所有這些查找表。現在生成原始字符串的所有排列，然後將它們添加到結果中，然後在查找表中查找它們。

使用生成algorthm的遞歸排列（依次選擇第一個數字的每個可能性，遞歸生成其餘數字的排列），但是在沿着到目前爲止產生的最後兩個數字的每個遞歸遍中。然後在遞歸調用函數中，如果傳入的兩個值相同，則不要讓第一個數字與這些值相同。

Answer 2

爲什麼不在正常置換函數週圍打包一個包含N個連續重複值的值？是這樣的：

（僞）

funciton custom_perm(int max_rep) 
    do 
    p := next_perm() 
    while count_max_rerps(p) < max_rep 
    return p 

Answer 3

香酥，我已經在做，在函數結尾，而不是解決問題，因爲需要生成所有排列，並檢查他們每個人一個。

consecutive := 1; 
IsValid := True; 
for n := 0 to len - 2 do 
begin 
    if anyVector[n] = anyVector[n + 1] then 
     consecutive := consecutive + 1 
    else 
     consecutive := 1; 
    if consecutive > MaxConsecutiveRepeats then 
    begin 
     IsValid := False; 
     Break; 
    end; 
end; 

既然我開始使用的詞素文字順序中的第一，最終是需要通過這種方式產生了很多不必要的燙髮。

Answer 4

這很容易做到，但很難提高效率。

如果你需要建立一個單一的一段代碼，只考慮有效的輸出，從而不打擾行走在整個組合空間，那麼你將不得不認真反思一下。

在另一方面，如果你可以用代碼在內部生產所有的組合，有效或不住，那麼它應該是簡單的。

創建一個新的枚舉，其中一個可以調用該方法next_perm，並且有這個內部使用其他枚舉，產生每個組合的一個。

然後，只需使while循環外枚舉運行要求更多的排列內一個，直到你找到一個有效的，那麼產生。此

僞代碼：

generator1: 
    when called, yield the next combination 

generator2: 
    internally keep a generator1 object 
    when called, keep asking generator1 for a new combination 
     check the combination 
     if valid, then yield it 

Answer 5

我的做法是一個遞歸發電機不遵循包含非法序列分支。

這裏的蟒蛇3碼：

def perm_maxlen(elements, prefix = "", maxlen = 2): 
    if not elements: 
     yield prefix + elements 
     return 

    used = set() 

    for i in range(len(elements)): 
     element = elements[i] 
     if element in used: 
      #already searched this path 
      continue 

     used.add(element) 

     suffix = prefix[-maxlen:] + element 
     if len(suffix) > maxlen and len(set(suffix)) == 1: 
      #would exceed maximum run length 
      continue 

     sub_elements = elements[:i] + elements[i+1:] 
     for perm in perm_maxlen(sub_elements, prefix + element, maxlen): 
      yield perm 


for perm in perm_maxlen("6667778"): 
    print(perm) 

的implentation爲可讀性，不寫速度，但算法應該比天真地過濾所有排列快得多。

print(len(perm_maxlen("a"*100 + "b"*100, "", 1))) 

例如，它以毫秒爲單位運行，其中樸素過濾解決方案需要幾千年甚至更久。