Iterator to traverse the binary tree

I need to generate an iterator that traverses a binary tree of n variables.

Where the parent node represents a function and the child node represents a value.

For example when n = 4, there are 5 constructors:

f(n,f(n,f(n,n)))
f(n,f(f(n,n),n))
f(f(n,n),f(n,n))
f(f(n,f(n,n)),n)
f(f(f(n,n),n),n)

How should I generate iterators for general cases?


Some hard coded attempts:

use std::slice::Iter;

fn catalan_tree3<T: Copy>() -> Iter<'static, fn(&[fn(T, T) -> T], &[T]) -> T> {
    // &[fn(&[fn(T, T) -> T; 2], &[T; 3]) -> T; 2]
    let fs: &[fn(&[fn(T, T) -> T], &[T]) -> T; 2] = &[
        |f, n| f[0](n[0], f[1](n[1], n[2])),
        |f, n| f[0](f[1](n[0], n[1]), n[2])
    ];
    return fs.iter();
}

fn catalan_tree4<T: Copy>() -> Iter<'static, fn(&[fn(T, T) -> T], &[T]) -> T> {
    // &[fn(&[fn(T, T) -> T; 3], &[T; 4]) -> T; 5]
    let fs: &[fn(&[fn(T, T) -> T], &[T]) -> T; 5] = &[
        |f, n| f[0](n[0], f[1](n[1], f[2](n[2], n[3]))),
        |f, n| f[0](n[0], f[1](f[2](n[1], n[2]), n[3])),
        |f, n| f[0](f[1](n[0], n[1]), f[2](n[2], n[3])),
        |f, n| f[0](f[1](n[0], f[2](n[1], n[2])), n[3]),
        |f, n| f[0](f[1](f[2](n[0], n[1]), n[2]), n[3]),
    ];
    return fs.iter();
}

fn catalan_tree<'a, T>(n: usize) -> Iter<'a, fn(&[fn(T, T) -> T], &[T]) -> T> {
    // I am not sure if such type annotation is appropriate
    unimplemented!()
}


#[test]
fn test() {
    use std::ops::{Add, Sub};
    let fs: Vec<fn(i32, i32) -> i32> = vec![Add::add, Sub::sub];
    let ns: Vec<i32> = vec![1, 2, 3];
    // for f in catalan_tree::<i32>(3)
    for f in catalan_tree3::<i32>() {
        println!("{}", f(&fs, &ns))
    }
}
1 Like

You want to generate a list of all binary trees with n nodes?

No, in most cases, I don't need to generate all of them.

In my needs, it can return when encounter the first solution.

Unless there is no solution, all possibilities will be traversed.

Now it is a vec, can such a triple loop be rewritten as an iterator?

pub fn generate(rank: usize) -> Vec<String> {
    if rank == 0 {
        return vec!["n".to_string()];
    }
    let mut ans = vec![];
    for i in 0..rank {
        for left in generate(rank - 1 - i) {
            for right in generate(i) {
                ans.push(format!("f({}, {})", left, right));
            }
        }
    }
    return ans;
}


pub fn generate_tree(rank: usize, f: usize, n: usize) -> Vec<String> {
    if rank == 0 {
        return vec![format!("n[{}]", n)];
    }
    let mut ans = vec![];
    for i in 0..rank {
        for left in generate_tree(rank - 1 - i, f + 1, f) {
            for right in generate_tree(i, f + 1, f + 1) {
                ans.push(format!("f[{}]({}, {})", f, left, right));
            }
        }
    }
    return ans;
}

#[test]
fn test() {
    println!("{:#?}", generate(3));
    println!("{:#?}", generate_tree(3, 0, 0));
}

Here’s a way to use iterators for this: (link to playground).

I’ve changed the functions into a special type, called Tree that has the advantage of being generically applicable. I’ve also generalized your &[fn(T, T) -> T] to impl Iterator<Item=impl FnOnce(T, T) -> T>. And the &[T] to impl Iterator<Item = T> and got rid of the Copy constraint on T.

A good thing that’s demonstrated here is that you can often build up Iterators from existing ones and don’t necessarily need to manually implement new ones. (Although the manual approach could sometimes be more efficient.)

1 Like

This seems more flexible.

But I still don’t understand how to use it:

use std::ops::{Add, Sub, Mul, Div};
use itertools::Itertools;

fn solvable(cards: &[i32], target: i32) -> bool {
    let mut f: Vec<fn(f32, f32) -> f32> = vec![Add::add, Sub::sub, Mul::mul, Div::div];
    let mut n: Vec<f32> = cards.iter().map(|&i| i as f32).collect();
    let mut fs = (0..cards.len()).map(|_| f.iter()).multi_cartesian_product();
    let mut ns = n.iter().permutations(cards.len());
    for tree in all_trees(cards.len() - 1) {
        if let Some(ans) = tree.apply::<f32>(&mut fs, &mut ns) {
            if (ans * 10000.0) as i32 == target * 10000 {
                return true;
            }
        }
    }
    return false;
}

fn main() {
    assert_eq!(solvable(&[1, 2, 3, 4], 24), true)
}

Why it shows that what I passed in is Vec<T>, but what I passed in is indeed T: IntoIterator

I don’t quite understand what specific problem you’re asking about and there’s multiple error messages in the code. Nonetheless, I fixed it until I got it working:

use std::ops::{Add, Sub, Mul, Div};
use itertools::Itertools;

fn solvable(cards: &[i32], target: i32) -> bool {
    let f: Vec<fn(f32, f32) -> f32> = vec![Add::add, Sub::sub, Mul::mul, Div::div];
    let n = cards.iter().map(|&i| i as f32);
    let fss = (0..cards.len()).map(|_| f.iter()).multi_cartesian_product();
    let nss: Vec<Vec<f32>> = n.permutations(cards.len()).collect();
    for fs in fss {
        for ns in &nss {
            for tree in all_trees(cards.len() - 1) {
                let ans = tree.apply(&mut fs.iter(), &mut ns.iter().copied()).unwrap();
                if (ans * 10000.0f32) as i32 == target * 10000 {
                    return true;
                }
            }
        }
    }
    return false;
}

fn main() {
    assert_eq!(solvable(&[1, 2, 3, 4], 24), true)
}

Of course such a brute-force search will quickly get very slow for larger inputs.

Note that for practicality, you might want to add a wrapper to apply that takes impl IntoIterator<Item=...> instead of &mut impl Iterator<Item=...> arguments. The type of apply as it is now is mostly for making the recursive calls possible. Edit: demonstrating the wrapper.

Just noticed, you need to call (and use) all_trees(cards.len()) for correct behavior. Also you can make all the fs one shorter using (1..cards.len()) or (0..cards.len()-1).