風之軒

假如說有個變數能輸入合法的字為( 1, 2), 我想要產生所有可能的組合為

{'12'} {'21'}
{'1'} {'2'}
{' '}

上列五種情形，該怎麼用程式產生呢？


將問題拆成兩個問題，第一個是all subsets,
接著第二個是同樣的集合有不同的排列組合情形來解.

1.所有子集合的產生方法.


把這個問題倒轉來看。
{}
--------------
{4}
--------------
{3,4}
{3}
--------------
{2,4}
{2,3,4}
{2,3}
{2}
--------------
{1,4}
{1,3,4}
{1,3}
{1,2,4}
{1,2,3,4}
{1,2,3}
{1,2}
{1}

你發現到什麼？

原來
{3,...} 就是把上面所有集複製一次，只是在前面加入 3 而已。
{2,...} 就是把上面所有集複製一次，只是在前面加入 2 而已。
{1,...} 就是把上面所有集複製一次，只是在前面加入 1 而已。
留意一下，4 也是把上面的空集複製一次而加進 4 啊。


上面這個講法在python中用動態的陣列寫就行了，很簡單.


算法規則:每個節點的子節點只能比自己小, 可有0到N-1個子節點
以4而言
以空集合為起點, 向下有1-4的節點
第二層
1往下就有2,3,4
2往下就有3,4
3往下就有4
第三層
[1 這串0
2往下有3,4
3往下有4
.
.
.
因此每個節點所代表的尋訪路徑,就是你的答案
以深度搜尋,就會變成
{}, {1}, {1,2},{1,2,3}, {1,2,3,4},{1,2,4},{1,3},{1,3,4},{1,4},
{2},{2,3},{2,3,4}{2,4},{3},{3,4},{4}

第二種就是用遞迴的方式建出一個tree,再用DFS跑出結果來，


但第二種還是複雜了點，現在把第一個方法 遞迴化再列出來的式子為

AllSet(N) = AllSet(N-1) , AllSet(N-1) N for n >= 2
{}, 1 for n = 1


---

接著來講一下 第二個 排列組合的怎麼列，

先舉個例子.{123}
要列出 {123} {132} {213} {231} {312} {321}

首先以寫程式來說照原本我們手動這樣列
程式不太好寫，可能會寫超多層迴圈的，
所以用另一種演算法。


def all_perms(str):
if len(str) <=1:
yield str
else:
for perm in all_perms(str[1:]):
for i in range(len(perm)+1):
#nb str[0:1] works in both string and list contexts
yield perm[:i] + str[0:1] + perm[i:]


解釋一下這code.

排列數是n!= n * (n-1)!
故
n = 1 => 1
n = 2 => [2]1, 1[2] (2為新加入的元素)
n = 3 => [3]21, 2[3]1, 21[3], [3]12, 1[3]2, 12[3] (21, 12為n =2的表示項, 3為新加入的元素)

看出來就是新加入的元素去插入前面n-1結果中的每個空隙，
而上面是程式碼是用python用 generator 所做出來的，

而最直覺的解法是需要用多用到目前哪個數被用過，
還要多一個空間來紀錄.
(最直覺的簡法，就是上面一開始我怎麼寫出所有解的想法就是了)