算法请教

bleem1998

UID: 272
帖子: 63
积分: 144
在线时间: 5 小时

1^# bleem1998 发表于 2007-01-11 14:12

算法请教

[Copy to clipboard] [ - ]

CODE:

把一个字符串中所有字符的所有可能的组合打印出来(字符串中没有重复的字符)
不考虑字符顺序（'123'和'312'是一样的）

很久很久以前有人问了这个问题
然后有人写了下面这个程序
函数虽然短
但是用到了一种我没见过的递归
哪位高手能解释一下这个算法吗
我想了很久没想通
bow!!

[Copy to clipboard] [ - ]

CODE:

def func(str,prefix):
      if len(str) == 0:
            print prefix,
            return
      func(str[1:],prefix+str[0])
      func(str[1:],prefix)

func('123','')

ttvast

UID: 15420
帖子: 51
积分: 117
在线时间: 3 小时

2^# ttvast 发表于 2007-01-11 15:56

递归的层次依次为：
包含1的序列和不含1的序列
包含2的序列和不含2的序列
包含3的序列和不含3的序列

3个层次连接起来，就是所有可能的组合了

bleem1998

UID: 272
帖子: 63
积分: 144
在线时间: 5 小时

3^# bleem1998 发表于 2007-01-11 16:38

谢谢
大致明白了是怎么回事
可还是理解的不够彻底
没有抓到原作者解决问题的算法关键啊
如果能像理解快速排序算法一样理解这个算法就好了

bleem1998

UID: 272
帖子: 63
积分: 144
在线时间: 5 小时

4^# bleem1998 发表于 2007-01-11 16:43

有点开窍了
如果用二叉树的观念去想这个问题就得到了合理的解释
原始字符串在树的根节点
然后就如二楼所说的
每个节点的两个儿子分别代表‘包含’和‘不包含’某个字符
如此分下去

终于搞明白了
bow~~~