Cartesian product of two or more lists: Difference between revisions
Cartesian product of two or more lists (view source)
Revision as of 23:26, 5 November 2017
, 6 years agoGo solution
m (→{{header|REXX}}: changed comments, whitespace, and indentations, used simpler DO index variables.) |
(Go solution) |
||
Line 340:
[]
[]</pre>
=={{header|Go}}==
'''Basic Task'''
<lang go>package main
import "fmt"
type pair [2]int
func cart2(a, b []int) []pair {
p := make([]pair, len(a)*len(b))
i := 0
for _, a := range a {
for _, b := range b {
p[i] = pair{a, b}
i++
}
}
return p
}
func main() {
fmt.Println(cart2([]int{1, 2}, []int{3, 4}))
fmt.Println(cart2([]int{3, 4}, []int{1, 2}))
fmt.Println(cart2([]int{1, 2}, nil))
fmt.Println(cart2(nil, []int{1, 2}))
}</lang>
{{out}}
<pre>
[[1 3] [1 4] [2 3] [2 4]]
[[3 1] [3 2] [4 1] [4 2]]
[]
[]
</pre>
'''Extra credit 1'''
This solution minimizes allocations and computes and fills the result sequentially.
<lang go>package main
import "fmt"
func cartN(a ...[]int) [][]int {
c := 1
for _, a := range a {
c *= len(a)
}
if c == 0 {
return nil
}
p := make([][]int, c)
b := make([]int, c*len(a))
n := make([]int, len(a))
s := 0
for i := range p {
e := s + len(a)
pi := b[s:e]
p[i] = pi
s = e
for j, n := range n {
pi[j] = a[j][n]
}
for j := len(n) - 1; j >= 0; j-- {
n[j]++
if n[j] < len(a[j]) {
break
}
n[j] = 0
}
}
return p
}
func main() {
fmt.Println(cartN([]int{1, 2}, []int{3, 4}))
fmt.Println(cartN([]int{3, 4}, []int{1, 2}))
fmt.Println(cartN([]int{1, 2}, nil))
fmt.Println(cartN(nil, []int{1, 2}))
fmt.Println()
fmt.Println("[")
for _, p := range cartN(
[]int{1776, 1789},
[]int{7, 12},
[]int{4, 14, 23},
[]int{0, 1},
) {
fmt.Println(" ", p)
}
fmt.Println("]")
fmt.Println(cartN([]int{1, 2, 3}, []int{30}, []int{500, 100}))
fmt.Println(cartN([]int{1, 2, 3}, []int{}, []int{500, 100}))
fmt.Println()
fmt.Println(cartN(nil))
fmt.Println(cartN())
}</lang>
{{out}}
<pre>
[[1 3] [1 4] [2 3] [2 4]]
[[3 1] [3 2] [4 1] [4 2]]
[]
[]
[
[1776 7 4 0]
[1776 7 4 1]
[1776 7 14 0]
[1776 7 14 1]
[1776 7 23 0]
[1776 7 23 1]
[1776 12 4 0]
[1776 12 4 1]
[1776 12 14 0]
[1776 12 14 1]
[1776 12 23 0]
[1776 12 23 1]
[1789 7 4 0]
[1789 7 4 1]
[1789 7 14 0]
[1789 7 14 1]
[1789 7 23 0]
[1789 7 23 1]
[1789 12 4 0]
[1789 12 4 1]
[1789 12 14 0]
[1789 12 14 1]
[1789 12 23 0]
[1789 12 23 1]
]
[[1 30 500] [1 30 100] [2 30 500] [2 30 100] [3 30 500] [3 30 100]]
[]
[]
[[]]
</pre>
'''Extra credit 2'''
Code here is more compact, but with the cost of more garbage produced. It produces the same result as cartN above.
<lang go>func cartN(a ...[]int) (c [][]int) {
if len(a) == 0 {
return [][]int{nil}
}
r := cartN(a[1:]...)
for _, e := range a[0] {
for _, p := range r {
c = append(c, append([]int{e}, p...))
}
}
return
}</lang>
'''Extra credit 3'''
This is a compact recursive version like Extra credit 2 but the result list is ordered differently. This is still a correct result if you consider a cartesian product to be a set, which is an unordered collection. Note that the set elements are still ordered lists. A cartesian product is an unordered collection of ordered collections. It draws attention though to the gloss of using list representations as sets. Any of the functions here will accept duplicate elements in the input lists, and then produce duplicate elements in the result.
<lang go>func cartN(a ...[]int) (c [][]int) {
if len(a) == 0 {
return [][]int{nil}
}
last := len(a) - 1
l := cartN(a[:last]...)
for _, e := range a[last] {
for _, p := range l {
c = append(c, append(p, e))
}
}
return
}</lang>
=={{header|Haskell}}==
| |||