[ML][练习] 生成排列

win_hate

切，我那段代码的目的在前面写了。是某人华丽地跳出来，说“看来不怎么样啊”。然后给出一个一段代码，本质上处理的却是另一个问题。


当元素很多时，遍历整个状态空间是不可能的。

通过计算阶乘只可以处理整个状态空间里的一个小子集。

nextperm 可以随机生成一个排列，遍历其附近的排列。复杂度只有 O(n)。

懂了吗，小网友。

starfuck

滚

MMMIX

讨论问题就好好讨论，嘴里不干不净的算是怎么回事？

win_hate

本着学习一下 python 的想法，研究了 starfuck 的代码。

下面是他的正向推导代码：

1. 
   
2. def swap_g(a, i, j):
   
3.     if a[i] > a[j]:
   
4.         a[i], a[j] = a[j], a[i]
   
5.         return 1
   
6.     return 0
   
7. 
   
8. def fuck(a):
   
9.     for i in xrange(2, len(a)+1):
   
10.         for j in xrange(1, i):
    
11.             if swap_g(a, -j, -j-1):
    
12.                 return
    
13.         for j in xrange(1, i+1):
    
14.             if swap_g(a, -j, -i-1):
    
15.                 a[-i:] = sorted(a[-i:])
    
16.                 return
    
17. 
    
18. import time
    
19. t0 = time.time()
    
20. a = range(1000000)
    
21. for i in xrange(200000):
    
22.     fuck(a)
    
23. print time.time()-t0
    

复制代码

后面的比较逻辑把我弄糊涂了。后来加了几句代码才看得比较清楚。很有意思

这是添加了输出的代码：

1. 
   
2. def swap_g(a, i, j):
   
3.     if a[i] > a[j]:
   
4.         a[i], a[j] = a[j], a[i]
   
5.         return 1
   
6.     return 0
   
7. 
   
8. def fuck(a):
   
9.     for i in xrange(2, len(a)+1):
   
10.         for j in xrange(1, i):
    
11.             print a[-j], "<->", a[-j-1]
    
12.             if swap_g(a, -j, -j-1):
    
13.                 print a
    
14.                 return
    
15.         for j in xrange(1, i+1):
    
16.             print a[-j], "<=>", a[-i-1]
    
17.             if swap_g(a, -j, -i-1):
    
18.                 a[-i:] = sorted(a[-i:])
    
19.                 print a
    
20.                 return
    

复制代码

这是计算排列  8,9,7,6,5,4,3,2,1 后继排列的代码

1. 
   
2. def swap_g(a, i, j):
   
3.     if a[i] > a[j]:
   
4.         a[i], a[j] = a[j], a[i]
   
5.         return 1
   
6.     return 0
   
7. 
   
8. def fuck(a):
   
9.     for i in xrange(2, len(a)+1):
   
10.         for j in xrange(1, i):
    
11.             print a[-j], "<->", a[-j-1]
    
12.             if swap_g(a, -j, -j-1):
    
13.                 print a
    
14.                 return
    
15.         for j in xrange(1, i+1):
    
16.             print a[-j], "<=>", a[-i-1]
    
17.             if swap_g(a, -j, -i-1):
    
18.                 a[-i:] = sorted(a[-i:])
    
19.                 print a
    
20.                 return
    
21. 
    
22. a = [8, 9, 7, 6, 5, 4, 3, 2, 1]
    
23. 
    
24. print a
    
25. fuck(a)
    

复制代码

从输出可以看出比较的逻辑

1. 
   
2. [8, 9, 7, 6, 5, 4, 3, 2, 1]
   
3. 1 <-> 2
   
4. 1 <=> 3
   
5. 2 <=> 3
   
6. 1 <-> 2
   
7. 2 <-> 3
   
8. 1 <=> 4
   
9. 2 <=> 4
   
10. 3 <=> 4
    
11. 1 <-> 2
    
12. 2 <-> 3
    
13. 3 <-> 4
    
14. 1 <=> 5
    
15. 2 <=> 5
    
16. 3 <=> 5
    
17. 4 <=> 5
    
18. 1 <-> 2
    
19. 2 <-> 3
    
20. 3 <-> 4
    
21. 4 <-> 5
    
22. 1 <=> 6
    
23. 2 <=> 6
    
24. 3 <=> 6
    
25. 4 <=> 6
    
26. 5 <=> 6
    
27. 1 <-> 2
    
28. 2 <-> 3
    
29. 3 <-> 4
    
30. 4 <-> 5
    
31. 5 <-> 6
    
32. 1 <=> 7
    
33. 2 <=> 7
    
34. 3 <=> 7
    
35. 4 <=> 7
    
36. 5 <=> 7
    
37. 6 <=> 7
    
38. 1 <-> 2
    
39. 2 <-> 3
    
40. 3 <-> 4
    
41. 4 <-> 5
    
42. 5 <-> 6
    
43. 6 <-> 7
    
44. 1 <=> 9
    
45. 2 <=> 9
    
46. 3 <=> 9
    
47. 4 <=> 9
    
48. 5 <=> 9
    
49. 6 <=> 9
    
50. 7 <=> 9
    
51. 1 <-> 2
    
52. 2 <-> 3
    
53. 3 <-> 4
    
54. 4 <-> 5
    
55. 5 <-> 6
    
56. 6 <-> 7
    
57. 7 <-> 9
    
58. 1 <=> 8
    
59. 2 <=> 8
    
60. 3 <=> 8
    
61. 4 <=> 8
    
62. 5 <=> 8
    
63. 6 <=> 8
    
64. 7 <=> 8
    
65. 9 <=> 8
    
66. [9, 1, 2, 3, 4, 5, 6, 7, 8]
    

复制代码

学习了。