recursion - 在golang中创建数字组合的递归函数

Question

我正在尝试弄清楚这个递归函数。我有一个 non-recursive demo that works但它使用非递归的静态方法。这些函数打印出“pool_size”中“number sets”的所有组合。如果有人可以，请帮助我使这个函数递归，那会很棒。

package main

import (
    "fmt"
)

func combos_of1(pool_size int) {
    for i := 1; i < pool_size+1; i++ {
        fmt.Println(i)
    }
    fmt.Println("\n")
}

func combos_of2(pool_size int) {
    for i := 1; i < pool_size+1; i++ {
        for j := i + 1; j < pool_size+1; j++ {
            fmt.Println(i, j)
        }
    }
    fmt.Println("\n")
}

func combos_of3(pool_size int) {
    for i := 1; i < pool_size+1; i++ {
        for j := i + 1; j < pool_size+1; j++ {
            for k := j + 1; k < pool_size+1; k++ {
                fmt.Println(i, j, k)
            }
        }
    }
    fmt.Println("\n")
}

func main() {
    combos_of1(10)
    combos_of2(10)
    combos_of3(10)
}

Answer 1

例如，

package main

import "fmt"

func rCombinations(p int, n []int, c []int, ccc [][][]int) [][][]int {
    if len(n) == 0 || p <= 0 {
        return ccc
    }
    if len(ccc) == 0 {
        ccc = make([][][]int, p)
    }
    p--
    for i := range n {
        cc := make([]int, len(c)+1)
        copy(cc, c)
        cc[len(cc)-1] = n[i]
        ccc[len(cc)-1] = append(ccc[len(cc)-1], cc)
        ccc = rCombinations(p, n[i+1:], cc, ccc)
    }
    return ccc
}

func Combinations(p int, n []int) [][][]int {
    return rCombinations(p, n, nil, nil)
}

func main() {
    pools := 3
    numbers := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    fmt.Println(pools, "pools", "for", "numbers", numbers)
    fmt.Println()
    nc := 0
    c := Combinations(pools, numbers)
    fmt.Println("pools:")
    d := " digit : "
    for i := range c {
        fmt.Println(i+1, d)
        d = " digits: "
        for j := range c[i] {
            nc++
            fmt.Println(c[i][j], " ")
        }
    }
    fmt.Println()
    fmt.Println(nc, "combinations")
}

输出:

3 pools for numbers [1 2 3 4 5 6 7 8 9 10]

pools:
1  digit : 
[1]  
[2]  
[3]  
[4]  
[5]  
[6]  
[7]  
[8]  
[9]  
[10]  
2  digits: 
[1 2]  
[1 3]  
[1 4]  
[1 5]  
[1 6]  
[1 7]  
[1 8]  
[1 9]  
[1 10]  
[2 3]  
[2 4]  
[2 5]  
[2 6]  
[2 7]  
[2 8]  
[2 9]  
[2 10]  
[3 4]  
[3 5]  
[3 6]  
[3 7]  
[3 8]  
[3 9]  
[3 10]  
[4 5]  
[4 6]  
[4 7]  
[4 8]  
[4 9]  
[4 10]  
[5 6]  
[5 7]  
[5 8]  
[5 9]  
[5 10]  
[6 7]  
[6 8]  
[6 9]  
[6 10]  
[7 8]  
[7 9]  
[7 10]  
[8 9]  
[8 10]  
[9 10]  
3  digits: 
[1 2 3]  
[1 2 4]  
[1 2 5]  
[1 2 6]  
[1 2 7]  
[1 2 8]  
[1 2 9]  
[1 2 10]  
[1 3 4]  
[1 3 5]  
[1 3 6]  
[1 3 7]  
[1 3 8]  
[1 3 9]  
[1 3 10]  
[1 4 5]  
[1 4 6]  
[1 4 7]  
[1 4 8]  
[1 4 9]  
[1 4 10]  
[1 5 6]  
[1 5 7]  
[1 5 8]  
[1 5 9]  
[1 5 10]  
[1 6 7]  
[1 6 8]  
[1 6 9]  
[1 6 10]  
[1 7 8]  
[1 7 9]  
[1 7 10]  
[1 8 9]  
[1 8 10]  
[1 9 10]  
[2 3 4]  
[2 3 5]  
[2 3 6]  
[2 3 7]  
[2 3 8]  
[2 3 9]  
[2 3 10]  
[2 4 5]  
[2 4 6]  
[2 4 7]  
[2 4 8]  
[2 4 9]  
[2 4 10]  
[2 5 6]  
[2 5 7]  
[2 5 8]  
[2 5 9]  
[2 5 10]  
[2 6 7]  
[2 6 8]  
[2 6 9]  
[2 6 10]  
[2 7 8]  
[2 7 9]  
[2 7 10]  
[2 8 9]  
[2 8 10]  
[2 9 10]  
[3 4 5]  
[3 4 6]  
[3 4 7]  
[3 4 8]  
[3 4 9]  
[3 4 10]  
[3 5 6]  
[3 5 7]  
[3 5 8]  
[3 5 9]  
[3 5 10]  
[3 6 7]  
[3 6 8]  
[3 6 9]  
[3 6 10]  
[3 7 8]  
[3 7 9]  
[3 7 10]  
[3 8 9]  
[3 8 10]  
[3 9 10]  
[4 5 6]  
[4 5 7]  
[4 5 8]  
[4 5 9]  
[4 5 10]  
[4 6 7]  
[4 6 8]  
[4 6 9]  
[4 6 10]  
[4 7 8]  
[4 7 9]  
[4 7 10]  
[4 8 9]  
[4 8 10]  
[4 9 10]  
[5 6 7]  
[5 6 8]  
[5 6 9]  
[5 6 10]  
[5 7 8]  
[5 7 9]  
[5 7 10]  
[5 8 9]  
[5 8 10]  
[5 9 10]  
[6 7 8]  
[6 7 9]  
[6 7 10]  
[6 8 9]  
[6 8 10]  
[6 9 10]  
[7 8 9]  
[7 8 10]  
[7 9 10]  
[8 9 10]  

175 combinations

单个池的变化是:

package main

import "fmt"

func rPool(p int, n []int, c []int, cc [][]int) [][]int {
    if len(n) == 0 || p <= 0 {
        return cc
    }
    p--
    for i := range n {
        r := make([]int, len(c)+1)
        copy(r, c)
        r[len(r)-1] = n[i]
        if p == 0 {
            cc = append(cc, r)
        }
        cc = rPool(p, n[i+1:], r, cc)
    }
    return cc
}

func Pool(p int, n []int) [][]int {
    return rPool(p, n, nil, nil)
}

func main() {
    pool := 9
    numbers := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    p := Pool(pool, numbers)
    fmt.Println(pool, "digit pool", "for", "numbers", numbers)
    for i := range p {
        fmt.Println(p[i])
    }
}

输出:

9 digit pool for numbers [1 2 3 4 5 6 7 8 9 10]
[1 2 3 4 5 6 7 8 9]
[1 2 3 4 5 6 7 8 10]
[1 2 3 4 5 6 7 9 10]
[1 2 3 4 5 6 8 9 10]
[1 2 3 4 5 7 8 9 10]
[1 2 3 4 6 7 8 9 10]
[1 2 3 5 6 7 8 9 10]
[1 2 4 5 6 7 8 9 10]
[1 3 4 5 6 7 8 9 10]
[2 3 4 5 6 7 8 9 10]