玩蛇网提供最新Python编程技术信息以及Python资源下载!

求大家帮解一道关于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互助QQ群,欢迎加入-->: 106381465 玩蛇网Python新手群
修订日期:2017年05月24日 - 19时22分40秒 发布自玩蛇网

您现在的位置: 玩蛇网首页 > Python问题解答 > 正文内容
我要分享到:

必知PYTHON教程 Must Know PYTHON Tutorials

必知PYTHON模块 Must Know PYTHON Modules