算法中的排列组合问题
一、全排列：
算法：
递归：
先确定第一个元素，对后面的全排列；
将后面元素逐渐与第一个交换，然后对除第一个之外的进行全排列；
代码：直接考虑了重复元素的情况
package main
import "fmt"
var (
inputs []int
)
func main() {
inputs =append(inputs, 3, 1,1, 2)
perm(0, len(inputs))
}
func perm(m, nint) {
switch {
case m == n:
for i :=0; i < n; i++ {
fmt.Print(inputs[i], " ")
}
fmt.Print("\n")
case m < n:
for i := m; i < n; i++ {
if !needSwitch(m, i) {
continue
}
inputs[m], inputs[i] = inputs[i], inputs[m]
perm(m+1, n)
inputs[m], inputs[i] = inputs[i], inputs[m]
}
}
}
func needSwitch(m, iint)bool {
for j := m; j < i; j++ {
if inputs[j] == inputs[i] {
return false
}
}
return true
}
字典序
思路：
1·、先对所有的元素进行一个排序，从小到大；
2、找到后面所有的字典序；
找下一个字典序的方法：
1、先找到第一个破坏逆序的元素i；
2、从元素i后面开始找到大于元素i的，最小的那个元素j；
3、对元素i和元素j进行互换；（此时i位置元素后面的元素为逆序的）
4、对i后面的逆序元素进行一个逆序，变为顺序的，此时出现的列表即为 序列的下一个字典序；
代码：golang
package main
import (
"fmt"
"sort"
)
var (
inputs []int
)
func main(){
inputs =append(inputs,1,2,3)
sort.Ints(inputs)
fmt.Print(inputs,"\n")
n :=len(inputs) -1
var kint
for ;nextPerm(n);k++{
fmt.Print(inputs,"\n")
}
}
func nextPerm(nint)bool{
var i,jint
for i = n;i>0;i--{
if inputs[i-1] < inputs[i]{
break
}
}
if i==0{
return false
}
for j= n;j>i-1 ;j--{
if inputs[j]> inputs[i-1]{
break
}
}
inputs[i-1],inputs[j] = inputs[j],inputs[i-1]
sort.Ints(inputs[i:])
return true
}
