[範例] next_permutation

作者: bigpigbigpig (To littlepig with love)   2014-05-29 10:57:31
def next_permutation(L):
n = len(L)
if n == 0 or n == 1: return (False, L)
i = n - 1
while True:
i -= 1
if L[i] < L[i+1]:
j = n - 1
while not ( L[i] < L[j] ): j = j - 1
L[i], L[j] = L[j], L[i]
nL = L[(i+1):]
nL.reverse()
L[(i+1):] = nL
return (True, L)
if i == 0:
L.reverse()
return (False, L)
執行範例:
>>> L1 = [ 1, 2, 3, 4 ]
>>> count = 0
>>> not_yet = True
>>> while not_yet:
count += 1
print("%5d" % count, L1)
(not_yet, L1) = next_permutation(L1)
1 [1, 2, 3, 4]
2 [1, 2, 4, 3]
3 [1, 3, 2, 4]
4 [1, 3, 4, 2]
5 [1, 4, 2, 3]
6 [1, 4, 3, 2]
7 [2, 1, 3, 4]
8 [2, 1, 4, 3]
9 [2, 3, 1, 4]
10 [2, 3, 4, 1]
11 [2, 4, 1, 3]
12 [2, 4, 3, 1]
13 [3, 1, 2, 4]
14 [3, 1, 4, 2]
15 [3, 2, 1, 4]
16 [3, 2, 4, 1]
17 [3, 4, 1, 2]
18 [3, 4, 2, 1]
19 [4, 1, 2, 3]
20 [4, 1, 3, 2]
21 [4, 2, 1, 3]
22 [4, 2, 3, 1]
23 [4, 3, 1, 2]
24 [4, 3, 2, 1]
>>>
作者: tiefblau (tiefblau)   2014-05-29 13:04:00
itertool表示
作者: tjjh89017 (伊達政宗)   2014-05-29 17:32:00
這是要實作離散數學中的作法吧XD
作者: shaopin (Brian)   2014-05-30 09:58:00
so..? C++STL都有, 還有prev_permutation, 實做這個要做啥?
作者: bigpigbigpig (To littlepig with love)   2014-05-30 14:58:00
試試 L = [ 0, 0, 1, 1, 1 ] :)

Links booklink

Contact Us: admin [ a t ] ucptt.com