I'm sorry the title is so vague ... I cannot think how to describe it any better.

I have a collection in this format:

var myCollection = [{id:"a"}, {id:"b",excludes:["a"]}, {id:"c",excludes:["b"]}];

What I want after running my algorithm is to see this:

processedCollection = [{id:"a"}, {id:"c",excludes:["b"]});

Alternatively, if "c" hadn't existed, then only "b" would be visible. I hope that makes sense. It's further complicated by the possibility that any item in the collection could exclude multiple other items (hence why it's an array).

NOTE: I do NOT have to worry about circular references, as it is reasonable in this instance to expect only good data to come into my algorithm.

I've attempted to construct an appropriate function but am coming unstuck. I'd figured I would first run through the collection and create an excludedBy parameter on each item, and to then run through again, outputting the correct result, but it's not quite so simple.

Any help would be much appreciated. I'm hoping very much that this is a known problem with defined algorithm(s) to deal with it! Thank you in advance!

  • 3
    You have exclusion rules for a and b, but your output is supposed to contain a and not b. Why? Please elaborate. – Kilian Foth Mar 6 '15 at 15:37
  • ... because c has excluded b, which was the only item that excluded a. Because b no longer exists, the exclusion for a is no longer in effect. Had c wanted a also excluded, its exclusions would have been ["a","b"] not ["b"]. – Martin Mar 6 '15 at 15:54
  • 1
    So the specification is that you iterate from the right? Because if you started from the left, you'd end up with only c, wouldn't you? – Kilian Foth Mar 6 '15 at 16:01
  • A "holistic" approach is needed that analyses the collection as whole, as the order cannot be guaranteed. The reason c wins here is because nothing excludes it, therefore it must be present, and because it is present then b must therefore be excluded. I never said it was a simple algorithm I required! :) – Martin Mar 6 '15 at 16:07
  • You might be able to go from left to right, as it were, but you would have to be able to revisit previous decisions if they were later invalidated. It doesn't feel like that's the right approach, but of course I could be wrong. – Martin Mar 6 '15 at 16:08

I would think of it as a graph:


Creating a topological sorting would give you a valid order to process the nodes in. Note there can be multiple topological sorts. Whether you need to worry about that depends on if you need one solution or all the solutions.

In this case, there is only one topological sort: c, b, a. You start with c, add it to the output, and remove all its direct children from the graph. The next non-removed node in the sorting is a, which has no children, so you just add it to the output. No nodes remain in the topo sort, so you're done.

  • I've created a codepen with, what I believe to be, an appropriate algorithm. I'd welcome your opinion on whether it seems robust and generic enough. You can find it here. – Martin Mar 8 '15 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.