以特定順序獲取字符串組合的遞歸算法

有幾種算法可以打印字符串的所有組合，但我需要一個以特定順序打印出來的算法。目前我使用類似這樣的問題的一個在頂端回答（而不是問題本身）的標準置換算法：C++ recursive permutation algorithm for strings -> not skipping duplicates 以特定順序獲取字符串組合的遞歸算法

例如，輸入「ABC」，輸出將是：ABC ACB BAC BCA CAB CBA

對於輸入「ACC」，這將是：ACC CAC CCA

輸出是正確的，但我需要他們以不同的順序。輸入將只包含字符'A'和'C'，爲了方便起見，我將字符串按字母順序排序，然後將輸入字符串輸入到遞歸函數中，以便輸入字符串總是具有相同的字符（即AACCC）。至於命令，我想把'C'的集合看作是一個單獨的實體，我將左邊的每個字符集合轉移到第一個'C'的右邊。因此，對於輸入「ACC」，第一個輸出是「ACC」，這是正常的，下一個輸出應該是「CCA」，因爲我將所有'C的所有字符向左移動了一步，然後所有字符的「CCA」在第一個'C'的右邊是最後的輸出，就是「ACA」。

我需要它看起來像這樣這些輸入：

輸入：ACC

輸出：ACC CCA CAC

輸入：AACC

輸出：

AACC ACCA ACAC CCAA CACA CAAC

任何想法我應該如何ld修改我的算法以按此順序生成組合？

來源

2012-11-10 Mark Skinner

說明有點混亂。你能爲AABBCC顯示正確的輸出嗎？ –

我只會將它用於只包含兩種字符的字符串，所以假設它只包含A和C，但不包含B。 –

你仍然需要澄清你想要的輸出順序。它含糊不清或令人困惑。我的建議是生成所有的排列，然後對這些結果應用排序功能，以保證您想要的順序。不僅會更直接，而且會確保您完全定義所需的輸出順序（通過編寫比較函數進行排序） – davec

對於具有兩個明顯不同的字符A和C一個字符串，給出n是A數的，這聽起來像你要找的是什麼，這些序列的連接：所有排列開頭恰好nA的相反字典順序，所有的排列與準確n-1A的反向字典順序等開始所以，你可以把你現有的輸出這是字典順序，並以相反的順序循環訪問它，選擇元素通過匹配/^A{n}C/，/^A{n-1}C//^A{0}C/並將它們添加到新集合中。

您可以直接生成此輸出，方法是從nA的每個長度生成A的字符串到零，然後爲每個長度添加反向字典順序中其餘字符的排列。

來源

2012-11-10 22:00:02

以特定順序獲取字符串組合的遞歸算法

回答

相關問題