程序员必备算法 |
您所在的位置:网站首页 › 排列组合分组公式应用 › 程序员必备算法 |
暴力求解(不可取,不可取) 相信很多初入门的小伙伴首先想到的就是就是直接通过嵌套多个for循环去遍历不就好了,只要不相等就直接输出,就像下面这样: def force(): data = "abc" for i in range(len(data)): for j in range(len(data)): for k in range(len(data)): if data[i] != data[j] and data[j] != data[k] and data[k] != data[i]: print(data[i],data[j],data[k]) if __name__ == '__main__': force() /*输出 a b c a c b b a c b c a c a b c b a */看上去还可以的样子,不过这样有几个坏处,如果不想全排列abc了,而是想对abcd进行全排列了,那么我们必须要修改源代码增加一个for循环,而且如果排列的数很多的话,那这个循环也太多了吧。 递归求解 上面这种解法实在有点不优雅,那么我们如何在不修改源码的情况下就可以求出所有的排列组合情况呢?我们先来看张图: 对于abc的排列,当我们进行排列时,可以先考虑第1位可能有哪些情况,如上图所示有a,b,c三种情况,然后再对后面的两位进行排列,采用相同的思路,所以我们可以很容易的就通过递归实现全排列了。 def rank(data, step): if len(data) == step+1: print(data) return else: for i in range(step, len(data)): data[step], data[i] = data[i], data[step] //让当前首位依次为后面的每一个数 rank(data, step + 1) //递归后面的情况 data[step], data[i] = data[i], data[step] if __name__ == '__main__': data = list("abc") rank(data, 0)运行上面的代码,可以得到和上面暴力求解一毛一样的结果,且这次如果需要对其他情况进行全排列不需要再修改源代码,且只用了一个循环(虽然用递归效率还不如多个循环^-^),不过至少代码看上去还是很优雅的。 解决全排列的重复问题 细心的小伙伴肯定会发现,上面的代码其实是有问题的,如果排列的数组中有重复的元素那么结果中也会有重复的排列,这是我们不希望看到的。那么我们如何解决这个问题呢? 要想解决这个问题,我们首先需要知道这个问题是怎么来的,还是参考刚刚的图,我们稍微修改下: 就拿cac这个举个栗子: 当以第一个c为开头时,我们需要对ac进行全排列,没问题 当以a为开头时,我们需要对cc进行全排列,没问题 当以第二个c为开头时,我们需要对ca进行全排列,这就有问题了,ac和ca的全排列不就一样的嘛,而且开头也一样,这个肯定就会有重复了呀,我们对源码稍加修改下: def is_equal(data,left,right): #判断left到当前right是否有相等的,如果有说明之前已经对这 for i in range(left,right): #个进行过全排序了 if data[i] == data[right]: return True return False def rank(data, step): if len(data) == step+1: print(data) return else: for i in range(step, len(data)): if is_equal(data,step,i): #加一个判断 continue else: data[step], data[i] = data[i], data[step] rank(data, step + 1) data[step], data[i] = data[i], data[step] if __name__ == '__main__': data = list("bcc") rank(data, 0)ok,这样运行上面的代码的就不会有重复的问题了,这里可能需要小伙伴们多思考下了,不过还是很简单的。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |