抛砖引玉，算法求解

bleem1998

UID: 272
帖子: 63
积分: 144
在线时间: 5 小时

1^# bleem1998 发表于 2006-05-18 11:11

抛砖引玉，算法求解

把一个字符串中所有字符的所有可能的组合打印出来(字符串中没有重复的字符)
不考虑字符顺序（'123'和'312'是一样的）
我勉强写了一个
超级慢
大伙有好的算法吗

[Copy to clipboard] [ - ]

CODE:

#!/usr/bin/env python

def split_str(mystr):
s_len=len(mystr)
if s_len <= 0:
return []
l_ret=[]
s_list=list(mystr)
while s_len > 0:
s_len=s_len-1
pp=s_list[:s_len]+s_list[s_len+1:]
if len(pp):
l_ret.append(''.join(pp))
return l_ret

def split_list(mylist):
l_len=len(mylist)
if l_len <= 0:
return []
while l_len > 0:
l_len=l_len-1
zz=split_str(mylist[l_len])
zz_len=len(zz)
while zz_len > 0:
zz_len=zz_len-1
yy=split_list([zz[zz_len]])
if len(yy):
zz=zz+yy
if len(zz):
for i in zz:
if i not in mylist:
mylist.append(i)
return mylist

if __name__ == '__main__':
print split_list(['12345'])

[Copy to clipboard] [ - ]

CODE:

sam-linux:/tmp# ./bb.py
['12345', '1234', '1235', '1245', '1345', '2345', '234', '235', '245', '345', '34', '35', '45', '4', '5', '3', '24', '25', '2', '23', '134', '135', '145', '14', '15', '1', '13', '124', '125', '12', '123']

stone.zh

UID: 39884
帖子: 157
积分: 361
在线时间: 1 天 9 小时

2^# stone.zh 发表于 2006-05-18 23:37

def permute(str):
for i in str:
      yield i;
      for j in permute(str[str.index(i)+1:]):
         yield i+j

for i in permute("12345"):
print i,

bleem1998

UID: 272
帖子: 63
积分: 144
在线时间: 5 小时

3^# bleem1998 发表于 2006-05-19 00:17

太厉害了。。。

Hex

UID: 24710
帖子: 1
积分: 2
在线时间: 10 分钟

4^# Hex 发表于 2006-05-20 00:48

yield 到底是啥意思，看了半天python的帮助，还是看不懂。：（

generator是什么？generator function又跟普通的functions有啥区别？谁能讲讲？

ukyo502

UID: 17448
帖子: 1
积分: 2
在线时间: 10 分钟

5^# ukyo502 发表于 2006-05-22 09:15

在网上看到了limodou的博客,以下是关于生成器的话:

Iterator是迭代器的意思，它的作用是一次产生一个数据项，直到没有为止。这样在 for 循环中就可以对它进行循环处理了。那么它与一般的序列类型(list, tuple等)有什么区别呢？它一次只返回一个数据项，占用更少的内存。但它需要记住当前的状态，以便返回下一数据项。它是一个有着next()方法的对象。而序列类型则保存了所有的数据项，它们的访问是通过索引进行的。

再看了一下二楼的代码,有点懂了..

guotie

UID: 37694
帖子: 58
积分: 133
在线时间: 4 小时

6^# guotie 发表于 2006-05-23 11:07

yield好难懂啊！

shaohui

UID: 33184
帖子: 1
积分: 2
在线时间: 10 分钟

7^# shaohui 发表于 2006-06-04 23:12

我暂时还看不懂yield是什么意思,刚入门
所以用递归写了一个

[Copy to clipboard] [ - ]

CODE:

def permute(str,prefix):
if len(str) == 0:
print prefix,
return
permute(str[1:],prefix+str[0])
permute(str[1:],prefix)

permute('12345','')

也比较简单,就只要5行代码
运行结果如下

[Copy to clipboard] [ - ]

CODE:

12345 1234 1235 123 1245 124 125 12 1345 134 135 13 145 14 15 1 2345 234 235 23 245 24 25 2 345 34 35 3 45 4 5

broader

UID: 39020
帖子: 191
积分: 439
在线时间: 2 天 1 小时

8^# broader 发表于 2006-06-05 09:53

QUOTE:

原帖由 shaohui 于 2006-6-4 23:12 发表
我暂时还看不懂yield是什么意思,刚入门
所以用递归写了一个

[code]
def permute(str,prefix):
if len(str) == 0:
print prefix,
return
permute(str[1:],prefix+str[0])
permute(str[1:],prefix ...

递归算法解决问题总是很优雅！

bleem1998

UID: 272
帖子: 63
积分: 144
在线时间: 5 小时

9^# bleem1998 发表于 2006-06-05 13:55

无敌了
竟然看不懂！！
解释一下这个递归吧
谢谢

shaohui

UID: 33184
帖子: 1
积分: 2
在线时间: 10 分钟

10^# shaohui 发表于 2006-06-06 14:03

permute(str,prefix): 表示在把一个字符串str中所有字符的所有可能的组合打印出来,在打印的同时前面加上一个前缀prefix
而对于任意一个字符串又可以分成2个部分,第一个字符和後面的部分,而第一个字符又有兩種情况:选入和不选入,
因此prefix有prefix 和prefix+str[0]两种情况
对于後面的部分
则又是一个规模比较小的与原来问题性质一样的问题，所以用递归了