如何在Rust中实现子序列迭代器

Question

我想要实现一个迭代器，它可以生成输入序列的所有子序列。一些例子：

subsequences "abc"
["","a","b","ab","c","ac","bc","abc"]
subsequences [1,2]
[[],[1],[2],[1,2]]
subsequences [1,2,3]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
subsequences [1,2,3,4]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3],[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4]]

这方面的Haskell实现非常简单：

subsequences            :: [a] -> [[a]]
subsequences xs         =  [] : nonEmptySubsequences xs
nonEmptySubsequences         :: [a] -> [[a]]
nonEmptySubsequences []      =  []
nonEmptySubsequences (x:xs)  =  [x] : foldr f [] (nonEmptySubsequences xs)
where f ys r = ys : (x : ys) : r

我似乎不知道如何在Rust中重现这一点。我认为它应该有以下签名，这样它就可以在没有不必要的内存分配的情况下生成非常长的序列。

fn subsequences<A: Copy>(xs: &[A]) -> impl Iterator<Item=impl Iterator<Item=A>>;

有什么指导吗？

Answer 1

fn subsequences<A: Copy>(xs: &[A]) -> impl Iterator<Item=impl Iterator<Item=A>+ '_> {
// return all subsequences of a given sequence
let n = xs.len();
(0..1 << n).map(move |i| {
(0..n).filter(move |j| i & (1 << j) != 0).map(move |j| xs[j])
})
}
mod tests {
use super::*;
#[test]
fn test_subseq() {
let xs = [1, 2, 3];
let mut it = subsequences(&xs);
for _ in 0..8 {
println!("{:?}", it.next().unwrap().collect::<Vec<_>>());
}
}
}

测试输出：

[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]

Answer 2

看起来这正是itertools:：powerset所做的(操场(：

use itertools::Itertools;
fn main() {
for s in ['a', 'b', 'c'].into_iter().powerset() {
println!("{:?}", s);
}
}
[]
['a']
['b']
['c']
['a', 'b']
['a', 'c']
['b', 'c']
['a', 'b', 'c']

返回的值是一个Powerset<I>(I是输入类型(，它实现了Iterator<Item = Vec<<I as Iterator>::Item>>，浏览实现时，它看起来并没有预先分配回复，而是动态计算回复。

Answer 3

您在haskell中的代码和您想要的似乎有所不同，难道haskell不缺少[[a]]([[], [a]](中的空子集吗？

无论如何，或多或少直接翻译成Rust应该是这样的(操场(：

fn subsequences<A: Copy>(xs: &[A]) -> Vec<Vec<A>> {
match xs {
[] => vec![],
[x] => vec![vec![*x], vec![]],
[xs@.., x] => {
subsequences(xs).into_iter()
.fold(vec![],
|mut r, ys| {
let mut ys0 = ys.clone();
ys0.push(*x);
r.push(ys0);
r.push(ys);
r
})
}
}
}
fn main() {
for s in subsequences(&['a', 'b', 'c']) {
println!("{:?}", s);
}
}
['a', 'b', 'c']
['a', 'b']
['a', 'c']
['a']
['b', 'c']
['b']
['c']
[]

请注意，Haskell被优化为在列表的前面添加值，而Rust最好添加到Vec的末尾，这样输出的顺序就会颠倒。

避免分配并不容易，因为必须将要返回的值存储在某个地方。也许您可以返回一个实现impl Iterator<Item: Iterator<A>>的值，该值可以避免分配，但需要一个非常不同的算法。