python实现排列组合，官方代码+自己写

想象一下，现在有A、B、C、D、E五个人中需要抽出三个人去比赛，请问有多少种参赛阵容？
这是一个简单的排列组合问题，结果如下：
ABC-ABD-ABE-ACD-ACE-ADE
BCD-BCE-BDE
CDE
聪敏的你也许已经看出来了一点规律

好了，现在我们用python自己实现个寂寞

先分析一下，可以感觉出来这个方法是FILO。像是一个井盖，可以容纳三个人，A先下井，B跟着下井，C其次。因为容量为3，C需要立马出去，D进来，当然D后面还有E排队等着下矿。E出去后B出去靠边站，C下井当老二，又是新的一轮。当D当完老二后，A出栈，B入栈当老大又是新的一轮。
显然我们需要用到循环或者是递归。但是递归不仅不容易理解，而且很占内存。不过我都给他防回去了，因为我都没做出来😔。
我的思路是一个函数接受三个参数(list, num, ret),list为需要组合的对象们，num为每个组合的规模，ret是为了递归后写入新的数据，就是把ret当作一个栈来用。搞了两个小时，愣是搞不明白。。。。。。。。。
我一直在进行递归方向的尝试，而且还在for循环里递归，最终觉得递归不是一个好的方法，是时候放弃了。

最后我顿悟看了官网手册

下面的中文注释是我的理解

def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)#强制可迭代对象对象成为一个稳定的元组，I suppose...
    n = len(pool) #获取元组长度
    if r > n: #如果小组最低数量大于总人数，则无意义
        return #并非返回None，因为下文有yield，所以返回的是个空的生成器
    indices = list(range(r)) #一个长度为要求小组长度的索引
    yield tuple(pool[i] for i in indices) #把前r个作为一个小组来
    while True: #开始循环输出不同的索引组合
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1 #for循环结束后，i的值仍未被GC回收，所以可以使用i    
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

看到到后我发现，自己好笨啊，没有直接从数字出发。
其实上面的while循环部分就干了一件事，对索引进行排列组合。其实我们唯一需要做的就是从一个索引列表如：[0, 1, 2, 3, 4]中输出以下索引：
[0, 1, 3]
[0, 1, 4]
[0, 2, 3]
[0, 2, 4]
[0, 3, 4]
[1, 2, 3]
[1, 2, 4]    
[1, 3, 4]
[2, 3, 4]

那么搞清楚了方法，具体的代码就容易了然而并没有搞清楚那个whil循环


只能说那些人太聪明了。自己感觉python简单只不过是因为无数前人在努力，不说了，日后填坑






评论

发表评论

此博客中的热门博文

我们应该满足欲望吗？——谈谈为什么感觉不到幸福

一、现代生活VS原始生活     在看米哈伊的大作《心流》时，读到了一段话： 古波斯的居鲁士大帝有一万名厨子替他调理珍馐，而国内老百姓却濒临饥饿边缘。现在发达国家人人都可以取得最罕见的食谱，仿制古代帝王的御膳，但大家因此就满足了吗？      很明显，这段话意在表明所谓的文明进步并没有让我们人类得到满足。不约而同，我依稀记得尤瓦尔·赫拉利在《人类简史》中也表达了类似的观点，即人类学会种地养牲畜进而步入农业文明，但满足饥饿和安全的欲望并没有让我们更幸福，反而把我们套牢了，就像【棘轮】一样，一旦走上了这条路就只能继续走下去，但这条路并没有让我们引向幸福。      这不禁让我思考一个问题， 我们应该满足欲望吗？ 比如想要更充足的食物、更快的交通、更温暖舒适的居所和更长的寿命等。 需要再次提醒的是，本文所讨论的欲望并非杀人、强奸那样邪恶欲望，更多的是一些生物本能和较为【中性的欲望】，比如吃饱穿暖等，更为关注的是我们个人，而不是我们和他人之间的关系。      为了便于分析，我们不妨假设每个人的目的只有一个，那就是让我们自己变得更加幸福。但是什么是幸福呢？我很难给幸福下一个让所有人都满意的定义，其实这也是没有必要的。有许多概念，我们都无法下一个完美的定义，比如说民主，但这并不妨碍我们对其进行讨论。定义幸福就像【大象测试】一样，我无法给你说幸福是什么，但是你能感觉到幸福。既然 人生的目的就是获得尽可能多的幸福 ，那么如果满足欲望能够让我们得到幸福，那么我们就应该做，反之则不然。所以 现在的问题就是满足欲望能够让我们得到幸福吗？     直观来说， 这一问题并不是很好回答，不过我们能通过一种简单的方法来进行回答。现代社会是原始人类不断满足其欲望的发展结果，我想这一点应该没有人会反对吧？那么如果我们想要回答我们应不应该满足欲望，只需要把我们的现代社会和原始社会加以比较，看二者谁更为可取，那么就可以间接给出答案。当然，所有人类并不会给出一个一致的答案，总是会有多数和少数，多数的选择也并不恒等于【应然】，但出于对民主制度的尊重和对人类理性选择的信任，笔者选择将多数的选择与【应然】相挂钩，即只要大多数人认为现代社会更为可取，那么欲望就是应该被满足的。 ...
阅读全文

