※ 引述《ric2k1 (Ric)》之銘言： : Permutation without recursion 然後還要 ascending order 其實蠻困難的. : 抱歉當初出題時沒有想清楚. : 想不出來可以不要寫, : 或是參考下以下網頁 (但是他只有 permutations, 沒有 sorting): : http://www.geocities.com/permute_it/ Recursive function 的基本特性就是 1. The task itself is a series of repeated actions. 2. The series of the repeated actions can be characterized by certain index. 3. Each of the repeated action can be formulated by the index. For example, the Ficonacci series can be formulated as: f(n) = f(n-1)+f(n-2). The factorial can be formulated as f(n) = (n)*f(n-1). These are trivial cases. How to formulate the "permutation" function? 此外, recursive function 的基本作法有以下要點: 1. Identify the base case. For example, the base case for Fibonacci is when n = 1 or 0, while for factorial it is n = 1. 2. Assume the "recursed cases" have been completed. What is the task for this case in terms of the recursed results? For Fibonacci, it is just "addition", and for factorial, it is "multiplication". What's the base case for "permutation"? What is the task of permutation in terms of its recursed results? 以下不想被雷到的人可以按左鍵離開... 第一個問題, 假設我們要 permute n 個數字, 我們首先將它們排成一列 (in ascending order), >>> { x(0), x(1), ...., x(n-1) }, x(i) 表示數列中 index = i 的數字 permutation function 可用此數列中的 index 作為 recursive function 的 index. Let the recursive function called "permute(int i)". Obviously, the permutation task should start by calling "permute(0)". The recursive function is then: permute(i) = do_something_on_top_of (permute(i+1)); 第二個問題, The base case should be when there is only one number to permute. This is when the i = n-1 in permute(i). Clearly, there is only one way to permute when there is only one number. Please note that you should print out the permutation when you reach the base case. What to print? We will come back to this later. 第三個問題, 也是關鍵, permute(i) 與 permute(i+1) 的關係是什麼? 先想一下當 permute(i+1) return 回來, 就表示 以 { x(0)... x(i) } 為 prefix, 而對於 { x(i+1)... x(n-1) } 的所有 permutations 都已經產生過了, 接下來呢? 接下來就是從 { x(i+1)... x(n-1) } 中挑 "下一個沒當過 x(i) 的最小" 的數目, say x(j), 來與 x(i) 交換, 然後再 call permute(i+1) 一次, 直到找不到沒有做過的 "下一個數目", 就可以 return 這層 recursion. 前面問過在 base case 時要 print 什麼呢? 其實如果你 implement 的得宜的話, 就是把 swap 過的數列印出來就好了. 而且這樣正好符合 ascending order. ===== FYI, 我寫的 permute(int i) 的 body 包含印數字大概只有 20 行而已... ... 不是說你一定要寫那麼短, 而是想告訴你不要害怕, 沒那麼難!! 大家加油!! --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.121.132.121 ※ 編輯: ric2k1 來自: 59.121.132.121 (12/01 22:36)