Hello,
Let's say that I have a vector
let x = vec![0, 1, 2];
and I want to iterate over all the subvectors. That is, I want to iterate over
[], [0], [1], [2], [0, 1], [0, 2], [1, 2], [0, 1, 2]
I have some idea on how to implement this, but I'm not sure they are really idiomatic.
Do you have any suggestion?
Thank you!
You could flat_map
increasing lengths of Itertools::combinations
.
2 Likes
Actually, tuple combinations of slice indexes might work better, something like:
let x: Vec<_> = ...;
let iter = (0..=x.len()).tuple_combinations().map(|(start, end)| &x[start..end]);
I've implemented the first solution. Work pretty fine. I will take a look at the second option. Thanks!
Finn
July 2, 2019, 6:09pm
5
fn power_set<T: Clone>(a: &Vec<T>) -> Vec<Vec<T>> {
a.iter().fold(vec![vec![]], |mut p, x| {
let i = p.clone().into_iter()
.map(|mut s| {s.push(x.clone()); s});
p.extend(i); p})
}
fn main() {
println!("{:?}",power_set(&vec![0,1,2]));
}
minor nit: Never use &Vec<T>
it has no benefits over &[T]
and prevents other types that can be coerced to a slice from being used.
fn power_set<T: Clone>(a: &[T]) -> Vec<Vec<T>> { ... }
Finn
July 2, 2019, 6:35pm
7
Then by further nitpicking,
fn power_set<T: Clone>(a: impl Iterator<Item=T>) -> Vec<Vec<T>>
Well, if were going there it should be IntoIterator
to seemlessly allow most collections. But I think changing to a slice is enough for many uses cases.
With slices, we don't need any allocation:
fn power_set<'a, T>(a: &[T]) -> impl Iterator<Item = &[T]> {
std::iter::once([].as_ref()).chain(
(0..a.len()).flat_map(move |start| {
(start + 1..=a.len())
.map(move |end| &a[start..end])
})
)
}
Or with itertools
:
fn power_set<'a, T>(a: &[T]) -> impl Iterator<Item = &[T]> {
std::iter::once([].as_ref()).chain(
(0..=a.len())
.tuple_combinations()
.map(move |(start, end)| &a[start..end])
)
}
2 Likes
This doesn't produce [0, 2]
when you feed it the input &[0, 1, 2]
1 Like
Oh, right -- I got all subslices, but you can't get all combinations this way.
Finn
July 2, 2019, 9:05pm
13
A lazy variant:
#![feature(generators, generator_trait)]
fn power_set<T: Clone>(a: impl IntoIterator<Item=T>)
-> impl Iterator<Item=Vec<T>>
{
IteratorAdapter(|| {
let mut p = vec![vec![]];
yield vec![];
for x in a.into_iter() {
let b: Vec<_> = p.clone().into_iter()
.map(|mut s| {s.push(x.clone()); s}).collect();
for t in b.clone() {yield t;}
p.extend(b);
}
}).into_iter()
}
fn main() {
for t in power_set(0..).take(8) {
println!("{:?}",t);
}
}
struct IteratorAdapter<G>(G);
impl<G> Iterator for IteratorAdapter<G>
where G: std::ops::Generator<Return=()> + Unpin
{
type Item = G::Yield;
fn next(&mut self) -> Option<Self::Item> {
match std::pin::Pin::new(&mut self.0).resume() {
std::ops::GeneratorState::Yielded(item) => Some(item),
std::ops::GeneratorState::Complete(_) => None,
}
}
}
1 Like
Finn
July 2, 2019, 9:24pm
14
The same in Moss :
function power_set(a)
fn*||
p = [[]]
yield []
for x in a
b = p.map(|s| s+[x])
for t in b do yield t end
p.push(*b)
end
end
end
for t in power_set(0..).take(8)
print(t)
end
Thank you all for the answers. I wasn't expecting that much!
system
Closed
October 1, 2019, 3:18pm
16
This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.