CODEWITHSUNDEEP
rust
user1002430
user1002430

Reputation:

How to implement the subsequences iterator in Rust?

I want to implement an iterator that produces all the subsequences of an input sequence. Some examples:

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]]

The Haskell implementation of this is very straightforward:

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

I just cannot seem to figure out how to recreate this in Rust. I figure it should have the following signature so that it can produce very long sequences without unnecessary memory allocations.

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

Any guidance?

Upvotes: 1

Views: 118

Answers (3)

rodrigo
rodrigo

Reputation: 98526

It looks like that is exactly what itertools::powerset does (playground):

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']

The returned value is a Powerset<I> (being I the input type), that implements Iterator<Item = Vec<<I as Iterator>::Item>>, and skimming through the implementation it looks like it does not preallocate the replies, but it computes them on the fly.

Upvotes: 1

rodrigo
rodrigo

Reputation: 98526

Your code in haskell and what you want seems different, isn't the haskell missing the empty subset in [[a]] ([[], [a]])?

Anyway, a more or less direct translation to Rust would be something like this (playground):

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']
[]

Note that Haskell is optimized to add values at the front of a list, while Rust is best adding to the end of a Vec so the order of the output is inverted.

It is not easy avoding the allocations because you must store the values you want to return somewhere. Maybe you could return a value that implements an impl Iterator<Item: Iterator<A>> that avoids the allocations but that would require a very different algorithm.

Upvotes: 0

Nikolay Zakirov
Nikolay Zakirov

Reputation: 1584

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<_>>());
        }
    }
}

Test Output:

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

Upvotes: 1

Related Questions