還生成非唯一（重複）排列

我已經用C編寫了一個基本排列程序。用戶輸入一個數字，並打印出該數字的所有排列組合。還生成非唯一（重複）排列

基本上，這是它是如何工作（主算法是用於find the next higher permutation的一個）：

int currentPerm = toAscending(num); 
int lastPerm = toDescending(num); 
int counter = 1; 

printf("%d", currentPerm); 

while (currentPerm != lastPerm) 
{ 
    counter++; 
    currentPerm = nextHigherPerm(currentPerm); 
    printf("%d", currentPerm); 
}

然而，當輸入的號碼包括重複的數字 - 重複 - 不被產生一些置換，因爲他們是重複的。計數器顯示的數字與它應該顯示的數字不同 - 它不是顯示數字中的數字位數的階乘，而是顯示一個較小的數字，只有唯一的排列。

例如：

num = 1234567 
counter = 5040 (!7 - all unique) 

num = 1123456 
counter = 2520 

num = 1112345 
counter = 840

我想它來治療重複/重複的數字，好像他們是不同的 - 我不想只產生獨特排列 - 而是產生所有的排列，無論它們是重複的還是重複的。

來源

2012-11-12 amiregelz

如果你問如何改變生成排列的代碼，你不認爲這是明智的顯示生成代碼嗎？現在你只顯示一個函數調用：'nextHigherPerm（currentPerm）'。 – Caleb

@Caleb我沒有包括它，因爲它很長。我想我可以在'findHigherPerm'算法中找到一些我應該改變/注意的方向，所以我不會忽略不唯一的排列。 – amiregelz

呃...爲什麼不直接計算輸入字符串長度的階乘呢？ ;）

來源

2012-11-12 20:52:07

我想在該過程中顯示所有排列，所以我不能簡單地使用！數字來計算它。我還想顯示重複的排列 - 不僅是唯一的 - 如果有的話。 – amiregelz

所以簡單的答案是這樣的：創建一個新的字符串，其長度與輸入相同，並且沒有重複的條目。然後在新舊字符串之間創建一個映射;在新字符串和每個置換映射上生成排列。例如如果輸入爲76444321，則創建12345678，其中1映射到7,2映射到6,3映射到4（「第一」四），4映射到4（「第二」四）等等。 –

我想它來治療重複/重複的數字，好像他們是不同 - 我不想只計算的獨特排列數。

如果nextHigherPerm()使用的唯一信息是傳入的數字，那麼您運氣不好。考慮nextHigherPerm(122)。函數如何知道它已經看到了多少個122版本？應nextHigherPerm(122)返回122或212？除非您分開跟蹤發生器的當前狀態，否則無法知道。

來源

2012-11-12 21:03:38 Caleb

爲什麼不將它轉換爲字符串，然後把你的程序看作一個字謎發生器？

來源

2012-11-12 21:08:25 Jeff

如果您有3個字母，例如ABC，您可以：ABC, ACB, BAC, BCA, CAB, CBA,6個組合（6！）。如果其中的2個字母重複如AAB，則可以使：AAB，ABA，BAA，它不是3！那是什麼？它從哪裏來？來計算的話，當一個數字或字母重複真正的方法是使用組合 - >(n k) = n!/(n! * (n! - k!))

讓我們另一個說明性的例子：AAAB，那麼可能的組合是AAAB, AABA, ABAA, BAAA只有四種組合，如果按公式4C3 = 4. calcualte他們

是如何生成所有這些名單的正確步驟：

商店在數組中的數字。示例ABCD。
將數組的0元素設置爲透視元素，並將其從temp數組中排除。 A {BCD}
然後，當你想要所有的組合（即使是重複的），將時態數組的元素向右或向左移動（但是你喜歡），直到你到達n元素。

A {} BCD ------------ A {} CDB ------------ A {} DBC

再次執行第二步，但使用臨時數組。

A {B {CD}} ------------甲{C {DB}} ------------ A {d { BC}}

再次執行第三步，但在第二個溫度數組內。

A {B {CD}} ------------ A {C {DB}} ------------ A {D { BC}}

A {B {DC}} ------------ A {C {BD}} ------------ A {D {CB }}

轉到第一個陣列並移動陣列，BCDA，集B爲支點，而做到這一點，直到你找到所有組合。

來源

2012-11-12 21:56:15

還生成非唯一（重複）排列

回答

相關問題