Fork me on GitHub

python实现全排列

要靠别人的错误繁荣自己。

全排列

不在原列表上操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date : 2018-04-03 20:39:49
# @Author : wushilong
# @Email : 1320185818@qq.com | longofo.wu@gmail.com
# @Link : http://longofo.cc


def permutation(lst):

# print(id(lst))

if len(lst) <= 1:
yield lst if lst else []
else:
for index, _ in enumerate(lst):
for per in permutation(lst[0:index] + lst[index + 1:]):
yield list(lst[index]) + per


if __name__ == '__main__':
lst = list('abc')
for per_lst in permutation(lst):
print(' '.join(per_lst))
# pass

测试结果:

1
2
3
4
5
6
7
a b c
a c b
b a c
b c a
c a b
c b a
[Finished in 0.1s]

在原列表上操作(执行交换)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date : 2018-04-03 17:59:56
# @Author : wushilong
# @Email : 1320185818@qq.com | longofo.wu@gmail.com
# @Link : http://longofo.cc


def permutation(lst, start, length):

# print(id(lst))

if (start == length):
print(' '.join(lst))
# pass

for index in range(start, length):
lst[start], lst[index] = lst[index], lst[start]
permutation(lst, start + 1, length)
lst[start], lst[index] = lst[index], lst[start]


if __name__ == '__main__':
lst = list('abc')
permutation(lst, 0, len(lst))

测试结果:

1
2
3
4
5
6
7
a b c
a c b
b a c
b c a
c b a
c a b
[Finished in 0.1s]

py大法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date : 2018-04-03 20:39:49
# @Author : wushilong
# @Email : 1320185818@qq.com | longofo.wu@gmail.com
# @Link : http://longofo.cc

import itertools


def permutation(lst):

for per in itertools.permutations(lst, len(lst)):
print(' '.join(per))


if __name__ == '__main__':
lst = list('abc')
permutation(lst)

运行结果:

1
2
3
4
5
6
7
a b c
a c b
b a c
b c a
c a b
c b a
[Finished in 0.1s]

对比分析

py大法就不用说了,肯定是经过了各种优化

这里看下前两种方式每次lst的id号:

  • 第一种:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    #!/usr/bin/env python
    # -*- coding: utf-8 -*-
    # @Date : 2018-04-03 20:39:49
    # @Author : wushilong
    # @Email : 1320185818@qq.com | longofo.wu@gmail.com
    # @Link : http://longofo.cc

    def permutation(lst):

    print(id(lst))

    if len(lst) <= 1:
    yield lst if lst else []
    else:
    for index, _ in enumerate(lst):
    for per in permutation(lst[0:index] + lst[index + 1:]):
    yield list(lst[index]) + per


    if __name__ == '__main__':
    lst = list('abc')
    for per_lst in permutation(lst):
    # print(' '.join(per_lst))
    pass

    结果:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    2743162906952
    2743162962696
    2743162962760
    2743162962824
    2743162905672
    2743162904840
    2743162905544
    2743162962760
    2743162968776
    2743162968840
    [Finished in 0.3s]
  • 第二种方式:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    #!/usr/bin/env python
    # -*- coding: utf-8 -*-
    # @Date : 2018-04-03 17:59:56
    # @Author : wushilong
    # @Email : 1320185818@qq.com | longofo.wu@gmail.com
    # @Link : http://longofo.cc

    def permutation(lst, start, length):

    print(id(lst))

    if (start == length):
    # print(' '.join(lst))
    pass

    for index in range(start, length):
    lst[start], lst[index] = lst[index], lst[start]
    permutation(lst, start + 1, length)
    lst[start], lst[index] = lst[index], lst[start]

    if __name__ == '__main__':
    lst = list('abc')
    permutation(lst, 0, len(lst))

    结果:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    1574917631432
    1574917631432
    1574917631432
    1574917631432
    1574917631432
    1574917631432
    1574917631432
    1574917631432
    1574917631432
    1574917631432
    1574917631432
    1574917631432
    1574917631432
    1574917631432
    1574917631432
    1574917631432
    [Finished in 0.1s]

可以看到用第一种方式时每次都产生了新对象,栈上需要额外的空间来保存这些对象,而第二种只有最初的那个对象。所以当排列的列表很大时,第一种方式是不合适的。

-------------本文结束感谢您的阅读-------------

本文标题:python实现全排列

文章作者:Longofo

发布时间:2018年04月03日 - 22:04

最后更新:2018年04月03日 - 22:04

原始链接:http://longofo.cc/python实现全排列.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

请我吃包辣条也好啊!!!
分享到: