如何獲得xPy的所有排列？

我想計算一組大小爲X的大小爲Y的所有排列。也就是說，如果我有（1,2,3）並且想要所有大小爲2,3P2的排列，它將是（1,2 ）（1,3）（2,1）（2,3）（3,1）（3,2）。如何獲得xPy的所有排列？

GSL和C++ STL都只提供我可以看到的xPx。有人能指點我一個C/C++庫，它可以做到這一點，或者說明一個快速和高效的內存算法嗎？

我正試圖解決一個非常短的密碼。我已經弄清了兩封信，並決定進行暴力攻擊。我有「ouglg ouyakl」，我正在檢查每一個排列對一個非常好的字典。我已經刪除了兩個字母，所以它的24P7或1,744,364,160個可能性並不那麼糟糕。我現在有一個Perl程序正在運行，所以這將是編程時間+運行時間總效率的一個有趣測試。 :)

（不，我不只是要回答的密碼。）

來源

2009-11-02 Schwern

我用this庫之前（注意這是C++）在需要做類似的東西代碼。它有排列組合，有無重複。對於您的問題，這應該足夠了（未經測試...）：

std::vector<int> v; 
v.push_back(1); 
v.push_back(2); 
v.push_back(3); 

std::vector<int>::iterator first = v.begin(), middle = v.begin() + 2, last = v.end(); 

do { 
    // do stuff with elements in range first...middle (but dont change them) 
} while(next_partial_permutation(first, middle, last));

來源

2009-11-02 22:11:40

謝謝，這樣做！幸運的是，我已經將問題優化到了21P4 * 100，這是Perl可以在大約10分鐘內完成的。 – Schwern 2009-11-02 23:06:20

我不exacly讓你對密碼的問題。但是如果你想在你的字典中找到這個詞的最長排列（anagram），你可以試試他的方式。

創建您的單詞的位掩碼。你大概可以使用64位運算法則，這樣你就可以放入近3個alpahbets了。

a->第一位，b->第二位等等。如果你有你的「ouglg ouyakl」字的情況下這意味着

abcdefghijklmnopqrstuvxyzabcdefghijklmnopqrstuvxyzabcdefghijklmnop 
100000100011001000001001000000010000100100000100000000000000000000

（希望我沒有錯過的東西）現在你的詞彙創建相同的位掩碼。

而當你對赤詞彙你只需要做的就是

vocabulary & (ouglg_ouyakl^vocabulary)

這trows 0如果你的詞彙字是從ouglg_ouyakl。

關於排列

for each permutation of numbers fom 1-n // that is 1,2 and 2,1 
    for(i=0;i<end;i++) 
    for(j=i+1;j<end;j++) 
     SET[permutation[i]],SET[permutation[j]]

編輯：prevous soluton是inapropriate爲24P7。

來源

2009-11-02 22:50:02

它的24P7，所以這將是相當多的複製代碼。 – Schwern 2009-11-02 23:03:17

您可以通過在vector<bool>標誌上使用std::next_permutation()來獲得組合。以你從(1,2,3)挑選2個元素爲例，開始你的載體(false, true, true)。重複next_permutation()這會給你(true, false, true)然後(true, true, false)，在重新開始之前。由於你想排列而不是組合，將每個組合映射到一組實際元素（例如，(true, false, true)變爲（1,3）），然後再次使用next_permutation()生成這些排列。

來源

2009-11-02 23:55:54

如何獲得xPy的所有排列？

回答

相關問題