在golang中創建數字組合的遞歸函數

Question

我想弄清楚這個遞歸函數的事情。我有一個non-recursive demo that works但它使用靜態方法不遞歸。這些函數從「pool_size」中打印出「數字集」的所有組合。如果有人可以，請幫助我使這個函數遞歸，這將是偉大的。

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]