如何制作多个数字的倍数排序列表? [英] How to make a sorted list of multiples for several numbers?

问题描述

我在处理Haskell类的作业时遇到了麻烦.我已经解决了此任务的部分问题:我必须编写一个函数，该函数接受一个I​​nt并使用该Int的倍数创建一个无限列表.

I'm having trouble with an assignment from my Haskell class. I have already solved a partial problem of this task: I have to write a function that takes an Int and creates an infinite list with the multiples of that Int.

function :: Int -> [Int]
function d = [d*x | x <- [1..]]

控制台:

ghci> take 10 (function 3)

给予

[3,6,9,12,15,18,21,24,27,30]

在第二个任务中，我必须扩展该函数，以便它接受一个数字列表，并将该列表的每个值用作因子(以前是d).例如:

In the second task I have to extend the function so that it accepts a list of numbers and uses each value of that list as a factor (d previously). For example:

ghci> take 10 (function [3, 5])

应该给

[3,5,6,9,10,12,15,18,20,21]

已经尝试过类似列表理解

Already tried a list comprehension like

function d = [y*x | y <- [1..], x <- d]

但是该函数以未排序的形式返回列表:

but the function returns the list in an unsorted form:

[3,5,6,10,9,15,12,20,15,25]

我们得到了应该使用Haskell的模函数的提示，但是我不知道如何确切地进行操作.你对我有个好建议吗?

We got the tip that we should use the modulo function of Haskell, but I have no real idea how to proceed exactly. Do you have a good tip for me?

推荐答案

我只有一个班轮.

import Data.List (nub)

f xs = nub [x|x<-[1..], d<-xs, x `mod` d == 0]

take 10 $ f [3,5] -- [3,5,6,9,10,12,15,18,20,21]

从结果列表中，

运行时应为O(n²+ n * d). nub 以O(n²)运行.摆脱它会很好.

runtime should be O(n² + n*d) from the resulting list. The nub runs in O(n²). Would be nice to get rid of it.

g xs = [x |x<-[1..], let ys = map (mod x) xs in 0 `elem` ys]

这执行得还不错.它应该以O(n * d)运行.我也有这个版本，我认为它的性能至少和 g 一样好，但是显然它的性能比 f 好，但比 g 差./p>

This performs pretty ok. It should run in O (n*d). I also have this version which I thought performs at least as well as g, but apparently it performs better than f and worse than g.

h xs = [x |x<-[1..], or [x `mod` d == 0 |d<-xs] ]

我不确定为什么或是懒惰的，据我所知，它运行速度较慢的任何原因都没有.当您增加输入列表的长度时，它尤其不能很好地缩放.

I am not sure why that is, or is lazy as far as I can tell and I don`t see any reason why it should run slower. It especially does not scale as well when you increase the length of the input list.

i xs = foldr1 combine [[x, x+x ..] |x<- sort xs]
    where
      combine l [] = l
      combine [] r = r
      combine l@(x:xs) r@(y:ys)
        | x < y = (x: combine xs r)
        | x > y = (y: combine l ys)
        | otherwise = (x: combine xs ys)

不再是一个班轮，而是我能想到的最快的班轮.我不能百分百地确定，如果您左右折叠并且事先对输入列表进行排序，为什么它对运行时有如此大的影响?但是，由于以下原因，它不会对结果产生影响:

Not a one liner anymore, but the fastest I could come up with. I am not a hundred percent sure why it makes such a big difference on runtime if you right or left fold and if you sort the input list in advance. But it should not make a difference on the result since:

commutative a b = combine [a] [b] == combine [b] [a]

我认为在将递归函数折叠到输入系数的倍数的无穷列表上时，完全想到这个问题是很疯狂的.

I find it completely insane to think about this Problem in terms of folding a recursive function over a list of endless lists of multiples of input coefficients.

在我的系统上，它仍然比这里使用Data.List.Ordered提供的另一种解决方案慢大约10倍.

On my System it is still about a factor of 10 slower than another solution presented here using Data.List.Ordered.

这篇关于如何制作多个数字的倍数排序列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！