CODEWITHSUNDEEP
iphoneobjective-cxcodealgorithm
Andrew Robinson
Andrew Robinson

Reputation: 3434

Algorithm Based Sorting / Re-Ordering of objects based on allowed following objects

I have a need to develop an algorithm that will take a set of unordered objects and re-order them intelligently based on the objects they are allowed to proceed to.

My initial design/thought is to use Core Data to store an entity (for instance "Objects") with a to-many relationship ("canGoTo") back on itself with a set of objects that can follow the selected Objects *object.

Consider the following example where each object has a set of objects in which it can proceed to (the actual set of objects is much larger).

Object A - can go to -> Objects B,C,D
Object B - can go to -> Objects E,F,G,Y,H
Object C - can go to -> Objects P,S,Z
Object D - can go to -> Objects H,J,X
...
Object G - can go to -> Objects R,Y,Z
Object H - can go to -> Objects G,Z
...
Object Y - can go to -> Objects Z
Object Z - can go to -> Objects NULL (no objects follow this object)

If the program is given a set of Objects (R,B,H,G,A,Z) the program needs to find how to re-order the objects to find an acceptable structure. Thus the correct outcome for this set would be A->B->H->G->Y->Z

What strategy is the best, or most efficient, to flow through this issue? Should I be looping through re-orders and quitting when I successfully touch all objects in a pass? Using a genetic algorithm to generate output and analyzing generations (i.e. http://ijoshsmith.com/2012/04/08/simple-genetic-algorithm-in-objective-c/)? Or do I use an Insertion Sort to analyze all objects and re-order the object to where it can fit in the sequence? Keep in mind the real list of objects will be more like 30+ objects long instead of 6, and in a perfect world the program would pick the BEST way to order the list (maybe based on "canGoTo" priority).

Any advice/best practices would be greatly appreciated. Sorry for no sample code, this is in the thought phase at the moment.

Upvotes: 4

Views: 227

Answers (1)

alestanis
alestanis

Reputation: 21863

You can model your problem as a Directed Acyclic Graph and then do Topological Sorting on it. This will give the exact output you are looking for.

Upvotes: 1

Related Questions