分享每一天-【golang】笛卡尔积算法

【golang】笛卡尔积算法

GoLang 1068 0 创建时间：2023-03-27 11:24:17

笛卡尔积算法

#### 【golang】笛卡尔积算法
input:
[[a,b],[c],[d,e]]

output:
[[a,c,d],[a,c,e],[b,c,d],[b,c,e]]

思路：分治#
预处理第一项：[a,b] -> [[a],[b]]

[[a],[b]] 和 [c] -> [[a,c],[b,c]]

[[a,c],[b,c]] 和 [d,e] -> [[a,c,d],[a,c,e],[b,c,d],[b,c,e]]

```go
// Product 
func Product(sets ...[]interface{}) [][]interface{} {
	lens := func(i int) int { return len(sets[i]) }
	product := [][]interface{}{}
	for ix := make([]int, len(sets)); ix[0] < lens(0); nextIndex(ix, lens) {
		var r []interface{}
		for j, k := range ix {
			r = append(r, sets[j][k])
		}
		product = append(product, r)
	}
	return product
}
 
func nextIndex(ix []int, lens func(i int) int) {
	for j := len(ix) - 1; j >= 0; j-- {
		ix[j]++
		if j == 0 || ix[j] < lens(j) {
			return
		}
		ix[j] = 0
	}
}
 
 
func main() {
 
	sets := cartesian.Product([]interface{}{"a", "b", "c"}, []interface{}{1, 2, 3})
	for _, set := range sets {
		fmt.Println(set)
	}
 
	// Ordered Output:
	// [a 1]
	// [b 1]
	// [c 1]
	// [a 2]
	// [b 2]
	// [c 2]
	// [a 3]
	// [b 3]
	// [c 3]
}
```

#### 【golang】笛卡尔积算法（泛型）
```go

// 笛卡尔积
func Product[T any](sli [][]T) [][]T {
	if len(sli) == 0 {
		return sli
	}
	ret := make([][]T, 0, len(sli[0]))
	for i := 0; i < len(sli[0]); i++ {
		ret = append(ret, []T{sli[0][i]})
	}
	for i := 1; i < len(sli); i++ {
		ret = product(ret, sli[i])
	}
	return ret
}

// 分治
func product[T any](sli [][]T, curr []T) [][]T {
	ret := make([][]T, 0, len(sli)*len(curr))
	for i := 0; i < len(sli); i++ {
		for j := 0; j < len(curr); j++ {
			tmp := make([]T, len(sli[i]))
			copy(tmp, sli[i])
			ret = append(ret, append(tmp, curr[j]))
		}
	}
	return ret
}

```

【golang】笛卡尔积算法

商品推荐

广告推荐

推荐文章