問VB程式,產生一個12個字元的所有排列(NPSC的題目)

Question

(NPSC2003決賽題目)
http://icpc.cc.ntu.edu.tw/npsc2003/
其實就是字典排序
只是超大的組合,讓我滿頭痛的
輸入說明:
第一個數 代表幾個字元,第二個數 代表第幾排字串
每行都是如此 , 做到 0 0 則停下
範例:
3 4
3個字元的所有組合如下
A B C 第1排
A C B 第2排
B A C 第3排
B C A 第4排 <<<< 答案要第4排 所以只須輸出此行就好!!
C A B 第5排
C B A 第6排
範例輸入
3 4
3 12
5 120
12 12
0 0
範例輸出
B C A
C B A
E D C B A
A B C D E F G H J L K I
------------------------------------------------------------------------------
我最多寫到 7! 就GAME OVER了, 有12!=479001600 組合 = =
想不到訣竅在哪????
拜託各位大大支援!>_<

http://www.tcgs.tc.edu.tw/blog/index.php?op=ViewArticle&articleId=46&blogId=2
這位大大寫的程式好厲害! 可是我看不懂C　= ="
請各位大大支援 VB要怎麼寫:|?

F選手 , 你的速度跟我一樣慢= = 這種速度我覺得算失敗吧?
兩位都有一個問題耶@__@"479001600 會爆

Answer 1

看到您寫"!"故想到一個較簡單的方法，因為只要某一排，直接求出那一排就好了阿，從機率的觀點來看，第一個數字有N種組合，第二個有N-1種組合，所以我的方法是先算出第一個字，再算第二個字，以此類推下去，第一個字的算法
假設有3個數字，第一個數字=(排數+1)/(3-1)!第二個數字=(排數-1)/(3-2)! Mod (3-2)!，MOD的用途再於把第一個數字踢掉，排數-1是因為我的程式設計是從0開始計算的，從您舉的例子來看一開始機會有"ABC"，第四排第一個數字算出來是1所以先取"B"出來，剩下的為"AC"，再把第二個數字算出來是1，把B取出來答案變成"BC"剩下A再把A取出來答案變成"BCA"...
在這裡計算第幾個數字可以用陣列+迴圈，一次就算出來，程式如下:
Dim a As Integer, b As Integer, i As Integer, j As Integer, Answer As String
Dim Data() As Integer, Data2() As String
a = val(InputBox("請輸入幾個字元?"))
b = val(InputBox("請輸入第幾排?")) - 1 '因為我設計的是把0當成第一列開始算
ReDim Data(a - 1), Data2(a - 1)
Data2(0) = "A"
Data(0) = 0 '最後要把剩下的取出來
'計算第幾個數放進DATA，順便把ABCD....按照順序放進去DATA2
For i = 1 To a - 1
Data(i) = b Mod (i + 1)
b = b \ (i + 1)
Data2(i) = Chr(65 + i)
Next
'根據第幾個數(DATA)向DATA2要字串，然後把DATA2整理一下，拿走的就消失，剩下的往前一格
'就像樹狀圖一樣，一開始選A會剩下BCD在選C會剩下BD以此類推...
　For i = a - 1 To 0 Step -1
　　Answer = Answer & Data2(Data(i))
　　For j = Data(i) To UBound(Data2) - 1
　　　Data2(j) = Data2(j + 1)
　Next
　Next
　'輸出答案
　MsgBox Answer
Exit Sub

2006-11-30 10:35:49 補充：
請輸入的字元數不要超過26，否則會從ASCII要到什麼奇怪的字我也不知道。

2006-11-30 10:50:12 補充：
把B宣告成LONG可以支援到12個字元數，Currency可以支援到20個字元數，還要更大的話...就要用字串處理了

2006-11-30 12:48:04 補充：
OK阿，我已經寄信給你了噢。

2006-11-30 12:50:03 補充：
學校不給我寄信...
[e-mail]

2006-11-30 21:44:43 補充：
不用擔心啦...等到程式比賽完...
就會有很多人潛水去準備大考了吧...
到時候又是你們幾位的天下了...
後面還是要靠你們繼續下去阿!!
不要灰心噢!!

Answer 2

12月是全國高職學校工科與商科的技藝競賽期，所以會有部分選手上來問/答

Answer 3

亡靈 兄
其時你也不賴,只是最近出現許多高手
可能跟最近的設計大賽有關.

2006-12-01 19:20:11 補充：
是啊!
希望他们不要潛水潛得太九久.

Answer 4

f兄~你這樣跑12階太慢了,參考看看小弟的吧...
'----------------------------------------------------------
Dim N&(), B() As Boolean

Private Sub Command1_Click()
inNum = Split(InputBox("測試值", , "12 12"), " ")
ReDim N(inNum(0) - 2), B(inNum(0) - 1)
N(0) = 1
For I = 1 To inNum(0) - 2
N(I) = (I + 1) * N(I - 1)
Next I
MsgBox Ans(inNum(1) - 1, inNum(0) - 2)
End Sub

