Algorithm in java for complex ordering problem

[Alfa Riz]

Hi guys,

I am looking for some Java help from someone on sorting/ordering a list.

1. Lets say I have a list which is in this order: 8, 3, 6, 2

2. I then have a set of rules provided in no particular order

// rule1: move 8 after 6 (8 is at index 0)
// rule2: move 3 after 8 (3 is at index 1)
// rule3: move 2 after 3 (2 is at index 3)

How can we apply the rules above in a specific order to achieve the desired outcome of 6,8,3,2

Thanks,

Alfa

[Les Morgan]

looks like you have a pretty good solution there just by order the rules by the index, 2nd to last digit of rules.

[Alfa Riz]

Les Morgan wrote:looks like you have a pretty good solution there just by order the rules by the index, 2nd to last digit of rules.

It's not that simple, take this example, and based on what you said by executing the rules in the order of the source index

8,3,6,2
// rule: move 8 after 6 (8 is at index 0) = 3,6,8,2
// rule: move 3 after 8 (3 is at index 1) = 6,8,3,2
// rule: move 6 after 2 (6 is at index 2) = 8,3,2,6
// rule: move 2 after 3 (2 is at index 3) = 8,3,2,6

We end up with 8,3,2,6 but that's not right because the first rule says 8 should be after 6

[Piet Souris]

hi Alfa,

a way to automize this, although it is not a very efficient way, is to note that (in this case) the sorting order is: 6, 8, 3, 2.
So we can use a Comparator to sort the array. For instance:

public class AlfaRiz {
    public static void main(String... args) {
        var sortingOrder = List.of(6, 8, 3, 2);
        Comparator<Integer> c = Comparator.comparingInt(sortingOrder::indexOf);
        var a = Arrays.asList(2, 3, 8, 6, 2, 5, 10);
        var b = a.stream().sorted(c).collect(toList());
        System.out.println(a);
        System.out.println(b);
    }
}

[Norm Radder]

Welcome to the forum.

[Alfa Riz]

Piet Souris wrote:hi Alfa,

a way to automize this, although it is not a very efficient way, is to note that (in this case) the sorting order is: 6, 8, 3, 2.
So we can use a Comparator to sort the array. For instance:

public class AlfaRiz {
    public static void main(String... args) {
        var sortingOrder = List.of(6, 8, 3, 2);
        Comparator<Integer> c = Comparator.comparingInt(sortingOrder::indexOf);
        var a = Arrays.asList(2, 3, 8, 6, 2, 5, 10);
        var b = a.stream().sorted(c).collect(toList());
        System.out.println(a);
        System.out.println(b);
    }
}

Hi Piet, many thanks for your reply. The problem with this is that the "sorting order" can not be an input to the function (i.e, in my first post 6,8,3,2 is the output result). It is something that the function needs to figure out. Also, we are restricted to Java 7, is there further help you can give me?

[Piet Souris]

I think so. But in oder for the function to do a correct sort, it must know these rules. Are the rules in question specified as shown in your first post? If not, how are these specified?

[Norm Radder]

There is more background for this question here: http://www.javaprogrammingforums.com/collections-generics/42153-ordering-items-but-bit-more-complex-then-just-swapping-items.html

[Piet Souris]

Thanks for the info, Norm.

That raises a couple of questions:

1) why is the discussion continued here at CodeRanch?
2) is there some usecase that makes all this a little comprehensible? First of all, the rules like "one comes after three" depends on some order of the list. and secondly, it is a very labourious way of doing. Three, the user must have full control over the Employee list, in order to invoke the method "processAfter()".

So, this seems unrealistic to me. Normally, you would have one or more fields in the Employee class, on which employees can be compared, for instance salary, function, department, service years, age, whatever. There must be a way to keep the employees up to date. Then all that the user needs to specify is on what field(s) the employees should be sorted.

If there IS a clear usecase, then please specify.

Since Norm is very involved in this, I will leave further replying to him, if that's okay.

[Alfa Riz]

Hi Piet,

The initial list of id's is passed to me by an external systen, the external system does a default order/sort and passes it to me. I have no control of the external system.

What I am trying to do is allow my system and my users to be able to override the order. In my system, each id is represented as a trade. My users would flag something on trade X to indicate that they want it to process after trade Y. This is the challenge I am trying to work with.

