Created
September 13, 2024 21:45
-
-
Save PratikDeoghare/05747c8c3524cd23a7da59617b69e2bc to your computer and use it in GitHub Desktop.
itertools.product in golang
This file contains hidden or 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" | |
| "testing" | |
| ) | |
| func product(xss [][]int) [][]int { | |
| if len(xss) == 0 { | |
| return nil | |
| } | |
| if len(xss) == 1 { | |
| var out [][]int | |
| for _, x := range xss[0] { | |
| out = append(out, []int{x}) | |
| } | |
| return out | |
| } | |
| var out [][]int | |
| head := xss[0] | |
| tail := xss[1:] | |
| yss := product(tail) | |
| for _, h := range head { | |
| for _, ys := range yss { | |
| out = append(out, append([]int{h}, ys...)) | |
| } | |
| } | |
| return out | |
| } | |
| func product1(xss [][]int, ys []int, ch chan []int) { | |
| if len(xss) == 0 { | |
| return | |
| } | |
| if len(xss) == 1 { | |
| for _, x := range xss[0] { | |
| ch <- append(ys, x) | |
| } | |
| return | |
| } | |
| head := xss[0] | |
| tail := xss[1:] | |
| for _, h := range head { | |
| product1(tail, append(ys, h), ch) | |
| } | |
| } | |
| func make_change(x int, coinset []int) [][]int { | |
| var xss [][]int | |
| for _, c := range coinset { | |
| var rs []int | |
| for i := 0; i < x/c+1; i++ { | |
| rs = append(rs, i) | |
| } | |
| xss = append(xss, rs) | |
| } | |
| var out [][]int | |
| for _, xs := range product(xss) { | |
| if dot(xs, coinset) == x { | |
| out = append(out, xs) | |
| } | |
| } | |
| return out | |
| } | |
| func dot(xs, ys []int) int { | |
| out := 0 | |
| for i := 0; i < len(xs); i++ { | |
| out += xs[i] * ys[i] | |
| } | |
| return out | |
| } | |
| func TestName(t *testing.T) { | |
| //fmt.Println(make_change(6, []int{1, 5, 10, 25})) | |
| //fmt.Println(make_change(6, []int{3, 4})) | |
| //fmt.Println(make_change(6, []int{1, 3, 4})) | |
| //fmt.Println(make_change(6, []int{5, 7})) | |
| //fmt.Println(make_change(16, []int{5, 7, 9})) | |
| ch := make(chan []int) | |
| xss := [][]int{ | |
| {1, 3}, {4, 5}, {9, 10}, | |
| } | |
| go product1(xss, nil, ch) | |
| n := 1 | |
| for _, xs := range xss { | |
| n = n * len(xs) | |
| } | |
| for xs := range ch { | |
| n-- | |
| fmt.Println(xs) | |
| if n == 0 { | |
| close(ch) | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment