一道题，做做看

teebye

数组['a','b','c','d']

输出该数组的全组合

x2

http://bbs3.chinaunix.net/thread-1414423-1-1.html
http://bbs2.chinaunix.net/viewth ... ;page=1#pid10292091
http://bbs2.chinaunix.net/viewth ... p;page=1#pid9455917
有答案,不过算法都一样。

[ 本帖最后由 x2 于 2009-3-27 17:36 编辑 ]

teebye

原帖由 x2 于 2009-3-27 17:35 发表
http://bbs3.chinaunix.net/thread-1414423-1-1.html
http://bbs2.chinaunix.net/viewth ... ;page=1#pid10292091
http://bbs2.chinaunix.net/viewth ... p;page=1#pid9455917
...

看清楚题目，是组合，不是排列

alan_yang

原帖由 teebye 于 2009-3-27 17:41 发表

看清楚题目，是组合，不是排列

你先看清楚别人回复，答案就在他那几个连接里

daybreakcx

def output(s):     for i in range(1<<len(s)):         if (i):             temp=""             for j in range(len(s)):                 if (i&(1<<j)):                     temp=temp+s[j]             print(temp) s="abcd" output(s)

我来了，简单起见，当作字符串，希望不介意，输出如下：

a b ab c ac bc abc d ad bd abd cd acd bcd abcd

daybreakcx

我用了位操作，直接枚举就得了，省得费事，时间复杂度是O(n*(2^n))。

julyzergcn

http://groups.google.com/group/python-cn/browse_thread/thread/b4d2dcc10eadc374/624a28e1aadf0734?hl=zh-CN#624a28e1aadf0734

x2

原帖由 teebye 于 2009-3-27 17:41 发表

看清楚题目，是组合，不是排列

不好意思，看成排列了

x2

求数组['a','b','c','d']所有组合的演算步骤：
''
'' a
'' a b ba
'' a b ba c ca cb cba
'' a b ba c ca cb cba d da db dba dc dca dcb dcba

def subset(s):     v=[""]     for c in s:         v+=[ c + e for e in v]     return v print subset(['a','b','c','d'])[1:]

[ 本帖最后由 x2 于 2009-3-28 11:23 编辑 ]

x2

5楼的算法的演算步骤应该就是：

1    0001    a
2    0010    b
3    0011    ab
4    0100    c
5    0101    ac
6    0110    bc
7    0111    abc
8    1000    d
9    1001    ad
10  1010    bd
11  1011    abd
12  1100    cd
13  1101    acd
14  1110    bcd
15  1111    abcd