Norm has been very helpful in trying to push the design and recommended I post this here. I understand it is laborious, but the users of my system only have access to flag fields on the trade, they can not input the order in some generic way anywhere. This is why I am trying to do it in this way. Any help appreciated.

Thanks,

Alfa

[Piet Souris]

I see. I apologize for having missed the last part of the JavaForum topic.

Well, sorting based on the index of an employee in the original list, or sorting based on a given id-order is equivalent qua complexity, but the second one seems more reliable, since the sorting then does not depend on some initial order of the list.

But if the user is able to supply a list of rules, like (1 after 2, 4 after 8, et ceera), then why not let the user give just one list like (8, 3, 7, 1, 0,...), to indicate that 3 comes after 8, 7 after 3, et cetera. That would be much less work and is much less errorprone.

Then you could have something like:

public class AlfaRiz {
    public static void main(String... args) {
        List<Integer> processOrder = Arrays.asList(6, 8, 3, 2);
        Comparator<Emp> c = new Comparator<>() {
            @Override
            public int compare(Emp a, Emp b) {
                int indexa = processOrder.indexOf(a.id);
                int indexb = processOrder.indexOf(b.id);
                if (indexa == -1) indexa = Integer.MAX_VALUE;
                if (indexb == -1) indexb = Integer.MAX_VALUE;
                return Integer.compare(indexa, indexb);
            }
        };
        List<Emp> emps = new ArrayList<>();
        for (int i = 1; i <= 10; i++) emps.add(new Emp(11 - i));
        List<Emp> b = new ArrayList<>();
        for (Emp a: emps) if (processOrder.contains(a.id)) b.add(a);
        b.sort(c);
        System.out.println(emps);
        System.out.println(b);
    }
    
    static class Emp {
        final int id;
        Emp(int x) {id = x;}
        @Override
        public String toString() {
            return "" + id;
        }
    }
}

[Alfa Riz]

Hi Piet,

Thank you for your time on the response, the code and thought is very much appreciated. When the user supplies the list of rules, he actually flags each individual rule on a trade in my system. So if there are 10 rules, he will make this flag/update on 10 trades. There is no way for him to push one list to me. This is the limitation here. I end up querying all trades and then accumulating a list of rules for adjusting the order.

Norm suggested something along the following:

Another idea for a design:
The original employee items are saved in a list.
Each employee record has a list of its own that contains the employees that must follow.
When a processAfter rule comes in, the referenced employee is removed from the original list and added to the individual employee's list.

This sounds interesting and like it could do the trick, especially when executing a "processAfter" on an object that was already "moved" by a previous "processAter" - any ideas on how we could code this one?

Thanks,

Alfa

[Piet Souris]

hi Alfa,

okay.

I do not like the idea to use an instance of an Employee as indication in what order it should be processed, unless you can show me the real usecase. I must admit that I still do not understand how the real thing operates.

Suppose the rules are given in the form (x, y), meaning "x must be processed after y". It is a straightforward task to turn that into the list that I was talking about. If this list of Rules is a valid one, then there must be an y in this list of Rules that does not appear as x. For instance: if we have these Rules:

(3, 5), (5, 12), (2, 3)

then the x-list is {3, 5, 2} and the y-list is {5, 12, 3}.

As we see, 12 is the value in the y-list that does not appear lin the x-list, so that's our starting point. Now, look up the Rule that has 12 as y value. We find (5, 12). That means that 5 is our next "victim". Look up 5 as right element in the rules. We find the Rule (3, 5). So, 3 is next. And in the same fashion, we find 2 as our last number. So the processlist = {12, 5, 3, 2}. And then you can proceed in the way I described.

If all this is still not correct, then probably Norm is understanding your mission better than I do. Can you give an example of the original list, and what the external users do to this list (i. e. the rules), and when the moment arrives for you to do the processing? A small example would be fine.

[Alfa Riz]

Hi,

I finally got this working based on Nord's idea. However, one last thing I need help with is how to turn the printListRecursively function into a function that returns a new LinkedList ?

   private static void printListRecursively(LinkedList<Deal> list)
   {
       for (Deal d : list)
       {
           System.out.println(d.getDealNum());
           
           printListRecursively(d.getFollowedBy());
       }
   }

This is the last part I'm stuck on.

The program now prints below which is expected, but I just need a final LinkedList for the "before" bit

Before:
2
4
7
3
After:
3
4
2
7

import java.util.LinkedList;

