※ 引述《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)