Permutation实现（Haskell）

发表于   |  

Permutation实现（Haskell）

得到一个列表的全排列（Permutation）是一个比较基本的问题, LeetCode上也有, n个元素的全排列有n!情况，最近在学习Haskell就理解总结一下实现的方法。

思路一

第一种方法是采用把新元素插入到子数组的全排列的各个可能位置的方法，比如要得到[a,b,c]的全排列，可以把c依次插入到[a,b], [b,a]的3个可能的位置，这样正是全排列的6种结果。所以要求一个列表的全排列，就可以自底向上，逐渐插入，代码如下：

1
2
3
4
5
6
7
insert :: a -> [a] -> [[a]]
insert n [] = [[n]]
insert n (n':ns) = (n:n':ns) : [n':ns' | ns' <- insert n ns]

permutation :: [a] -> [[a]]
permutation [] = [[]]
permutation (x:xs) = concat [insert x permuxs | permuxs <- permutation xs]

插入的过程通过举例很好理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
insert 1 [] = [[1]]

insert 2 [1] = insert 2 (1:)
			   = [2,1] : [1:∆], ∆ = insert 2 [] = [2]
			   = [2,1] : [1:[2]]
			   = [2,1] : [[1,2]]
			   = [[2,1], [1,2]]
insert 3 [1,2] = insert 3 (1:[2])
				 = [3,1,2] : [1: ∆], ∆ = insert 3 [2]
				 						   = 这一步已经理解了
				 						   = [[3,2],[2,3]]
				= [3,1,2] : [[1,3,2],[1,2,3]]
				= [[3,1,2],[1,3,2],[1,2,3]]

思路二

第2中思路来源于对排列结果的观察，每个排列可以归为两类，以元素x开头，或者不以x开头，所以这里的递归过程是已列表中的每个元素为首，然后concat通过其他元素得到的permutation。代码如下：

1
2
3
permutation' :: Eq a => [a] -> [[a]]
permutation' [] = [[]]
permutation' xs = [y:ys | y <- xs, ys <- permutation' (delete y xs)]

举例：

1
2
3
4
5
6
permutation' [] = []
permutation' [1] = [x:y | x<-[a], y<-[]] = [[1]]
permutation' [1,2] = [1: permutation' [2], 2 : permutation' [1] ]
					  = [[1,2], [2,1]]
permutation' [1,2,3] = [ 1: permutation' [2,3], 2: permutation' [1,3], 3: permutation' [1,2]]
					  = [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

结果分析

其实通过结果也可以看到结构上的特点，法2中分别以每个元素开头，子结构也同样如此，有分块的特点；法1中元素1插入到了子列表的排列中，然后分支。

1
2
3
4
5
6
7
*Main> permutation [1,2,3]
[[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]
*Main> :r
[1 of 1] Compiling Main             ( Permutation.hs, interpreted )
Ok, modules loaded: Main.
*Main> permutation' [1,2,3]
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

小插曲

最近发现一个Linux命令tldr不错，列出命令的常见用法，而不是迷失在详尽的man page里面，在github上star数很高。比如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
$ tldr lsof

lsof
  Lists open files and the corresponding processes.
  Note: In most cases, you need root privilege (or use sudo) because you want to list files opened by others.

  - Find the processes that have a given file open:
    lsof /path/to/file

  - Find the process that opened a local internet port:
    lsof -i :port

  - Only output the process PID:
    lsof -t /path/to/file

  - List files opened by the given user:
    lsof -u username

  - List files opened by the given command or process:
    lsof -c process_or_command_name