public class Deal 
{
	private int dealNum;
	private LinkedList<Deal> followedBy;
	
	public Deal(int dealNum)
	{
		this.dealNum = dealNum;
		
		followedBy = new LinkedList<Deal>();
	}
	
	public int getDealNum()
	{
		return this.dealNum;
	}
	
	public void addToList(Deal d)
	{
		followedBy.add(d);
	}
	
	public LinkedList<Deal> getFollowedBy()
	{
		return this.followedBy;
	}
}

import java.util.LinkedList;

public class JavaTestPlugin 
{
	public static void main(String[] args) 
	{
		Deal two = new Deal(2);
		Deal four = new Deal(4);
		Deal seven = new Deal(7);
		Deal three = new Deal(3);
		
		// Add to linked list in the order defined above
		LinkedList<Deal> originalList = new LinkedList<>();
		originalList.add(two);
		originalList.add(four);
		originalList.add(seven);
		originalList.add(three);
		
		System.out.println("Before:");
		for (Deal e : originalList)
		{
			System.out.println(e.getDealNum());        
		}
		
		// process 4 after 3
		three.addToList(four);
		
		// process 2 after 4
		four.addToList(two);
		
		// process 7 after 4
		four.addToList(seven);
		
		originalList.remove(1);
		originalList.remove(0);
		originalList.remove(0);
		
		System.out.println("After:");
		printListRecursively(originalList);
	}
	
	
	private static void printListRecursively(LinkedList<Deal> list) 
	{ 
		for (Deal d : list)
		{
			System.out.println(d.getDealNum());
			
			printListRecursively(d.getFollowedBy());
		}
	}
}

[Norm Radder]

What is the purpose of the statements on lines 34 to 36?  
It looks like the code is hardcoded for ONE order of events.  What happens when the ordering is different?

[Piet Souris]

Is this useful for the general case?

Here's what I would do. First, determine where to start. I suppose you have a List A of all the Deals that must be processed, now make a second List B of all the Deals that are present in all the followdBy Lists of every Deal in List A. Then determine what Deals are in A that are not in the followdBy List B. Look at the removeAll-method of Lists for an easy way to do this. Normally, the resulting List of starting Deals will not be empty. But, life ain't that simple, decide what to do if you do find this starting list to be empty.

For this to work you must override the equals method in the Deal class. When are two Deals equal?

Now you can form, say, a Queue<Deal>, where you put the starting Deals in. Then, while the Queue is not empty, remove the head, execute it, put the follwedBy Deals into the Queue, and proceed until the Queue becomes empty.

[Alfa Riz]

Norm Radder wrote:What is the purpose of the statements on lines 34 to 36?  
It looks like the code is hardcoded for ONE order of events.  What happens when the ordering is different?

It's just an example for the forum. I remove the deals from the original list and add them to the followedBy lists instead. In reality there will be more code.

Can someone give me an example of how to recursively return a  linkedlist in the example i've given please?

[Norm Radder]

Why recursive?  Would a loop do?

[Alfa Riz]

Norm Radder wrote:Why recursive?  Would a loop do?

Shouldnt it be recursive if embedded deals have followedBy lists, and if the deals in those lists have further embedded followedBy lists?

Can you give me an example of how we could loop recursively please norm?

[Norm Radder]

loop through the list item by item
if an item has a list, loop through the items in that list

[Alfa Riz]

Norm Radder wrote:loop through the list item by item
if an item has a list, loop through the items in that list

Hi Norm - that would be 2 loops? What if there are further lists items in the last set of items? Maybe i am misunderstanding something here?

Pseudo code:

For (Deal d : someList)
{
//d.getDealNum()
anotherList = d.getFollowedBy()

For (Deal x : anotherList) // do something with x but the x's may have further lists? I can't keep declaring loops?
}

[Norm Radder]

Right, if followers can have followers that have followers etc.
Back to the drawing board.

Does the currently posted code support that?

[Alfa Riz]

Norm Radder wrote:Right, if followers can have followers that have followers etc.
Back to the drawing board.

Does the currently posted code support that?

Yes it will.

I just need a recursive function to be able to read all objects and inner items from the objects - can you help with that?

[Norm Radder]

Write the code to generate that case requiring the recursive search.
By the time you have code that requires recursive search someone will have worked on a solution.

[Alfa Riz]

Can anyone else help me with changing the function below to return a LinkedList instead? At the moment I have it recursively printing the items, but not sure how to have it pop and add the items to a linkedlist that is instantiated outside of the recursive function?

