python 组合排列,python列表排序算法
array的问题是从指定数量的元素中检索指定数量的元素并排序。组合的问题是从N个不同的数中选出M个数，输出所有的组合方法。这两个问题是经典回溯算法的问题。先解决排列问题，再解决组合问题。
假设你需要排列四个数[1，3，4，5]。我们知道第一个数字有四个选择，第二个数字有三个选择，第三个数字有两个选择，第四个数字有一个选择。你其实可以不用回溯算法写代码。伪代码如下。
nums=[ 1，3，4，5 ]
对于数字中的：
nums1=不带的nums
解决方案1=[ a]
对于nums1中的b:
nums2=不带b的nums1
解决方案2=解决方案1。追加(b))
对于nums2中的c:
nums3=不带c的nums2
方案3=方案2。追加(c)
对于nums3中的d:
解决方案4=解决方案3。追加(c)
打印(解决方案4)。
上述伪代码的思想是从列表中排除已经使用的选择，并使用for循环继续遍历下一个位置的数量。这样做的缺点是代码很麻烦，写代码前必须知道nums的长度。用回溯算法来解决这个问题就没有这个缺点了。
定义置换(nums)方法。输入nums数组。permute(nums)方法输出nums中的所有数字数组。例如，permute ([1，2，3])的输出：
[ 1,2,3 ],[ 1,3,2 ],[ 2,1,3,1 ],[ 3,1,2 ],[ 3,2,2 ],[ 3,2,2,1 ] ]
置换(nums)方法的思想如下。
选择第一个位置的数字，称为X；
使用permute(nums)方法得到剩余数字的所有排列；
将x放在这些数组的第一个位置。保存答案；
回到第一步，改X；
试完所有的X，输出答案。
permute(nums)方法的边界条件是，如果nums数组为空，则将当前数组添加到结果集中并返回。
以[1，2，3，4]为例。
一开始，我只关心初始位置的数量。总共有四个选择。我们在这四个选项之间来回切换，第一次选择1。
我们知道从1开始的序列组合等于1“[2，3，4]的序列组合”。此时，如果再次调用permute(nums)方法并传递[2，3，4]，就会得到“[2，3，4]数组组合”。
获得6个“[2，3，4]排列组合”后，在数组中加1，放在第一个位置。
回到第一步，将第一个位置的编号替换为2。
递归步骤如图1所示。最初递归到底部时保存的组合是[1，2，3，4]。看看接下来的步骤。
图1:第一个结果
如图，我们回到三楼。第三层次，三选四。我们试过3次。现在是4。将4放在第三个位置，并将剩余的数字3作为参数传递给第四级。至此，获得了第二数组[1，2，4，3]的组合。
图2:第二个结果
如图3所示，我们再次回到三楼。三楼的两个选项，33543和4，因为试过了，会继续退到二楼。二楼的选择是234。尝试从3开始继续。把3放在第三个位置。把剩下的号码——2和4传到三楼。然后，把2放在第三个位置，把4给第四层。第三个结果是[1，3，2，4]。
图3:第三个结果
重复以上步骤得到顺序：[1，3，4，2]，[1，4，2，3，2]，[2，1，3，4]，…，[4，3，2，1]。
序列问题代码：
对num排序并返回所有组合
defpermute(nums，solution=[]):
If nums: #边界条件
结果追加(解决方案)
Return #返回
forIinrange(Len ) nums):
New solution=solution [nums [I]] #将nums中的数字按顺序排列，放在下一个组合位置。
新列表=nums [0: I] nums [I 1:] #新列表包含除nums[i]以外的所有号码
继续使用permute(newlist，newSolution) #数组
新列表中的数字
res=[]
置换([1，2，3，4])
解就是当前的排列组合。当初，解=[]。放置第一个数字后，解=[1]，放置第二个数字后，解=[1，2]。
注意，变量解只存在于当前层中。比如我们从第一层传到第二层，第二层的解和第一层的解同名，但不是同一个变量。当第二层的解等于[1，2]时，第一层的解仍然是[1]。主动改变的是newSolution，也就是传入下一层的数组。
如图4所示，每一层的新解就是下一层的解。
图4:解决方案和新解决方案之间的关系
比如我们从第四层回到第三层，第三层的解不变，还是[1，2]，但是第三层的For循环把newSolution改成了[1，2，4]。
虽然图4中没有显示，但是当我们再次递归到第四层时，第四层会放弃原来的解和newSolution，在内存中重新声明一个名为solution的变量和一个名为newSolution的变量，然后将解赋给[1，2，4]。每一次进步，我们都重新创造变量，赋予它们新的值。但是每次回去，因为方法不变，变量不变。
因为解是“一次性”变量，所以我们不必深度复制解并添加到结果列表中，只需使用append()方法即可。同理，每层的num只存在于当前层。当我们从一层递归到另一层时，每一层的num都是独立存在的，而newList是变化的。新列表决定了下一层的num是什么，只有当新列表改变并且方法被重新传递到下一层时，num才会改变。
接下来，解决组合问题。假设我们需要从[1，2，3，4]中选择2个数字。我们知道有六种选择：[1，2]、[1，3]、[1，4]、[2，3]、[2，4]、[3，4]。
我们将定义组合(nums)方法。输入nums数组，combination()方法输出nums中数字的所有排列。例如，permate ([1，2，3，4])输出[[1，2]，[1，3]，[1，4]，[2，3]，[2，4]，[3，4]]。
排列问题和组合问题的性质非常相似。在组合问题中，我们也可以只关心第一个数，然后让递归的方法得到其余数的组合。
步骤如下：
选择第一个位置的数字，称之为x。
使用combination()方法获得剩余数字的组合。
将X放在第二步中获得的数组的第一个位置。保存答案。
回到第一步，改x。
试完所有的X，输出答案。
如果传递给combination()方法的nums数组为空，则停止递归，并将当前排列添加到结果集中。
比如第一步，我们只关心在[1，2，3，4]中选一个数。有四个选择。当我们选择1时，我们知道答案等于1加上“在[2，3，4]中选择1个数字的组合”。同样，当我们选择第一个数字为2时，答案等于2加上“[1，4]
combination()方法和permute()方法的区别在于第二步“余数”的定义。在permute()方法中，“剩余数”是除x之外的所有数，但是在combination()方法中，“剩余数”是x之后的所有数，比如nums是[1，2，3，4]，当前数是2，那么permute()方法的“剩余数”是[1，3，4]，而combination()方法的“剩余数”是[3，4]。
这是因为用过的数在组合题中是不能用的。在排列问题中，数字的位置是有意义的，但在组合问题中，数字的位置是没有意义的。比如[2，1]和[1，2]是两种不同的排列，但却是同一种组合。
代码如下：
#nums是要组合的数字列表，solution是当前组合，n是所选数字的个数。
#输出所有组合
定义组合(数字，解决方案，n):
If==0: #边界条件
结果追加(解决方案)
返回
对于范围内的I(len(nums)):
NewSolution=solution [nums[i]] #将nums中的数字依次放入新组合NewSolution中。
List=nums [I 1:] #剩余号码
组合(新列表，新解决方案，n-1) #从剩余的数字中选择n-1个数字。
res=[]
组合([1，2，3，4，5]，[]，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]]
组合问题代码和排列问题代码有两个区别。
combination()方法有一个额外的参数N，用来表示我们需要选择几个数字。combination()方法每调用一次自身，n就减1。
newList的定义不再是nums[0:i] nums[i 1:]，而是nums[i 1:]。这是因为我们不能重复使用已经使用过的号码。让我们浏览一下代码，理解为什么要这样定义newList。
我们第一次进入组合()方法。组合()的参数为nums=[1，2，3，4]，solution=[]，n=2。
对于范围(n)中的I:# n=2，i=0
new solution=solution[nums[I]]# new solution=[][1]=[1]
newList=nums[i 1:]#newList=[2，3，4]
combination(newList，newSolution，n-1) #combination([2，3，4]，[1]，1)
目前选择了一个号码——1。接下来，在[2，3，4]中选择一个数字。
第二次输入组合()方法。组合()的参数为：nums=[2，3，4]，solution=[1]，n=1。
对于范围(n)中的I:# n=1，i=0
新解决方案=解决方案[nums[I]]#新解决方案=[1] [2]
List=nums [i 1:] # newlist=[3，4]而不是[1，3，4]
combination(newList，newSolution，n-1) #combination([3，4]，[1，2]，0)
目前的数字是2。当前选择的两个数字是1和2。新列表是[3，4]而不是[1，3，4]。如果是[1，3，4]，逻辑上就说不通了，因为1已经在组合里了，所以不再可选。
第三次输入组合()方法。combination()方法得到的参数是nums=[3，4]，solution=[1，2]，n=0。
如果n==0: #n=0
res.append(solution) #res=[[1，2]]
返回
满足边界条件并将当前组合添加到res列表。回到上次调用combination()方法的地方。
combination()方法的当前参数为nums=[2，3，4]，solution=[1]，n=1。
继续未完成的主循环。
对于范围(n)中的I:# n=1，i=1
新解决方案=解决方案[nums[i]] #新解决方案=[1] [3]
new list=nums[I 1:]# new list=[4]=[4]而不是[1，2，4]
combination(newList，newSolution，n-1) # combination([4]，[1，3]，0)
目前的数字是3。当前选择的两个数字是1和3。NewList是[4]而不是[1，2，4]。因为组合中已经有4，所以不再可选。
如你所见，newList只选择当前号码之后的号码，因为之前的号码都已经被使用过了，一个号码在组合问题中是不能重复使用的。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。