时间戳

首页 > 解决方案 > 给定数字 n，如何打印大小为 m 的所有子序列？

algorithm - 给定数字 n，如何打印大小为 m 的所有子序列？

问题描述

对于以下问题：

数字的子序列是数字的一系列（不一定是连续的）数字。例如，12345 的子序列包括 123、234、124、245 等。您的任务是生成低于一定长度的子序列。

def generate_subseq(n, m):
    """
    Print all subsequence of length at most m that can be found in the given number n.
    For example, for n = 20125 and m = 3, we have that the subsequences are
        201
        202
        205
        212
        215
        225
        012
        015
        025
        125
   

    >>> generate_subseq(20125, 3)
        201
        202
        205
        212
        215
        225
        012
        015
        025
        125
     >>> generate_subseq(20125, 5)
        20125
    """

以下是非工作解决方案：

package main

import (
    "fmt"
    "strconv"
)

func generateSubSequence(n int, subSequenceSize int) []int {

    digitSequence := intToSequenceOfDigits(n) // [2,0,1,2,5]

    var f func([]int, int, int) []int
    f = func(digitSequence []int, pickingIndex int, currentSubSequenceSize int) []int {

        if pickingIndex+1 == currentSubSequenceSize {
            value := sequenceOfDigitsToInt(digitSequence[0:currentSubSequenceSize])
            return []int{value}
        }

        if currentSubSequenceSize == 0 {
            return []int{}
        }

        digit := digitSequence[pickingIndex]

        withM := mapDigit(f(digitSequence, pickingIndex-1, currentSubSequenceSize-1), digit)
        withoutM := f(digitSequence, pickingIndex-1, currentSubSequenceSize)

        return append(withM, withoutM...)
    }

    return f(digitSequence, len(digitSequence)-1, subSequenceSize)
}

func mapDigit(slice []int, digit int) []int {
    result := make([]int, len(slice))
    for i, value := range slice {
        result[i] = value*10 + digit
    }
    return result
}

func sequenceOfDigitsToInt(digits []int) int {
    result := 0
    for _, value := range digits {
        result = result*10 + value
    }
    return result
}

func intToSequenceOfDigits(n int) []int { // [2,0,1,2,5]
    var convert func(int) []int
    sequence := []int{}
    convert = func(n int) []int {
        if n != 0 {
            digit := n % 10
            sequence = append([]int{digit}, sequence...)
            convert(n / 10)
        }
        return sequence
    }
    return convert(n)
}


func main() {
    fmt.Println(generateSubSequence(20125, 3))
}

实际输出为：[225 215 205 212 202 201]

预期输出为：[201 202 205 212 215 225 012 015 025 125]

为什么实际输出缺少一些子序列？之类的125……

标签： algorithmgorecursiondata-structuresdivide-and-conquer

解决方案

像这样的东西？修改我的其他答案：

function f(s, i, l){
  if (i + 1 == l)
    return [s.substr(0, l)];

  if (!l)
    return [''];
    
  const left = f(s, i - 1, l);
  const right = f(s, i - 1, l - 1);

  return left.concat(
    right.map(x => x + s[i]));
}

var input = [
  ['20125', 3],
  ['12345', 3]
];

for (let [s, l] of input){
  console.log(s + ', l: ' + l);
  console.log(JSON.stringify(f(s, s.length-1, l)));
  console.log('');
}

推荐阅读