Recursive function to create number combinations in golang

huangapple go评论83阅读模式
英文:

Recursive function to create number combinations in golang

问题

我正在尝试理解这个递归函数的问题。我有一个非递归的演示代码,它可以工作,但它使用的是静态方法而不是递归。这个函数会打印出所有从"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)
}

请帮我将这段代码改写成递归的形式。谢谢!

英文:

I'm trying to figure out this recursive function thing. I have a <a href="https://play.golang.org/p/GYizR_0qdc">non-recursive demo that works</a> but it uses static methods not recursive. The functions prints out all the combinations of the "number sets" from the "pool_size". If someone could, please help me make this function recursive that would be great.

package main

import (
	&quot;fmt&quot;
)

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

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

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

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

答案1

得分: 2

例如,

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, "个池子", "用于", "数字", numbers)
    fmt.Println()
    nc := 0
    c := Combinations(pools, numbers)
    fmt.Println("池子:")
    d := " 位数: "
    for i := range c {
        fmt.Println(i+1, d)
        d = " 位数: "
        for j := range c[i] {
            nc++
            fmt.Println(c[i][j], " ")
        }
    }
    fmt.Println()
    fmt.Println(nc, "种组合")
}

输出:

3 个池子 用于 数字 [1 2 3 4 5 6 7 8 9 10]

池子:
1  位数: 
[1]  
[2]  
[3]  
[4]  
[5]  
[6]  
[7]  
[8]  
[9]  
[10]  
2  位数: 
[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  位数: 
[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 种组合

单个池子的变化是:

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, "位数池", "用于", "数字", numbers)
    for i := range p {
        fmt.Println(p[i])
    }
}

输出:

9 位数池 用于 数字 [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]
英文:

For example,

package main

import &quot;fmt&quot;

func rCombinations(p int, n []int, c []int, ccc [][][]int) [][][]int {
	if len(n) == 0 || p &lt;= 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, &quot;pools&quot;, &quot;for&quot;, &quot;numbers&quot;, numbers)
	fmt.Println()
	nc := 0
	c := Combinations(pools, numbers)
	fmt.Println(&quot;pools:&quot;)
	d := &quot; digit : &quot;
	for i := range c {
		fmt.Println(i+1, d)
		d = &quot; digits: &quot;
		for j := range c[i] {
			nc++
			fmt.Println(c[i][j], &quot; &quot;)
		}
	}
	fmt.Println()
	fmt.Println(nc, &quot;combinations&quot;)
}

Output:

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

The variation for a single pool is:

package main

import &quot;fmt&quot;

func rPool(p int, n []int, c []int, cc [][]int) [][]int {
	if len(n) == 0 || p &lt;= 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, &quot;digit pool&quot;, &quot;for&quot;, &quot;numbers&quot;, numbers)
	for i := range p {
		fmt.Println(p[i])
	}
}

Output:

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]

huangapple
  • 本文由 发表于 2016年2月6日 05:19:37
  • 转载请务必保留本文链接:https://go.coder-hub.com/35233717.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定