求一则算法（python）

Question

罗列出qwerty被.分割的所有情况：

q.werty
q.w.erty
qw.erty
...
q.w.e.r.t.y

Answer 1

楼主 这个问题其实不难，首先肯定的是“点”是存在于两个字母之间的 ，那么你就想象有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/

Answer 2

具体的实现:

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 ''

Answer 3

来个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)]

Answer 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的列表解析*)