树递归-打印给定数字的子序列 [英] Tree recursion - Print subsequence of a given number

问题描述

// m is the number, n is upto-length of subsequences
// m = 20125, n =3  should print 201, 202, 205, 212, 215, 225, 012, 015, 125
// m = 20125, n =2 should print 20, 21, 22, 25, 01, 02, 05, 12, 15, 25
// m = 20125, n =1 should print 2, 0, 1, 2, 5
// m = 20125, n =4 should print 2012, 2015, 2125, 0125, 2025
// m = 20125, n =5 should print 20125

---

以下是在GoLang中实现的递归解决方案:

---

Below is the recursive solution implemented in GoLang:

package recursion

import (
    "fmt"
    "strconv"
)

// m is the number, n is upto-length of subsequences
// m = 20125, n =3  should print 201, 202, 205, 212, 215, 225, 012, 015, 125
// m = 20125, n =2 should print 20, 21, 22, 25, 01, 02, 05, 12, 15, 25
// m = 20125, n =1 should print 2, 0, 1, 2, 5
// m = 20125, n =4 should print 20125

func PrintSubSequence(m int, n int) {

    numDigits := digits(m)

    if n >= 1 && numDigits >= n { // m != 0
        for i := 1; i <= numDigits-n+1; i++ { // tree recurion
            firstInvocToIter := true
            var slice []string
            var findSubSequence func(int, int)

            findSubSequence = func(m int, n int) {

                if n == 1 { // base case
                    for m != 0 {
                        slice = append(slice, strconv.Itoa(m%10))
                        m = m / 10
                    }
                    return
                } else {
                    if firstInvocToIter {
                        firstInvocToIter = false
                        findSubSequence(m/tenToThePower(i), n-1)
                    } else {
                        findSubSequence(m/10, n-1)
                    }

                    for i, value := range slice {
                        slice[i] = value + strconv.Itoa(m%10)
                    }
                }

            }
            findSubSequence(m, n) // (20125, 3)
            fmt.Println(slice)
        }

    } else {
        return
    }

    PrintSubSequence(m/10, n)
}

func tenToThePower(times int) int {
    number := 1
    for times > 0 {
        number *= 10
        times--
    }
    return number
}

// Return the number of the digits of positive integer n
func digits(n int) int {
    if n <= 0 {
        return 0
    } else if n < 10 {
        return 1
    } else {
        allButLast, _ := split(n)
        return digits(allButLast) + 1
    }
}

---

package main

import (
    "github.com/myhub/cs61a/recursion"
)

func main() {

    recursion.PrintSubSequence(20125, 2) // prints duplicates as per debugging
    recursion.PrintSubSequence(20125, 3) // Works fine 
}

---

对于recursion.PrintSubSequence(20125, 3)输出可以:

---

For recursion.PrintSubSequence(20125, 3) output is fine:

[125 025 225]
[015 215]
[205]
[012 212]
[202]

对于recursion.PrintSubSequence(20125, 2)输出有重复项(问题输出):

For recursion.PrintSubSequence(20125, 2) output has duplicates(problem output):

[25 15 05 25]        --> Valid
[15 05 25] --> duplicate
[05 25] --> duplicate
[25] --> duplicate
[12 02 22]           --> Valid
[02 22] --> duplicate
[22] --> duplicate
[01 21]              --> Valid
[21] --> duplicate
[20]                 --> Valid

---

这是否需要维护一组字符串?将slice包含在集合中

---

Does this require maintaining a set of strings? to include slice in a set

或

如何处理重复项?看起来n==1树递归的基本情况给问题了吗?

How to handle duplicates? Looks like n==1 base case of tree recursion is giving issue?

推荐答案

此处此处:-

1. 您需要从每个数字的角度进行思考. 因此，当您生成子序列时，数字可以是子序列的一部分，也可以不是.
2. 当您考虑一个特定的数字时，增加一个计数器(例如currentLength). 将到目前为止形成的序列添加到Set中，以避免重复.
3. 如果currentLength计数器已达到给定的最大长度，则停止形成当前子序列.
4. 移至下一个序列形成.

1. You need to think from a each digit perspective. So, when you generating subsequence, either a digit can be part of the subsequence, or it cannot be.
2. When you consider a particular digit, increment a counter (say, currentLength). Add the sequence which is formed till now to a Set to avoid duplicates.
3. If the currentLength counter has reached your given upto-length, then stop the formation of current subsequence.
4. Move onto next sequence formation.

这篇关于树递归-打印给定数字的子序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！