列出1…5 排列組合

如何列出1..n 的所有排列組合

例如 123 的所有排列組合 為  123 132 321 132 213 231  3! =  6種

可是如果12345 勒 就將近有120種排列組合 如果擴增到 1…10勒 就會有10!=3628800種的排列組合

這時人腦便沒辦法一個一個將他展現出來了

而且此類問題可以歸類為NP hard 問題 也就是數字規模增大 求解時間以及複雜度將會非線性的來增加

我一開始是用暴力法 也就是所謂的窮舉法一一把他列出

但是後來發現如果用遞迴(類似於Branch and bound)的方式   會比較節省運算的時間和記憶體空間

如網路上這位網友所提的概念 http://new-acos.blogspot.com/2007/07/blog-post_04.html

 

不過我既然用了窮舉法可以解出來 就懶得想遞迴的方式了 以後再說吧 或許有厲害網友或同學可以幫我寫出來讓我參模學習一下

P.S. 窮舉的方式 在EXCEL執行沒辦法解到 1…8 => 記憶體不足 XD 窮舉法實在不是好方法阿

那小弟真的是感激不盡啊

 

兩種窮舉法的原始碼列舉如下(意思是差不多的)

第一種 :

 

Dim y(5)
y(1) = 1
y(2) = 2
y(3) = 3
y(4) = 4
y(5) = 5

‘==================================================
k = 1

For a = 1 To 5
For b = 1 To 5
For c = 1 To 5
For d = 1 To 5
For e = 1 To 5

If e <> d And e <> c And e <> b And e <> a Then
 If d <> c And d <> b And d <> a Then
  If c <> b And c <> a Then
    If b <> a Then

Cells(k, 1) = y(a) & y(b) & y(c) & y(d) & y(e)

k = k + 1

   End If
  End If
 End If
End If

Next
Next
Next
Next
Next

 

第二種

 

‘=================================================
‘==使用者輸入
‘=================================================

n = 5
s = 120
Dim y(5)
Dim U(120)

‘=================================================
‘==使用者輸入
‘=================================================
y(1) = 1
y(2) = 2
y(3) = 3
y(4) = 4
y(5) = 5

‘==================================================

k = 1

For a = 1 To n ‘==使用者輸入
For b = 1 To n
For c = 1 To n
For d = 1 To n
For e = 1 To n

 

Cells(k, 1) = y(a) & y(b) & y(c) & y(d) & y(e)  ‘==使用者輸入

k = k + 1

 

Next
Next
Next
Next
Next
‘==================================================

For a = 1 To n ^ n
 For i = 1 To n
  For j = 1 To n
ten = Mid(Cells(a, 1), i, 1)
ten2 = Mid(Cells(a, 1), i + j, 1)

If Mid(Cells(a, 1), i, 1) = Mid(Cells(a, 1), i + j, 1) Then

Cells(a, 1) = ""

End If
  Next
 Next
Next

k = 1

For x = 1 To n ^ n

If Cells(x, 1) <> "" Then

U(k) = Cells(x, 1)

k = k + 1

End If

Next

For x = 1 To s

Cells(x, 2) = U(x)

Next

 

哪種方法比較好用 答案是都很差 呵呵  應該還是要走演算法的方式會比較好

而且我的版本 還要隨著數字的規模大小而做修改 所以算是很差的寫法

而且窮舉法最大的缺點就是 數字規模越大 所花費的時間是成非線性成長的

所以如果有更好建議或想法 請跟我說 我會很感激

 

兩種窮舉法EXCEL範例下載   下載1   下載2