时间戳

首页 > 解决方案 > 生成数字顺序递增的数字列表

haskell - 生成数字顺序递增的数字列表

问题描述

嗨，我正在尝试生成一个列表

例如，如果n = 3输出为 [111 .. 321 .. 543 ..999]。

我最初的尝试是

--attempt1

digits n = map (\x -> read [x] :: Int) (show n)

sorted [] = True
sorted [x] = True
sorted (x:y:xs) = if x <= y then sorted (y:xs) else False


[ x | x <- [ 10^(n-1) .. 10^n ] , sorted $ digits $ x]

然而，随着变量 n 变大，这种方法会以指数方式变慢。

我的第二种方法是（如果 n == 3）

joiner :: [Integer] -> Integer
joiner = read . concatMap show

[ joiner [z,y,x] |
        x <- [1..9],
        y <- [9,8..x],
        z <- [9,8..y]]

但是现在的问题是我如何将这段代码推广到任意n

joiner :: [Integer] -> Integer
joiner = read . concatMap show

[ joiner [a_n,...,a_1] |
        a_1 <- [1..9],
        a_2 <- [9,8..x],
        .
        .
        .
        a_n <- [9,8..a_n-1]
]

谢谢！

标签： haskell

解决方案

每次你需要组合 N 个东西（其中 N 是预先未知的）时，答案总是递归。毕竟，这是在 Haskell 中迭代的唯一方法。

首先，我们需要一种将另一个数字附加到给定数字的方法。很简单：

appendDigit x = [ x*10 + d | d <- [0..9] ]

让我们测试一下：

λ appendDigit 2
[20,21,22,23,24,25,26,27,28,29]
λ appendDigit 3                
[30,31,32,33,34,35,36,37,38,39]

但还不够好：我们只需要附加小于最后一位的数字。嗯，很容易修改：

appendDigit x = [ x*10 + d | d <- [0..(lastDigit-1)] ]
    where lastDigit = x `mod` 10

试试看：

λ appendDigit 2          
[20,21]                  
*Main Lib                
λ appendDigit 3          
[30,31,32]               
*Main Lib                
λ appendDigit 8          
[80,81,82,83,84,85,86,87]

现在剩下的就是做 N 次，一路连接结果列表：

decDigits 0 = []  -- degenerate case: when N = 0, there are no such numbers
decDigits 1 = [0..9] -- base case: N = 1
decDigits n = concatMap appendDigit $ decDigits (n-1)

推荐阅读