免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 5651 | 回复: 13

抛砖引玉,算法求解 [复制链接]

论坛徽章:
0
发表于 2006-05-18 11:11 |显示全部楼层
把一个字符串中所有字符的所有可能的组合打印出来(字符串中没有重复的字符)
不考虑字符顺序('123'和'312'是一样的)
我勉强写了一个
超级慢
大伙有好的算法吗

  1. #!/usr/bin/env python

  2. def split_str(mystr):
  3.         s_len=len(mystr)
  4.         if s_len <= 0:
  5.                 return []
  6.         l_ret=[]
  7.         s_list=list(mystr)
  8.         while s_len > 0:
  9.                 s_len=s_len-1
  10.                 pp=s_list[:s_len]+s_list[s_len+1:]
  11.                 if len(pp):
  12.                         l_ret.append(''.join(pp))
  13.         return l_ret

  14. def split_list(mylist):
  15.         l_len=len(mylist)
  16.         if l_len <= 0:
  17.                 return []
  18.         while l_len > 0:
  19.                 l_len=l_len-1
  20.                 zz=split_str(mylist[l_len])
  21.                 zz_len=len(zz)
  22.                 while zz_len > 0:
  23.                         zz_len=zz_len-1
  24.                         yy=split_list([zz[zz_len]])
  25.                         if len(yy):
  26.                                 zz=zz+yy
  27.                 if len(zz):
  28.                         for i in zz:
  29.                                 if i not in mylist:
  30.                                         mylist.append(i)
  31.         return mylist

  32. if __name__ == '__main__':
  33.         print split_list(['12345'])
复制代码

  1. sam-linux:/tmp# ./bb.py
  2. ['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']

复制代码

[ 本帖最后由 bleem1998 于 2006-5-18 11:19 编辑 ]

论坛徽章:
0
发表于 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,

论坛徽章:
0
发表于 2006-05-19 00:17 |显示全部楼层
太厉害了。。。

论坛徽章:
0
发表于 2006-05-20 00:48 |显示全部楼层
yield 到底是啥意思,看了半天python的帮助,还是看不懂。:(

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

论坛徽章:
0
发表于 2006-05-22 09:15 |显示全部楼层
在网上看到了limodou的博客,以下是关于生成器的话:

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

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

论坛徽章:
0
发表于 2006-05-23 11:07 |显示全部楼层
yield好难懂啊!

论坛徽章:
0
发表于 2006-06-04 23:12 |显示全部楼层

我用的是递归

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


  1. def permute(str,prefix):
  2.         if len(str) == 0:
  3.                 print prefix,
  4.                 return
  5.         permute(str[1:],prefix+str[0])
  6.         permute(str[1:],prefix)       
  7.    
  8. permute('12345','')
复制代码

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

  1. 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
复制代码

[ 本帖最后由 shaohui 于 2006-6-4 23:27 编辑 ]

论坛徽章:
0
发表于 2006-06-05 09:53 |显示全部楼层
原帖由 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 ...

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

论坛徽章:
0
发表于 2006-06-05 13:55 |显示全部楼层
无敌了
竟然看不懂!!
解释一下这个递归吧
谢谢

论坛徽章:
0
发表于 2006-06-06 14:03 |显示全部楼层
permute(str,prefix): 表示在把一个字符串str中所有字符的所有可能的组合打印出来,在打印的同时前面加上一个前缀prefix
而对于任意一个字符串又可以分成2个部分,第一个字符和後面的部分,而第一个字符又有兩種情况:选入和不选入,
因此prefix有prefix 和prefix+str[0]两种情况
对于後面的部分
则又是一个规模比较小的与原来问题性质一样的问题,所以用递归了
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP