Pythonic:递归、回溯等5种方法生成不重复数字整数

问题描述：从0到9这10个数字任选3个不重复的数字，能构成哪些三位数？

So easy！看到这样的问题，很多人会写出类似（注意，只是类似，我为了使得本文几个函数具有相同的调用形式，给demo1和demo2加了点多余的东西）下面这样的代码：

def demo1(data, k=3):

    '''从data中选择不同的3个数字组成三位数'''

    assert k == 3, 'k must be 3'

    for i in data:

        if i == 0:continue

        ii = i*100

        for j in data:

            if j == i:continue

            jj = j * 10

            for k in data:

                if k!=i and k!=j:

                    print(ii + jj + k)

OK，这段代码确实能够满足题目的功能要求，但是好像有个小问题：在上面的代码中，先选择i，然后再依次选择j和k，如果选到重复数字就“放回去”重新选，有没有办法可以保证在选择的时候避免选到已有的数字呢？答案是确定的，请看下面的代码（感谢浙江温州永嘉县教师发展中心应根球老师提供的思路）：

def demo2(data, k=3):

    '''妙用集合实现同样功能'''

    assert k == 3, 'k must be 3'

    data = set(data)

    for i in data:

        if i == 0:continue

        ii = i * 100

        for j in data - {i}:

            jj = j * 10

            for k in data - {i, j}:

                print(ii + jj + k)

上面这段代码首先把给定的数字序列转换为集合，然后每选择一个数字之后就把这个数字从集合中拿走，巧妙地避免了选择重复数字。

现在问题又来了：如果题目稍微修改一下，让选择4个不重复的数字组成4位数，肿么办？修改上面的代码，再增加一个嵌套的循环来选择第4个数？要是让选择8个呢？再改？很明显，这是不行的，做不到自适应的代码绝对不是好代码。

如果循环次数没法提前确定，如何才能做到选择任意个（当然小于等于10）不重复数字来组成整数呢？答案是递归和回溯。下面来看看这两段代码：

def demo3(data, k, s=()):

    '''回溯法'''

    if len(s) == k and s[0] != 0:

        print(eval(''.join(map(str,s))))

    res = []

    for item in data:

        if item in s:

            continue

        for r in demo3(data, k, s+(item,)):

            res.append(r)

    return res

def demo4(data, k, s=()):

    '''递归法'''

    if len(s) == k and s[0] != 0:

        print(eval(''.join(map(str,s))))

    else:

        for item in data:

            if item not in s:

                demo4(data, k, s+(item,))

晕不晕？回溯法和递归法往往以代码简洁著称，但是在很多时候确实也比较难理解的。难道就真的没有更好的办法了吗？既然选择了Python，那就让我们写一个下面这样Pythonic的代码，不用递归，也不用回溯，并且能够实现选择任意个数字来组成整数，OMG！

def demo5(data, k):

    '''使用枚举组合数的方法产生任意位数的数字'''

    from itertools import permutations

    r = permutations(data, k)

    for item in r:

        if item[0] != 0:

            print(eval(''.join(map(str, item))))

然后就可以调用上面的函数来生成整数了：

data = range(10)

demo5(data, 5)