Last active
July 1, 2023 17:15
-
-
Save cuiweixie/1f7134af3faf0170e0e94a092322dfb6 to your computer and use it in GitHub Desktop.
problem of solving polynomial equations of quintic and higher degree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import ( | |
"fmt" | |
"strconv" | |
"strings" | |
) | |
func permute(nums []int) [][]int { | |
if len(nums) == 0 { | |
return [][]int{} | |
} else if len(nums) == 1 { | |
return [][]int{{nums[0]}} | |
} | |
result := [][]int{} | |
for i, num := range nums { | |
subNums := make([]int, len(nums)-1) | |
copy(subNums[:i], nums[:i]) | |
copy(subNums[i:], nums[i+1:]) | |
subPermutations := permute(subNums) | |
for _, subPermutation := range subPermutations { | |
result = append(result, append([]int{num}, subPermutation...)) | |
} | |
} | |
return result | |
} | |
func Mul(a []int, b []int) []int { | |
var result []int | |
for i := 0; i < len(a); i++ { | |
result = append(result, a[b[i]-1]) | |
} | |
return result | |
} | |
func Inverse(a []int) []int { | |
var result []int | |
m := make(map[int]int) | |
for i := 0; i < len(a); i++ { | |
m[a[i]] = i + 1 | |
} | |
for i := 0; i < len(a); i++ { | |
result = append(result, m[i+1]) | |
} | |
return result | |
} | |
func unique(a [][]int) [][]int { | |
toString := func(a []int) string { | |
var result string | |
for index, i := range a { | |
result += fmt.Sprintf("%d", i) | |
if index != len(a)-1 { | |
result += "," | |
} | |
} | |
return result | |
} | |
toSlice := func(a string) []int { | |
var result []int | |
for _, i := range strings.Split(a, ",") { | |
j, _ := strconv.Atoi(i) | |
result = append(result, j) | |
} | |
return result | |
} | |
m := make(map[string]bool) | |
for _, i := range a { | |
m[toString(i)] = true | |
} | |
var result [][]int | |
for i := range m { | |
result = append(result, toSlice(i)) | |
} | |
return result | |
} | |
func getSwapSubGroup(permutations [][]int) [][]int { | |
var result [][]int | |
for i := 0; i < len(permutations); i++ { | |
for j := 0; j < len(permutations); j++ { | |
a := Mul(Mul(Mul(permutations[i], permutations[j]), Inverse(permutations[i])), Inverse(permutations[j])) | |
result = append(result, a) | |
} | |
} | |
return unique(result) | |
} | |
func checkN(n int) bool { | |
nums := make([]int, n) | |
for i := 0; i < n; i++ { | |
nums[i] = i + 1 | |
} | |
permutations := permute(nums) | |
println("len(permutations)", len(permutations)) | |
for { | |
swapSubGroup := getSwapSubGroup(permutations) | |
if len(swapSubGroup) == 1 { | |
fmt.Println(swapSubGroup) | |
return true | |
} | |
if len(swapSubGroup) >= len(permutations) { | |
println("len(swapSubGroup) >= len(permutations)", len(swapSubGroup), len(permutations)) | |
return false | |
} | |
permutations = swapSubGroup | |
} | |
return false | |
} | |
func main() { | |
println(checkN(2)) | |
println(checkN(3)) | |
println(checkN(4)) | |
println(checkN(5)) | |
println(checkN(6)) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment