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)

本文内容针对《Python程序设计基础》和《Python程序设计》(第2版)(董付国编著,清华大学出版社)两本教材中的例3-13进行拓展。

原文发布于微信公众号 - Python小屋(Python_xiaowu)

原文发表时间:2016-08-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C#

关于.NET参数传递方式的思考

    年关将近,整个人已经没有了工作和写作的激情,估计这个时候很多人跟我差不多,该相亲的相亲,该聚会喝酒的聚会喝酒,总之就是没有了干活的心思(我有很多想...

24590
来自专栏逸鹏说道

我为NET狂面试题-基础篇-答案

面向过程: 答案:图片只贴核心代码,完整代码请打开解决项目查看 (答案不唯一,官方答案只供参考,若有错误欢迎提出~) 99乘法表 https://githu...

377130
来自专栏工科狗和生物喵

【计算机本科补全计划】C++ Primer:指针和const限定符

正文之前 今天下午看了一下午的计算机组成与设计,结果好死不死的看到了设计部分--处理器的设计。天哪,我现在还只是一个准备给人装一台电脑做实验田的家伙,连用都不咋...

28940
来自专栏chenjx85的技术专栏

leetcode-35- Search Insert Position

22730
来自专栏C/C++基础

C++中函数重载、隐藏、覆盖和重写的区别

C++规定在同一作用域中,同名函数的形式参数(指参数的个数、类型或者顺序)不同时,构成函数重载。

26020
来自专栏数说工作室

统计师的Python日记【第1天:谁来给我讲讲Python?】

统计师的Python日记 【第一天】谁来给我讲讲Python? 我是一名数据分析师,曾在漫长的岁月中使用SAS、Matlab和R(使用频率依次递减)。其他如...

48970
来自专栏苦逼的码农

Unicode与UTF-8的区别

要弄清Unicode与UTF-8的关系,我们还得从他们的来源说起,下来我们从刚开始的编码说起,直到Unicode的出现,我们就会感觉到他们之间的关系

97020
来自专栏华章科技

从Zero到Hero,一文掌握Python关键代码

首先,什么是 Python?根据 Python 创建者 Guido van Rossum 所言,Python 是一种高级编程语言,其设计的核心理念是代码的易读性...

9230
来自专栏潇涧技术专栏

Python Data Structures - C2 Sort

参考内容: 1.Problem Solving with Python Chapter5: Search and Sorting online_link ...

9610
来自专栏编程

自学Python笔记(二)

作为最最基础的初学者,尤其是面对中小学生学习Python我想大概了解一下Python,能编个小程序,能看懂一般的程序就可以,如果想深一步的学习还是需要静下心来好...

27270

扫码关注云+社区

领取腾讯云代金券