Looking for an algorithm that does some form of multiple product with backtracking

I'm hunting down an algorithms for the function I need to write, and it seems like it's some sort of multi product with backtracking, but I'm not sure.

Here's the intro.

I have two lists - sources (think, directories), and paths (to files). Each resource may be in each source, or not.
I need to build an iterator that returns a list of sources for each resource and can react to when a given source does not have a resource by pruning the whole branch.

As an example, I may have:

sources: [S1, S2]
paths: [R1, R2, R3]

In the optimistic scenario, my iterator should return:

  • [S1, S1, S1]
  • [S1, S1, S2]
  • [S1, S2, S1]
  • [S1, S2, S2]
  • ...

and so on. From what I can find so far, this is some version of multi product and itertools provide it. I'm not sure if it really is multi cartesian product, since cartesian product produces pairs, and I'm looking for list of sources for each path, so it doesn't need to be paths.

Now, the trick starts in that in my sequential code, some sources may not have the resource. Since I'm testing sequentially, I'd like to recognize that and "prune" that branch of iteration since the partial product cannot result in full product.

I'd also love to end up with an iterative, not recursive solution (I think it's given for Rust Iterator?).

Here's a playground of an example: Rust Playground in case someone with good algo skills likes challenges :slight_smile:

Can some point me in the right direction? What algorithms solve that? Is there something in rust, python, js etc. that I can look at?

Thank you,
zb.

I think this does the job (requires itertools):

    let available=&available_paths;
    let mut i = paths.iter().copied()
                     .map(|p| sources.iter().copied()
                                     .filter(move |&s| available[s][p]))
                     .multi_cartesian_product();

(Playground)

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.