python 回溯法 子集树模板 系列 —— 4、数字组合问题

简介: 问题找出从自然数1、2、3、...、n中任取r个数的所有组合。例如,n=5,r=3的所有组合为:1,2,31,2,41,2,51,3,41,3,51,4,52,3,42,3,52,4,53,4,5分析换个角度,r=3的所有组合,相当于元素个数为3的所有子集。

问题

找出从自然数1、2、3、...、n中任取r个数的所有组合。

例如,n=5,r=3的所有组合为:
1,2,3
1,2,4
1,2,5
1,3,4
1,3,5
1,4,5
2,3,4
2,3,5
2,4,5
3,4,5

分析

换个角度,r=3的所有组合,相当于元素个数为3的所有子集。因此,在遍历子集树的时候,对元素个数不为3的子树剪枝即可。

注意,这里不妨使用固定长度的解。

直接套用子集树模板。

代码


'''数字组合问题'''

n = 5
r = 3
a = [1,2,3,4,5] # 五个数字

x = [0]*n # 一个解(n元0,1数组) 固定长度
X = []    # 一组解

def conflict(k):
    global n, r, x
    
    if sum(x[:k+1]) > r: # 部分解的长度超出r
        return True
    
    if sum(x[:k+1]) + (n-k-1) < r: # 部分解的长度加上剩下长度不够r
        return True
        
    return False # 无冲突

    
# 套用子集树模板
def comb(k): # 到达第k个元素
    global n, x, X
    
    if k >= n:  # 超出最尾的元素
        #print(x)
        X.append(x[:]) # 保存(一个解)
    else:
        for i in [1, 0]: # 遍历元素 a[k] 的两种选择状态:1-选择,0-不选
            x[k] = i
            if not conflict(k): # 剪枝
                comb(k+1)


# 根据一个解x,构造对应的一个组合
def get_a_comb(x):
    global a
    
    return [y[0] for y in filter(lambda s:s[1]==1, zip(a, x))]
    
# 根据一组解X,构造对应的一组组合
def get_all_combs(X):
    return [get_a_comb(x) for x in X]


# 测试
comb(0)
print(X)
print(get_all_combs(X))

效果图

img_a60d6e3ff16ebae89cb77ee7c8d6ebd5.jpg

目录
相关文章
|
Python 机器学习/深度学习 安全
python 回溯法 子集树模板 系列 —— 19、野人与传教士问题
问题 在河的左岸有N个传教士、N个野人和一条船,传教士们想用这条船把所有人都运过河去,但有以下条件限制: (1)修道士和野人都会划船,但船每次最多只能运M个人; (2)在任何岸边以及船上,野人数目都不能超过修道士,否则修道士会被野人吃掉。
1386 0
|
Python 数据可视化
python 回溯法 子集树模板 系列 —— 1、8 皇后问题
问题 8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 分析 为了简化问题,考虑到8个皇后不同行,则每一行放置一个皇后,每一行的皇后可以放置于第0、1、2、...、7列,我们认为每一行的皇后有8种状态。
969 0
|
14天前
|
人工智能 数据可视化 数据挖掘
探索Python编程:从基础到高级
在这篇文章中,我们将一起深入探索Python编程的世界。无论你是初学者还是有经验的程序员,都可以从中获得新的知识和技能。我们将从Python的基础语法开始,然后逐步过渡到更复杂的主题,如面向对象编程、异常处理和模块使用。最后,我们将通过一些实际的代码示例,来展示如何应用这些知识解决实际问题。让我们一起开启Python编程的旅程吧!
|
13天前
|
存储 数据采集 人工智能
Python编程入门:从零基础到实战应用
本文是一篇面向初学者的Python编程教程,旨在帮助读者从零开始学习Python编程语言。文章首先介绍了Python的基本概念和特点,然后通过一个简单的例子展示了如何编写Python代码。接下来,文章详细介绍了Python的数据类型、变量、运算符、控制结构、函数等基本语法知识。最后,文章通过一个实战项目——制作一个简单的计算器程序,帮助读者巩固所学知识并提高编程技能。
|
24天前
|
机器学习/深度学习 数据挖掘 程序员
探索Python编程:从基础到进阶的旅程
在这篇文章中,我们将一同踏上一场激动人心的Python编程之旅。无论你是初学者还是有一定经验的开发者,这里都有适合你的内容。文章分为三个部分:首先是“启程前的准备”,我们会介绍Python的安装和基本工具;其次是“旅途中的风景”,将通过实际代码示例深入探讨Python的核心概念;最后,“到达目的地”会带你了解如何将所学知识应用于实际项目。让我们开始吧!
|
20天前
|
存储 索引 Python
Python编程数据结构的深入理解
深入理解 Python 中的数据结构是提高编程能力的重要途径。通过合理选择和使用数据结构,可以提高程序的效率和质量
131 59
|
13天前
|
小程序 开发者 Python
探索Python编程:从基础到实战
本文将引导你走进Python编程的世界,从基础语法开始,逐步深入到实战项目。我们将一起探讨如何在编程中发挥创意,解决问题,并分享一些实用的技巧和心得。无论你是编程新手还是有一定经验的开发者,这篇文章都将为你提供有价值的参考。让我们一起开启Python编程的探索之旅吧!
38 10
|
16天前
|
机器学习/深度学习 人工智能 Java
Python 语言:强大、灵活与高效的编程之选
本文全面介绍了 Python 编程语言,涵盖其历史、特点、应用领域及核心概念。从 1989 年由 Guido van Rossum 创立至今,Python 凭借简洁的语法和强大的功能,成为数据科学、AI、Web 开发等领域的首选语言。文章还详细探讨了 Python 的语法基础、数据结构、面向对象编程等内容,旨在帮助读者深入了解并有效利用 Python 进行编程。
|
15天前
|
机器学习/深度学习 人工智能 数据挖掘
探索Python编程的奥秘
在数字世界的海洋中,Python如同一艘灵活的帆船,引领着无数探险者穿梭于数据的波涛之中。本文将带你领略Python编程的魅力,从基础语法到实际应用,一步步揭开Python的神秘面纱。
34 12
|
14天前
|
IDE 程序员 开发工具
Python编程入门:打造你的第一个程序
迈出编程的第一步,就像在未知的海洋中航行。本文是你启航的指南针,带你了解Python这门语言的魅力所在,并手把手教你构建第一个属于自己的程序。从安装环境到编写代码,我们将一步步走过这段旅程。准备好了吗?让我们开始吧!