有这么个需求, 给一组维度, 维度的数量不固定, 各个维度的取值数目也不一定。 类似
di: 0, 1, 2
dj: 0, 1
dk: 0, 1, 2, 3, 4
...
怎么取得这么一组给定不定长维度下值的组合?
# example
package main
import "fmt"
var (
di = []int{0, 1, 2}
dj = []int{0, 1}
dk = []int{0, 1, 2, 3, 4}
)
func main() {
getResult(di, dj, dk)
}
func getResult(di, dj, dk []int) {
for _, i := range di {
for _, j := range dj {
for _, k := range dk {
fmt.Printf("[%d, %d, %d] \t", i, j, k)
}
}
}
}
# result
[0, 0, 0] [0, 0, 1] [0, 0, 2] [0, 0, 3] [0, 0, 4] [0, 1, 0] [0, 1, 1] [0, 1, 2] [0, 1, 3] [0, 1, 4] [1, 0, 0] [1, 0, 1] [1, 0, 2] [1, 0, 3] [1, 0, 4] [1, 1, 0] [1, 1, 1] [1, 1, 2] [1, 1, 3] [1, 1, 4] [2, 0, 0] [2, 0, 1] [2, 0, 2] [2, 0, 3] [2, 0, 4] [2, 1, 0] [2, 1, 1] [2, 1, 2] [2, 1, 3] [2, 1, 4]
如果维度再增加, 还得手动加上一套for range
。
有没有更好的解决方案?
1
misdake 2021-01-31 21:26:35 +08:00
和指定长度数组的全排列蛮像的,循环的层数是不确定的,只是取数字的方式不一样
|
2
zhoudaiyu 2021-01-31 21:29:58 +08:00 via iPhone
是不是可以考虑用代码生成代码的思路?
|
3
fline 2021-01-31 21:31:28 +08:00
递归
|
4
minbaby 2021-01-31 21:41:51 +08:00
|
5
chairuosen 2021-01-31 21:47:42 +08:00
只写一层 for,自己判断跳出条件和累加策略
|
7
notamail 2021-01-31 22:03:39 +08:00
应该没有你这样写代码的。。。
|
8
Lemeng 2021-01-31 22:05:30 +08:00
for 有点多
|
9
jinliming2 2021-01-31 22:12:36 +08:00 1
不一定是最高效的办法:
```go package main import "fmt" var ( di = []int{0, 1, 2} dj = []int{0, 1} dk = []int{0, 1, 2, 3, 4} ) func main() { res := getResult(di, dj, dk) for _, item := range res { fmt.Println(item) } } func getResult(d0 []int, d1 ...[]int) (res [][]int) { if len(d1) == 0 { res = make([][]int, 0, len(d0)) for _, d := range d0 { res = append(res, []int{d}) } return } sub := getResult(d1[0], d1[1:]...) for _, item := range d0 { for _, s := range sub { c := []int{item} c = append(c, s...) res = append(res, c) } } return } ``` |
10
Claar 2021-01-31 22:55:52 +08:00 via iPhone
哈哈哈看来 V2EX 的少年算法水平不行啊
这看起来是求全排列吗? 最基本的解决方案可以看基础的算法里的暴力破解,不剪枝 手机登的 V2EX 没法发代码……图片也不知道咋发 |
11
Claar 2021-01-31 23:07:32 +08:00
"""
func main() { input := [][]int{[]int{1, 2, 3, }, []int{5, 6, 7, 8}, []int{9, 10, 11, 12}} res := make([][]int, 0) rec := make([]int, 0) helper(input, &res, &rec, 0) fmt.Println(res) } func helper(input [][]int, res *[][]int, rec *[]int, index int) { if index < len(input) { for _, v := range input[index] { *rec = append(*rec, v) helper(input, res, rec, index+1) *rec = (*rec)[:index] } return } tmp := make([]int, len(input)) copy(tmp, *rec) *res = append(*res, tmp) *rec = (*rec)[:index] } """ |
12
crclz 2021-01-31 23:08:17 +08:00
基础的 DFS
|
13
lu5je0 2021-01-31 23:08:46 +08:00
```java
class Demo { public static void main(String[] args) { new Demo().func(); } public void func() { List<List<Integer>> res = new ArrayList<>(); List<List<Integer>> sourceList = new ArrayList<>(); sourceList.add(Arrays.asList(0, 1, 2)); sourceList.add(Arrays.asList(0, 1)); sourceList.add(Arrays.asList(0, 1, 2, 3, 4)); dfs(sourceList, res, new ArrayList<>(), 0); System.out.println(res); } public void dfs(List<List<Integer>> sourceList, List<List<Integer>> res, List<Integer> curList, int index) { if (index == sourceList.size()) { res.add(new ArrayList<>(curList)); } else { List<Integer> source = sourceList.get(index); for (Integer i : source) { curList.add(i); dfs(sourceList, res, curList, index + 1); curList.remove(curList.size() - 1); } } } } ``` |
14
mauve 2021-02-01 08:20:01 +08:00 via iPhone
builtin 的 append 方法就是用的 for 循环
|
15
DarkCat123 2021-02-01 12:50:25 +08:00
康托展开。
|