Any help is much appreciated.

    private static void printListRecursively(LinkedList<Deal> list) 
    { 
        for (Deal d : list)
        {
            System.out.println(d.getDealNum());
             
            printListRecursively(d.getFollowedBy());
        }
    }

[Norm Radder]

In your print method, instead of printing the items, add them to the list.  Pass the list to the method.

[Piet Souris]

You do not need a recursive function. In my reply I used a Queue for this purpose.

I wrote a little code to illustrate what I was writing about:

public static void processDeals(List<Deal> deals) {
    // determine where to start
    List<Deal> original = new ArrayList<>(deals);
    List<Deal> allFollowers = new ArrayList<>();
    for (Deal d: original) allFollowers.addAll(d.followedBy);
    original.removeAll(allFollowers);
    if (original.isEmpty()) throw new RuntimeException("no starting deal found!!!!");
    // now start a queue of Deals
    LinkedList<Deal> queue = new LinkedList<>();
    queue.addAll(original);
    while (!queue.isEmpty()) {
        Deal d = queue.removeFirst();
        System.out.println(d);
        queue.addAll(d.followedBy);
    }
}

The idea is that if I have a List<Deal> deals, then I first want to determine where to start. So, I create a second list (allFollowers) and I put all the Deals in it that are in all the followedBy-lists. Now, all that is left to determine the starters is to remove from the total list all the deals that are in the allFollowers list.

In order to be able to remove Deals from a Deal-list, I must override the 'equals' method in the Deal-class.

Now, having a List of Deals to start with, I put these in a Queue<Deal>. For this I use a LinkedList. And then it is simply a while-loop:
while the queue is not empty
   remove the head of the queue
   do whatever must be done with that Deal
   put all the Deals from head.followedBy in the queue
end while.

My provisional code is this:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 *
 * @author Piet
 */
public class AlfaRiz {
    
    public static void main(String... args) {
        Deal one = new Deal();
        Deal two = new Deal();
        Deal three = new Deal();
        Deal four = new Deal();
        Deal five = new Deal();
        Deal six = new Deal();
        Deal seven = new Deal();
        Deal eight = new Deal();
        Deal nine = new Deal();
        Deal ten = new Deal();
        one.addFollower(four);
        one.addFollower(five);
        one.addFollower(six);
        two.addFollower(one);
        four.addFollower(seven);
        five.addFollower(eight);
        eight.addFollower(ten);
        List<Deal> deals = Arrays.asList(one, two, three, four, five, six, seven, eight, nine, ten);
        processDeals(deals);
    }
    
    static class Deal {
        private static int idTotal = 1;
        private final int id;
        public final String name;
        private List<Deal> followedBy = new ArrayList<>();
        
        Deal() {
            id = idTotal;
            name = "" + id;
            idTotal++;
        }
        
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || !(o instanceof Deal)) return false;
            return id == ((Deal) o).id;
        }

        @Override
        public int hashCode() {
            int hash = 5;
            hash = 83 * hash + this.id;
            return hash;
        }
        
        public boolean addFollower(Deal d) {
            if (followedBy.contains(d)) return false;
            followedBy.add(d);
            return true;
        }
        
        @Override
        public String toString() {
            return name;
        }
    }
        
    public static void processDeals(List<Deal> deals) {
        // determine where to start
        List<Deal> original = new ArrayList<>(deals);    // just making a copy of the input list
        List<Deal> allFollowers = new ArrayList<>();
        for (Deal d: original) allFollowers.addAll(d.followedBy);
        original.removeAll(allFollowers);
        if (original.isEmpty()) throw new RuntimeException("no starting deal found!!!!");
        // now start a queue of Deals
        LinkedList<Deal> queue = new LinkedList<>();
        queue.addAll(original);
        while (!queue.isEmpty()) {
            Deal d = queue.removeFirst();
            System.out.println(d);    // or whatever
            queue.addAll(d.followedBy);
        }
    }
}

Possible problems?

Yes. Suppose I have these Deals: 1 -> {4, 5}, and 5 -> {4}. This will cause that 4 wil be processed twice, because it comes after 1 and also after 5. Does your system have some detection for this? And what idf we have 1 -> {1, 4, 5}, causing an infinite loop?
There are ways to detect situations like these. And maybe your system of setting up these Deal lists does some checking of what is allowed.