求大家帮解一道关于python分割的算法题
罗列出qwerty
被.
分割的所有情况:
q.werty q.w.erty qw.erty ... q.w.e.r.t.y
具体的实现:
s = 'qwerty' k = {}.fromkeys(s[0:-1], 0) def foo(a, b): if b == len(a): for p, q in zip(s, a+[0]): print p, if q: print '.', print '' else: a[b] = 1 foo(a, b+1) a[b] = 0 foo(a, b+1) foo(k.values(), 0)
如果你想看下实现原理: 我这里有个C版的,更清楚些:
http://hit9.org/blog/Data_Structures_... 的第2题
--------------- 10-25更新-----------
好吧.比较简短的版本来了:
下面的属于比较'不那么麻烦的做法'~ 用了itertools模块:
from itertools import product s = 'qwerty' for i in product(*(([1, 0], )*(len(s)-1))): for p, q in zip(s, list(i)+[0]): print p, '.' if q else '', print ''
楼主 这个问题其实不难,首先肯定的是“点”是存在于两个字母之间的 ,那么你就想象有n个“位置”在n+1个字母之间,每一个“位置”有两个状态,一个是存在“点”,一个是不存在“点”,都不存在的情况被排除掉了,所以本题的核心是求集合的非空子集。所有的可能性的个数为 2^n - 1
假设 字符串为qwer,那么有三个“位置”,我们把这个三个“位置”分别命名为a,b,c
那个通过循环和二进制位的判断可以得出所有的结果
楼主静下心来看看下面的结果,悟一下,算法的复杂度还是蛮低的
index从 1 到 2^n-1 (<=) 循环,每一步判断当前index中二进制位为1对应的位,然后将"点"放到相应的位置,下面的例子当到2^3-1也就是7的时候,三个“位置”上都放上了“点”
c b a 0 0 1 qwe.r 0 1 0 qw.er 0 1 1 qw.e.r 1 0 0 q.wer 1 0 1 q.we.r 1 1 0 q.w.er 1 1 1 q.w.e.r
我自己之前写过一个SKU相关的算法,其实本质和这个问题是一样的,可以参见 http://geeklu.com/2012/09/sku/
来个5行简单版
def add_dots(s): r = [s[:i] + '.' + s[i:] for i in range(1, len(s))] r += [j + '.' + s[i:] for i in range(1, len(s)) for j in add_dots(s[:i])] r += [s[:i] + '.' + j for i in range(1, len(s)) for j in add_dots(s[i:])] return set(r)
//效率灰常低,纯属玩玩。。
p.s. 针对"abcde"字符串的排列
某男的ruby(1.9.x)精简版:
p (?b..?e).inject([?a]){|a,q|a.product [q,?.+q]}.map &:join
简单地说就是笛卡尔积,至于看不看得懂是另一回事了……(反正我没看太懂,ruby语法太抽象。。)
某男的C精简版:
#define z(a,b) printf(#a"%s",(x>>b)&1?".":""), main(x){z(a,3)z(b,2)z(c,1)z(d,0)puts("e");16-x&&main(x+1);}
与hit9同学协力完成了个(易读易写的)
from itertools import product [''.join(i + j for i, j in zip('abcd', p)) + 'e' for p in product(['.', ''], repeat = 4)]
写了个周期性交互插入的函数riffle,模仿的是Mathematica的一个内置函数,
from itertools import product
'''
riffle([1, 2, 3, 4, 5], [x, y]) = > [1, x, 2, y, 3, x, 4, y, 5]
'''
def riffle(a1, a2):
m ,n = divmod(len(a1), len(a2))
return sum( zip( a1, a2*m + a2[:n] ), ())[:-1]
print [''.join(riffle("abcde", i)) for i in product(['.', ''], repeat = 4) ]
注意,sum(.., ())的写法简洁但是低效.
Mathematica code(可以在www.mathics.net在线运行):
Row@Riffle[{a, b, c, d, e}, #] & /@ Tuples[{".", ""}, 4]
(*可能是最短的吧*)
TableForm@Table[Join @@ Append[ij, {e}] // Row,
{p, Tuples[{".", ""}, 4]}, {ij, {Transpose@{{a, b, c, d}, p}}}]
(*模仿ls的列表解析*)
玩蛇网文章,转载请注明出处和文章网址:https://www.iplaypy.com/wenda/wd20459.html
相关文章 Recommend
- • Python操作Redis数据库方面的问题
- • 豆瓣API 40次/分钟的访问限制怎么办
- • 大家都来晒晒您见过的最优秀最实用的一段pyth
- • 求更好的python 字典满足条件值的相加方法
- • 大家一起来讨论抽用正则取优酷视频并生成播放
- • 一段代码中使用了sqlite有部分不理解的地方,求老
- • python异常的问题有代码求指教,关于raise语句
- • 求分析django工程目录里找不到导入模块原因
- • 关于web.py性能优化方法大家闲聊讨论下
- • 请大家荐些适合新手练习python开源项目学习学习
- • 求大牛看下python源码中的__init__()作用是什么
- • Flask操作结束后,要回到触发请求页面需要怎么设
必知PYTHON教程 Must Know PYTHON Tutorials
- • python 解释器
- • python idle
- • python dir函数
- • python 数据类型
- • python type函数
- • python 字符串
- • python 整型数字
- • python 列表
- • python 元组
- • python 字典
- • python 集合
- • python 变量
- • python print
- • python 函数
- • python 类定义
- • python import
- • python help
- • python open
- • python 异常处理
- • python 注释
- • python continue
- • python pass
- • python return
- • python global
- • python assert
- • python if语句
- • python break
- • python for循环
- • python while循环
- • python else/elif
- • lambda匿名函数
必知PYTHON模块 Must Know PYTHON Modules
- • os 模块
- • sys 模块
- • re 正则表达式
- • time 日期时间
- • pickle 持久化
- • random 随机
- • csv 模块
- • logging 日志
- • socket网络通信
- • json模块
- • urlparse 解析URL
- • urllib 模块
- • urllib2 模块
- • robotparser 解析
- • Cookie 模块
- • smtplib 邮件
- • Base64 编码
- • xmlrpclib客户端
- • string 文本
- • Queue 线程安全
- • math数学计算
- • linecache缓存
- • threading多线程
- • sqlite3数据库
- • gzip压缩解压
最新内容 NEWS
- • Python程序员解决棘手问题的常用库
- • 求助关于restfull api接口几个问题
- • qiniu pythonsdk提示ImportError错误求解
- • 问一个关于Hadoop Python中读写文件统计分析
- • 求问str()同__str__原理上有什么不同,分别在
- • 大神帮忙看下20行的python代码,文件io和数
- • python 爬虫爬wiki 报错 [Errno 65] No route to
- • python续点上传问题None bad token...
- • python3环境下文本中超链接出错,要如何修
- • Python环境保存操作思路问题求助
图文精华 RECOMMEND
-
Python程序员解决棘手问题的常用库
-
求问str()同__str__原理上有什么不同
-
scrapy框架里面用link extractor怎么能
-
python {}.fromkeys创建字典append添加操
-
python3 类型Type str doesn't support th
-
python里面为什么系统的时区是东八
热点文章 HOT
- 学习Python有什么好的书籍推荐?
- Python匿名函数 Lambda表达式作用
- Python与Java、C、Ruby、PHP等编程语言有什么
- Python 正则中文网页字符串提取问题
- 如何为实时性应用存取经纬度?django my
- 想用python做个客户端,在二维码登录这个地
- 有让IDE可识别Python函数参数类型的方法吗
- Python字符串转换成列表正则疑问