字符串的固定長度排列

Question

我正在嘗試使用七個字符的字符串並生成所有可能的3和4個字母的排列。這看起來像遞歸會很方便（大多數我看到的所有置換生成器都是遞歸的），但是我一直在如何避免重複。也就是說，如果我的輸入字符串是「aabcdef」，我不希望任何排列包含兩個以上的「a」字符。

您可以提供的任何見解都非常感謝。

Answer 1

使函數獲得一組字母，使其返回以您指定的字母開頭的n個排列（3或4）的集合。然後爲您的套件中的每個獨特字符運行一次。

完整的結果集將成爲子集的聯合。

Answer 2

這可以迭代地和遞歸地完成。這是一個體面的permutation generator。這可以根據您的需要進行調整，並製作通用的（以獲取元素的List<T>），以便它可以獲取數字，字符串（字符列表）等列表。

Answer 3

這裏有一條線索可能有幫助。如果您輸入了「aabcdef」，而您不想使用兩個「a」排列，則更容易從輸入中移除其中一個「a」，而不是嘗試消除具有多個「a」的排列你生成它們。

Answer 4

嘗試將角色當作元素放入角色包中。

下面是一些僞代碼，應該工作：

permute (bag <character> : theBag, integer : length, string : resultSoFar) 
    if length <= 0 then: 
     print resultSoFar 
     exit 
    end-if 

    for each x in theBag: 
     nextResult = resultSoFar + x 
     nextBag = theBag - x 
     permute(nextBag, length - 1, nextResult) 
    end-for 
end-method 

祝你好運！

Answer 5

@ Chip Uni：當我實現你的代碼時，它產生了長度爲x到max的所有排列。所以當我給一個長度爲3的長度爲3的包裝袋包含7個字符時，它會產生長度爲3到7的所有排列。但是，消除大於長度4的所有結果是一件簡單的事情。

非常感謝你，你們都！我非常感謝您的建議和幫助。

Answer 6

這是在Ruby中，但它可能有所幫助： http://trevoke.net/blog/2009/12/17/random-constrained-permutations-in-ruby/