Private Function Ans$(ByVal inN%, ByVal inR%)
Dim divN%, modN%, I%, J%, K%
If inR < 0 Then
For K = 0 To UBound(B) - 1
If Not B(K) Then Ans = Chr(65 + K)
Next K
Exit Function
End If
divN = inN \ N(inR)
Do Until I > divN
DoEvents
If B(J) = False Then I = I + 1
J = J + 1
Loop
B(J - 1) = True
Ans = Chr(65 + J - 1) & Ans(inN - N(inR) * divN, inR - 1)
End Function
'-----------------------------------------------------------
說明:
當我看到題目的字典排序時,就覺得這實在很像數字進位...
因為無論是幾進制,當進位後,又是重覆相同的排序...
如2進制...
000
001
010
011
'---------------
100
101
110
111
不看最左邊的位數,其實右邊兩個位數只是相同的排列組合...
當進到第四位位數時,右邊三個位數亦然....
0111和1111的差別不過就是111+2^3*0和111+2^3*1的差別...
所以說,我們觀察一下3階的ABC排序
A B C
A C B
--------
B A C
B C A
--------
C A B
C B A
仔細看,除了"符號"不相同,其實三段都是相同的排列組合....
第二段的B,其實就扮演第一段的A的角色
第三段的C,其實也扮演第一段的A的角色
而B、C其實就有點像「數字進位」時,最左邊那個進位的角色...
只不過數字系統是數字,這裡是符號...
數字會重覆,這裡不會....
所以說,運用這點,就可以算出第幾排是什麼內容....
比如說,上面的3階....看一下各排的第一個字的算式
(1-1) \ 2 = 0 (加65,轉為文字即為A)
(2-1) \ 2 = 0 (加65,轉為文字即為A)
(3-1) \ 2 = 1 (加65,轉為文字即為B)
(4-1) \ 2 = 1 (加65,轉為文字即為B)
(5-1) \ 2 = 2 (加65,轉為文字即為C)
(6-1) \ 2 = 2 (加65,轉為文字即為C)
而第二個字如何計算?
(1-1) \ 1 = 0
(2-1) \ 1 = 1
這裡的0、1不一定=A、B,因為各段的"符號"不相同...
如第一段為B、C,第二段為A、C,第三段為A、B
你只須依循固定的算式,給它不同符號,就能把第幾排是什麼內容'算'出來了..
而 \ 2 和 \ 1的2、1各代表的是上一階共有的排列方式總數.....
1數時 1
2數時 2
3數時 6
4數時 24
5數時 120
6數時 720
下面這段程式即是在計算這個關係....
N(0) = 1
For I = 1 To inNum(0) - 2
N(I) = (I + 1) * N(I - 1)
Next I

2006-11-30 09:21:49 補充：
溢位的問題,改一個地方就OK了..Private Function Ans$(ByVal inN%, ByVal inR%)inN改成長整數&就好啦!Private Function Ans$(ByVal inN&, ByVal inR%)http://specterglobe.myweb.hinet.net/abc.txt

2006-11-30 15:07:10 補充：
又**掉了~~~ XD
採用率從84%一連下滑到74%..
不過還是560大比較高明,我甘拜下風..
練功練功~~我要練功~~~~

2006-12-01 11:39:39 補充：
560兄您言重了...
小弟上來知識+是為了學習(相信其他高手也是)
可不是為了當沒有老虎在山上的山猴子...
幾個月前小弟連Split、Join、InStr、Replace等函數都不會用..
還不就是不斷觀摩其他高手的程式,才慢慢有點小進..
前幾天才跟愁痕兄說最近的知識變得很有趣...
若問題的人和高手們都離去,那還有什麼意思...

Answer 5

'12階要跑很久
'你是工科選手嗎?
'我猜這應該是老師出給你的吧?
Dim N%, M%, A$()
Private Sub Form_Activate()
Do
N = InputBox("請輸入字元數", " ", "3")
M = InputBox("請輸入第幾排字串", " ", "4")
Loop Until N > 0 And M > 0
Call CH(j$, L#)
Print "第" & M & "排為" & A(M - 1)
End Sub
Private Sub CH(j$, L#)
Dim i%
If Len(j) = N Then ReDim Preserve A(L): A(L) = ABC(j): L = L + 1: Exit Sub
For i = 1 To N
If InStr(j, i) = 0 Then Call CH(j & i, L)
Next i
End Sub
Function ABC(j$) As String
Dim i%, Temp$
For i = 1 To Len(j)
Temp = Temp & Chr(64 + Val(Mid(j, i, 1)))
Next i
ABC = Temp
End Function

2006-11-30 12:12:30 補充：
560兄的實力不錯
不介意的話可以留個即時通交流嗎 ?