Among the number of instances of of n m is chosen
- 2020-06-07 04:37:20
- OfStack
An example of Go language implementation is presented in this paper. To share for your reference, specific as follows:
(1) Combination problem
Combination is a basic mathematical problem. The goal of this program is to output all combinations of m from n elements.
For example,2 Numbers are taken from [1,2,3], and 1 has 3 combinations: [1,2],[1,3],[2,3]. (the combination does not consider the order, that is, [1,2] and [2,1] belong to the same combination)
The idea of this program (from other great gods on the Internet) :
(1) Create an n array of elements. The value of the array element 1 means that it is selected, while the value of the array element 0 means that it is not selected.
(2) Initialize, set the first m elements in the array to 1, indicating that the first combination is the number of the first m elements.
(3) Scan the "10" combination of array element values from left to right, find the first "10" combination and turn it into the "01" combination, and move all the "1" on the left to the leftmost end of the array.
(4) When a combination of "10" is not found in a cycle, the last combination is obtained and the cycle ends.
For example, find the combination of 5 and 3:
1 1 1 0 0 //1,2,3
1 1 0 1 0 //1,2,4
1 0 1 1 0 //1,3,4
0 1 1 1 0 //2,3,4
1 1 0 0 1 //1,2,5
1 0 1 0 1 //1,3,5
0 1 1 0 1 //2,3,5
1 0 0 1 1 //1,4,5
0 1 0 1 1 //2,4,5
0 0 1 1 1 //3,4,5
Efficiency: 5 out of 20 elements were selected and a total of 15,504 results were obtained, which took about 10ms.
Code implementation:
package huawei
import (
"fmt"
"time"
)
/*
Permutation and combination problem: n The number of m A.
*/
func Test10Base() {
nums := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
m := 5
timeStart := time.Now()
n := len(nums)
indexs := zuheResult(n, m)
result := findNumsByIndexs(nums, indexs)
timeEnd := time.Now()
fmt.Println("count:", len(result))
fmt.Println("result:", result)
fmt.Println("time consume:", timeEnd.Sub(timeStart))
// Is the result correct
rightCount := mathZuhe(n, m)
if rightCount == len(result) {
fmt.Println(" Results the correct ")
} else {
fmt.Println(" The correct result is: ", rightCount)
}
}
// Combination algorithm ( from nums Remove the m The number of )
func zuheResult(n int, m int) [][]int {
if m < 1 || m > n {
fmt.Println("Illegal argument. Param m must between 1 and len(nums).")
return [][]int{}
}
// The array that holds the final result, and the total is calculated directly by the mathematical formula
result := make([][]int, 0, mathZuhe(n, m))
// Save every 1 An array of combined indexes, 1 That means selected, 0 That means it's not selected
indexs := make([]int, n)
for i := 0; i < n; i++ {
if i < m {
indexs[i] = 1
} else {
indexs[i] = 0
}
}
// The first 1 results
result = addTo(result, indexs)
for {
find := false
// Each cycle will be the first 1 Time in the 1 0 Instead of 0 1 And the one on the left 1 Move to the far left
for i := 0; i < n-1; i++ {
if indexs[i] == 1 && indexs[i+1] == 0 {
find = true
indexs[i], indexs[i+1] = 0, 1
if i > 1 {
moveOneToLeft(indexs[:i])
}
result = addTo(result, indexs)
break
}
}
// This cycle was not found 1 0 , which means we've got the last one 1 Kind of circumstance
if !find {
break
}
}
return result
}
// will ele Copy and add to arr , returns a new array
func addTo(arr [][]int, ele []int) [][]int {
newEle := make([]int, len(ele))
copy(newEle, ele)
arr = append(arr, newEle)
return arr
}
func moveOneToLeft(leftNums []int) {
// How many do I count 1
sum := 0
for i := 0; i < len(leftNums); i++ {
if leftNums[i] == 1 {
sum++
}
}
// The former sum A change to 1 , after 0
for i := 0; i < len(leftNums); i++ {
if i < sum {
leftNums[i] = 1
} else {
leftNums[i] = 0
}
}
}
// Gets an array of elements from the index number array
func findNumsByIndexs(nums []int, indexs [][]int) [][]int {
if len(indexs) == 0 {
return [][]int{}
}
result := make([][]int, len(indexs))
for i, v := range indexs {
line := make([]int, 0)
for j, v2 := range v {
if v2 == 1 {
line = append(line, nums[j])
}
}
result[i] = line
}
return result
}
Note: The total number of ways to take m 1 out of n elements can be directly calculated by mathematical formula, namely:
// The mathematical method calculates the number of permutations ( from n To take m The number of )
func mathPailie(n int, m int) int {
return jieCheng(n) / jieCheng(n-m)
}
// The mathematical method calculates the number of combinations ( from n To take m The number of )
func mathZuhe(n int, m int) int {
return jieCheng(n) / (jieCheng(n-m) * jieCheng(m))
}
// factorial
func jieCheng(n int) int {
result := 1
for i := 2; i <= n; i++ {
result *= i
}
return result
}This formula can be used to simply verify the correctness of the above program results under 1.
(2) Permutation problem
From the number of n, the number of m is taken and arranged. In fact, after the combination algorithm, the number of m selected is arranged in full. The full permutation problem has been discussed in a previous article.
Code implementation:
func pailieResult(nums []int, m int) [][]int {
// Combination of results
zuhe := zuheResult(nums, m)
// Save the final permutation results
result := make([][]int, 0)
// Iterate through the combined results, for each 1 The items are arranged in full order
for _, v := range zuhe {
p := quanPailie(v)
result = append(result, p...)
}
return result
}
//n Total number arrangement
// Such as the input [1 2 3] , the return [123 132 213 231 312 321]
func quanPailie(nums []int) [][]int {
COUNT := len(nums)
// check
if COUNT == 0 || COUNT > 10 {
panic("Illegal argument. nums size must between 1 and 9.")
}
// If only 1 The number is directly returned
if COUNT == 1 {
return [][]int{nums}
}
// Otherwise, it will be the last 1 Number inserted into all positions in the preceding permutation number
return insertItem(quanPailie(nums[:COUNT-1]), nums[COUNT-1])
}
func insertItem(res [][]int, insertNum int) [][]int {
// Save the result slice
result := make([][]int, len(res)*(len(res[0])+1))
index := 0
for _, v := range res {
for i := 0; i < len(v); i++ {
// in v Each of the 1 A new element is inserted before the element
result[index] = insertToSlice(v, i, insertNum)
index++
}
// in v Insert a new element at the end
result[index] = append(v, insertNum)
index++
}
return result
}
// The element value Insert into array nums The index for index The location of the
func insertToSlice(nums []int, index int, value int) []int {
result := make([]int, len(nums)+1)
copy(result[:index], nums[:index])
result[index] = value
copy(result[index+1:], nums[index:])
return result
}I hope this article has been helpful in Go programming.