创建一个scala函数，生成长度为N的整数的有序列表
[英]create a scala function that generates ordered list of integers of length N
Suppose I have a simple function that builds an iterator of all the lists of two positive integers (x,y) that are <1000 and have x <= y
假设我有一个简单的函数，它构建一个迭代器，该迭代器包含两个正整数(x,y)，它们都<1000，并且x <= y
def twoIntsIterator(): Iterator[List[Int]] = {
for {
x <- Iterator.range(1, 1000)
y <- Iterator.range(x, 1000)
} yield List(x, y)
}
How would you implement a function intsListIterator(n: Int, limit: Int) that geneneralizes the list creation to lists of variable length? Such a function would produce the same output of the one above for n=2 and limit=1000. If called with n=3 and limit=4 it would return an iterator that produces the following:
如何实现一个函数intsListIterator(n: Int, limit: Int)，使列表的创建成为可变长度的列表?这样的函数在n=2和limit=1000下的输出是相同的。如果用n=3和limit=4调用它，它将返回一个迭代器，该迭代器将生成以下内容:
List(1,1,1)
List(1,1,2)
List(1,1,3)
List(1,2,2)
List(1,2,3)
List(1,3,3)
List(2,2,2)
List(2,2,3)
List(2,3,3)
List(3,3,3)
N.B.: I used iterators but they could have been views, the point is the variable list length
注意::我使用了迭代器，但它们可以是视图，关键是变量列表的长度。
4 个解决方案
#1
3
Just use recursion:
用递归:
def produce(n: Int, limit: Int, k: Int = 1): Iterator[List[Int]] = {
Iterator.range(k, limit) flatMap {
case x if n > 1 => produce(n - 1, limit, x).map(x :: _)
case x => Iterator(List(x))
}
}
Or with for-comprehension:
或者对于理解:
def produce(n: Int, limit: Int, k: Int = 1): Iterator[List[Int]] = for {
x <- k to limit - 1 iterator;
y <- if (n > 1) produce(n - 1, limit, x) else Iterator(Nil)
} yield x :: y
#2
4
Here is my solution:
这是我的解决方案:
scala> def gen(n: Int, limit: Int): Iterator[List[Int]] = n match {
| case 0 => Iterator(Nil)
| case _ => for(t <- 1 to limit iterator;s <- gen(n-1, t)) yield s:+t
| }
EDIT The following method generating all Lists with size n and its elements satisfy start <= x < end, you can def intsListIterator by
编辑以下方法，生成大小为n的所有列表，其元素满足start <= x < end，您可以通过def intsListIterator
def intsListIterator(n: Int, limit: Int) = gen(n, 1, limit)
scala> def gen(n: Int, start: Int, end: Int): Iterator[List[Int]] = n match {
| case 0 => Iterator(Nil)
| case _ => for(i <- Iterator.range(start, end);s <- gen(n-1,i,end)) yield i::s
| }
gen: (n: Int, start: Int, end: Int)Iterator[List[Int]]
scala> gen(3, 1, 4) foreach println
List(1, 1, 1)
List(1, 1, 2)
List(1, 1, 3)
List(1, 2, 2)
List(1, 2, 3)
List(1, 3, 3)
List(2, 2, 2)
List(2, 2, 3)
List(2, 3, 3)
List(3, 3, 3)
scala> gen(7, -3, 4) take 10 foreach println
List(-3, -3, -3, -3, -3, -3, -3)
List(-3, -3, -3, -3, -3, -3, -2)
List(-3, -3, -3, -3, -3, -3, -1)
List(-3, -3, -3, -3, -3, -3, 0)
List(-3, -3, -3, -3, -3, -3, 1)
List(-3, -3, -3, -3, -3, -3, 2)
List(-3, -3, -3, -3, -3, -3, 3)
List(-3, -3, -3, -3, -3, -2, -2)
List(-3, -3, -3, -3, -3, -2, -1)
List(-3, -3, -3, -3, -3, -2, 0)
#3
2
Well this works:
这工作原理:
def intsIterator(n: Int, limit: Int) = (1 to n).map(List.fill(limit)(_)).flatten.combinations(limit).filter(l => (l, l.tail).zipped.forall(_ <= _))
scala> intsIterator(5,3) mkString "\n"
res16: String =
Vector(1, 2, 3)
Vector(1, 2, 4)
Vector(1, 2, 5)
Vector(1, 3, 4)
Vector(1, 3, 5)
Vector(1, 4, 5)
Vector(2, 3, 4)
Vector(2, 3, 5)
Vector(2, 4, 5)
Vector(3, 4, 5)
Basically you get a combination i.e. n C limit and then you filter based on if a list is sorted or not.
基本上你会得到一个组合，即n C极限然后根据列表是否排序进行过滤。
Or a more readable version:
或更可读的版本:
def intsIterator(n: Int, limit: Int) = (1 to n).map(List.fill(limit)(_)).flatten.combinations(limit).filter(l => l.sorted == l)
#4
0
If efficiency or scalability where important I would act on Vectors, I wouldn't use recursion and create an Iterator instead of a List
如果效率或可伸缩性很重要，我将对向量进行操作，那么我不会使用递归并创建迭代器而不是列表
new Iterator() {
val max = limit - 1 // makes logic simpler
var cur = Vector.fill(n - 1)(1) :+ 0
var (i, v) = (n - 1, 1)
def hasNext(): Boolean = cur.head != max
def next(): List[Int] = {
if (v <= max)
cur = cur.updated(i, v)
else {
i -= 1
if (cur(i) == max - 1)
cur = cur.update(i, max)
else {
v = cur(i) + 1
cur = cur.take(i) ++ Vector.fill(n - i)(v)
i = n - 1
}
}
v += 1
cur.toList // you could leave as a Vector
}
}
Of course you could always turn this into a List with toList
当然你可以把它变成一个有toList的列表
(Not tested; wrote with phone)
(不是测试;写有电话)
注意！
本站翻译的文章，版权归属于本站，未经许可禁止转摘，转摘请注明本文地址：http://www.silva-art.net/blog/2014/09/13/d36386cd7803bd8b39be365ac73a73cb.html。