浅谈公民、国家、政府和政党的区别

我们平日里见到都是如何区分人民、国家和政府、政党，但我觉得这种问题本身就不太对劲。 首先，什么是人民？什么又是公民？ 公民这个好理解，就是各国法律中明确规定的符合条件的那些人，援引中华人民共和国国籍法第四条 父母双方或一方为中国公民，本人出生在中国，具有中国国籍。法律对什么是公民做出了明确的规定。 什么是人民呢？你找不出一个口径一致的定义。不信你试试。其实人民和百姓的意思差不多，大概指那些劳动群众。不过问题又来了，什么是劳动群众？这个问题一个套一个，归根结底是因为这个词汇就是政治词汇，而不是法律上的词汇。 为什么我提倡讲公民，而非讲人民？ 正是因为人民的定义太模糊啦。记得好像是周孝正老师说过，人就是人，人家骂你狗，但你还是人；人民就不一样了，今天你是人民，明天你就可以是人民的敌人。我觉得说的很对。比如刘少奇，今天你是为人民服务的国家主席，明天就可以是叛徒、内奸、工贼。也就是说是不是人民，你说了不算，谁说了算？别问我我不知道。但是公民呢？今天他是中国公民，明天他也是中国公民。 如果一个社会只讲人民，不讲公民，这样是很容易出问题的。是不是公民大家心里都有数，但是不是人民这个就不好说了。如果上面说这个人不是公民，大家打死他，显然上面不对劲。但如果上面说这个人不是人民，再“拿出”点激昂澎湃的证据，一群人马上就被煽动起来了。这样的社会缺乏自我纠正机制，很容易被利用和煽动，只会放大上层的不稳定。也就是说很容易走上纳粹的道路滴 公民和国家什么区别呢？ 公民身份是由一个国家的法律规定的，所以国家变了、法律变了，自然自己的公民身份也就变了。比如法国近代历史，天天成立国家，所以每天都是新的国家公民，但换来换去还是一个人。公民组成了国家，国家法律规定了公民，好比同样都是一块地，张三李四谁强所有权就是是谁的。地，张三的地，张三这些概念对应的就是人、x国公民(x国的人)和x国。我理解的就这样。 国家和政府什么区别呢？ 政府就是朝廷，说白了就是法律规定的一群治理国家的人。好比是小区与物业的关系，你说物业一定会维护小区的利益吗？未必，物业只会维护物业自身的利益。这就可以说明为什么中国历史经常出现一些昏君不是穷兵黩武打败仗，就是劳民伤财修东西，因为国家的利益并不是他个人的利益。 政府和政党什么区别呢？ 政党就是一群政治看法相近的人的组合。比如我主张改革，你也主张改革，那咱俩就可以组织个政党，比如名...
阅读全文

should we satisfy our desire? Yes, it's justified

  Note that "desire" here is in a narrow and neutral sense, like more delicious food, more money, not the scope that more killing or salves. Nowadays, people often complains that "Life sucks, I'd rather like to be a primitive". Just like Mihaly Csikszentmihalyi mentioned in his book Flow , When Cyrus the Great had ten thousand cooks prepare new dishes for his table, the rest of Persia had barely enough to eat. These days every household in the “first world” has access to the recipes of the most diverse lands and can duplicate the feasts of past emperors. But does this make us more satisfied? It seems that satisfying ours desire hasn't made us happy, so what't your argument onto this one? Should we satisfy our desire? My argument as follows to this is positive. To answer this question better, let us presume that the only goal of our life is to get more happiness . But what is happiness? It's hard for me to define to meke all of us accepts it and that...
阅读全文