[Java] Nodes (Circularly Linked Lists)

Got questions? Got answers? Go here for both.

Moderator: MaxCoderz Staff

User avatar
Wesley
Regular Member
Posts: 137
Joined: Sun 12 Oct, 2008 1:42 am
Location: Boise, Idaho
Contact:

[Java] Nodes (Circularly Linked Lists)

Post by Wesley »

Okay, I have been developing a program to connect points in a "Tour" with the use of nodes. My project deals with the TSP (Traveling Salesman Problem).

I have implemented both the Nearest Insertion Heuristic and the Smallest Insertion Heuristic. However, I want to develop a way to manage the nodes by brute force to find the best possible tour. So there will be n! different paths to be traversed.

What is a good way to move nodes around to get all the possibilities? I know I could reduce this to (n-1)! ways pretty easily, but brute force goes through EVERY possibility. Any good ideas on moving nodes around for this case (including the first node)?

My nodes are defined as follows:

Code: Select all

private Node first;

private static class Node {
        private Point p;
        private Node next;
}
Where Point signifies x and y coordinates on a graph. Node next is the pointer for the next node.

Could I use brute force with this definition, or would I need a doubly-linked list?
ImageImage
ImageImage
Image
King Harold
Calc King
Posts: 1513
Joined: Sat 05 Aug, 2006 7:22 am

Re: [Java] Nodes (Circularly Linked Lists)

Post by King Harold »

You can use brute force no matter how you store your node-order, it just affects the speed.

Personally, I would use factoradic numbers for a brute force search (because they take less bookkeeping, and you can can increment them to get the next permutation)
User avatar
Wesley
Regular Member
Posts: 137
Joined: Sun 12 Oct, 2008 1:42 am
Location: Boise, Idaho
Contact:

Re: [Java] Nodes (Circularly Linked Lists)

Post by Wesley »

My only problem is actually knowing how to shuffle ALL the nodes around to create an entirely different circularly linked list of nodes.

Say I have 4 nodes. Then there are (n-1)! = (4-1)! = 6 different possibilities of the best path that can be traversed. So we can label these nodes A, B, C, and D. Our 6 different possibilities would be:

ABCD
ACBD
ACDB
ADCB
ADBC
ABDC

Notice how I shift one node until it hits the end, then I go back until right after A (the first node) and shift the next one? I do this until the original last node is at position n-1. For instance:

ABCD
-^
ACBD
--^
ACDB
---^
ADCB
--^
ADBC
---^
ABDC
--^
^ is the cursor. That is how I want to move my nodes, but I can't come up with the algorithm to actually move them around.
ImageImage
ImageImage
Image
King Harold
Calc King
Posts: 1513
Joined: Sat 05 Aug, 2006 7:22 am

Re: [Java] Nodes (Circularly Linked Lists)

Post by King Harold »

Ah well, no offense, but you're really reinventing the wheel here, using factoradic numbers is very easy and efficient and guarantees that you will in fact test every possible permutation and never more than once

If you really want to continue this way I will try to think of an answer, but I have to go for dinner now ( :( )

Good luck in any case :)
User avatar
Wesley
Regular Member
Posts: 137
Joined: Sun 12 Oct, 2008 1:42 am
Location: Boise, Idaho
Contact:

Re: [Java] Nodes (Circularly Linked Lists)

Post by Wesley »

King Harold, that would be awesome! If you could explain of course :P. I just found a HUGE error in my algorithm. I figured out how to move my nodes, but my algorithm only works for n<5.

I'm not exactly sure how the factoradic idea would work here, though.

I don't need code or anything, I just need to think of an algorithm. Once I got the algorithm, it won't be too difficult to put it into code.

Also, is there a way I could use the factoradic idea and always keep my first node in the first position?

I can keep track of the following:
The first node.
The last node.
A cursor node.
A second cursor node before the cursor node.
A third cursor node after the cursor node.

I'm not sure if that's the best way to do it, but I like it that way :).

Well, thanks for the help so far!
ImageImage
ImageImage
Image
polarBody
New Member
Posts: 23
Joined: Wed 02 Sep, 2009 3:01 pm
Location: Chicago, IL

Re: [Java] Nodes (Circularly Linked Lists)

Post by polarBody »

If I understand your question correctly, if given nodes ABCDE, you want to find all possible permutations of BCDE, since A will always be first. Of course, you want a general algorithm involving n nodes, but for now, let's consider just 4 nodes and then generalize.

First off, what are the permutations of nodes DE? This one's easy:

DE
ED

Next, let's introduce C into the list of permutations above. How do we do that? Take the first permutation of DE and insert C into the beginning, middle, and end, and then repeat that process with the second permutation of DE like so:

CDE
DCE
DEC

CED
ECD
EDC

Next, let's introduce B into the latest permutations list, using the same procedure as above:

BCDE
CBDE
CDBE
CDEB

BDCE
DBCE
DCBE
DCEB

etc. (there would be 24 permutations if we followed through)

Notice how when we add a new element, it added in a diagonal pattern for each permutation of the previous elements. To complete this problem, you would simply slap an A in front of each of the 24 permutations found in the last step. This procedure that we followed can be generalized to n elements, and suggests a recursive algorithm. I hope this is what you needed, and let me know if you need further help.
User avatar
Wesley
Regular Member
Posts: 137
Joined: Sun 12 Oct, 2008 1:42 am
Location: Boise, Idaho
Contact:

Re: [Java] Nodes (Circularly Linked Lists)

Post by Wesley »

Okay, I'm not sure if this can be done with a singularly linked list... Going off this method, how would this be done with being able to move ALL the nodes, starting from A, instead of E?

I was thinking earlier today that this is how it should be done, but I couldn't rap my head around how to move my nodes. I knew how to move my nodes for my first algorithm, but this is completely different.
ImageImage
ImageImage
Image
polarBody
New Member
Posts: 23
Joined: Wed 02 Sep, 2009 3:01 pm
Location: Chicago, IL

Re: [Java] Nodes (Circularly Linked Lists)

Post by polarBody »

Oh, okay. I see the problem with the algorithm I gave you. This problem is still do-able using singly linked lists and my algorithm, but it would be horribly space-inefficient. To implement it, you would need to create an array of (n - 1)! nodes, run the algorithm so that each element of the array holds a linked list with a different permutation of nodes, then run through each linked list to calculate the shortest path. Yikes! Anything above 10! and the average computer nowadays would start thrashing if you tried running such an algorithm. It's a memory hog, for sure.

I can see now that you were trying to come up with an iterative algorithm where you shift the nodes one at a time and calculate the path for each iteration. I remember trying to come up with a similar algorithm not too long ago, but I didn't give it much thought before abandoning it. I'll see if I can come up with something, but maybe someone else already knows of a solution.
User avatar
Wesley
Regular Member
Posts: 137
Joined: Sun 12 Oct, 2008 1:42 am
Location: Boise, Idaho
Contact:

Re: [Java] Nodes (Circularly Linked Lists)

Post by Wesley »

Hm... Okay, I think I will resort to a doubly linked list. If that doesn't work, it's an array.
ImageImage
ImageImage
Image
polarBody
New Member
Posts: 23
Joined: Wed 02 Sep, 2009 3:01 pm
Location: Chicago, IL

Re: [Java] Nodes (Circularly Linked Lists)

Post by polarBody »

One thing to keep in mind when you're designing algorithms is that you should try to separate the algorithm from the implementation. In other words, you should first try to come up with a generic algorithm involving the manipulation of an abstract list of objects, and then decide which data structure (array, singly linked lists, doubly linked list, binary tree, etc.) is the most appropriate for your algorithm.

So in the case of the problem you're currently trying to solve, you could think of your "nodes" as little wooden blocks with distinct numbers on them, and then imagine how you could swap two blocks, one at a time, to get all possible arrangements of a set of blocks. You could imagine that you have smaller wooden blocks (representing pointer variables) that you could move around next to your "node" blocks to keep track of which blocks to swap next. This may seem childish and absurd, but if you diagram something like this on paper, you'd be surprised at the clever things you'd come up with. And once you have your wooden block algorithm, then it should be fairly straightforward to decide which data structure you can use to implement your algorithm, and often times multiple data structures will work for the same algorithm.

At any rate, I'm just cautioning you against settling for this data structure or that data structure until you have a solid, generic algorithm first. And I will try to help you with that algorithm, but not now; it's late ; )
King Harold
Calc King
Posts: 1513
Joined: Sat 05 Aug, 2006 7:22 am

Re: [Java] Nodes (Circularly Linked Lists)

Post by King Harold »

Factoradic numbers are harder to explain than to write code for, here's an example in C# (easy enough to convert to Java)
http://www.koders.com/csharp/fid3FF1BAF ... D397.aspx?
You'd have to use something bigger than an int though, probably longer than a long as well - like a BigInt. The idea remains the same.

The idea then is to first generate permutation 0, and then increment the permutation number until you're at (n-1)!
You don't even have to juggle the A yourself, it should stay the same if you only generate (n-1)! permutations (the first item is the last to be changed)
User avatar
Wesley
Regular Member
Posts: 137
Joined: Sun 12 Oct, 2008 1:42 am
Location: Boise, Idaho
Contact:

Re: [Java] Nodes (Circularly Linked Lists)

Post by Wesley »

Well, thanks guys. This has been pretty interesting.

The point of this project was to get more familiar with nodes and I wanted to actually pull off using nodes, but I'm not sure how I'd go about doing it any more. I think an array will suffice for now. Until another day...
ImageImage
ImageImage
Image
polarBody
New Member
Posts: 23
Joined: Wed 02 Sep, 2009 3:01 pm
Location: Chicago, IL

Re: [Java] Nodes (Circularly Linked Lists)

Post by polarBody »

You could still use nodes with factoradics. Just think of a linked list as a fancy array. If you want to access the ith element of an array, you would write array. If you wanted to access the ith element of a linked list, you would traverse through i nodes. Both arrays and linked lists can be used to accomplish the same tasks, albeit in different ways.

Here's a brief description of how you could solve your problem using linked lists and factoradics. Let's say you have a linked list A -> B -> C called cities, and another called perms (which will hold all permutations of cities, but one at a time). You also have an array of ints called factoradic that will hold each factoradic number.

To generate the 3rd permutation of cities, you would first call a method that fills factoradic with the 3rd factoradic number (starting from 0). This is what your data would look like so far:

cities A -> B -> C
perms (empty)
factoradic 1 0 0

You would then use the first number in factoradic as an index to extract a node from cities and place it at the end of perms, like so:

cities A -> C
perms B
factoradic 1 0 0

Now use the second number in factoradic in the same way:

cities C
perms B -> A
factoradic 1 0 0

Now the third:

cities (empty)
perms B -> A ->C
factoradic 1 0 0

Now perms holds the 3rd permutation of cities. Of course, now we've destroyed the cities list, so we can't do any other permutations. To fix this, you could add a boolean value to the node called boolean hasBeenSelected, or something like that. At the beginning of each permutation loop, you would set all of these values in the cities list to false, and then use these boolean values while you traverse the list to find the next element that hasn't been selected to place into perms. When you do find the next node to retrieve, simply set hasBeenSelected to true for that node, instead of taking the node out of the cities list.

Hope that helps.

EDIT: Oops. In the example above, you would have to copy the nodes themselves to the perms list, not just the node references. So you would also need a copy constructor for your node class. Yikes, this is getting complicated! It's a good opportunity to learn, though.

EDIT: Oops again. I forgot that the first city should be left alone. King Harold is right, though. You could find the factoradic for n-1 and the first element won't be touched.
User avatar
Wesley
Regular Member
Posts: 137
Joined: Sun 12 Oct, 2008 1:42 am
Location: Boise, Idaho
Contact:

Re: [Java] Nodes (Circularly Linked Lists)

Post by Wesley »

Wowsers!

I said before that I could determine the code needed if I could figure out the algorithm, but in this case it's quite different. Or maybe (most likely) I'm just not understanding the algorithm.

Recursion would definitely have to be used, I can see. However, actually implementing the recursion is a different story than talking about its requirements!

I see how perm extracts a new permutation. But how do we go about actually changing to a different permutation?

...
ImageImage
ImageImage
Image
polarBody
New Member
Posts: 23
Joined: Wed 02 Sep, 2009 3:01 pm
Location: Chicago, IL

Re: [Java] Nodes (Circularly Linked Lists)

Post by polarBody »

This algorithm is not recursive. You could enclose it in a for loop that iterates (n-1)! times. Each time this for loop iterates, a different permutation of cities would be produced, from which you could check the distance of the path. All of this would occur within the for loop, without the need for a recursive call.

The key to understanding this algorithm is to understand how factoradic numbers contribute to the problem. Factoradic is a positional number system, similar to base 10 or base 2 in that the position and value of the digits both contribute to the value of the number. It's possible to count from 0 to n in factoradic, just like it's possible in base 10, but the factoradic numbers would obviously look different than the base 10 numbers.

For now, it's not important how to count in factoradic, just know that it's possible. The digits of factoradic numbers have a unique property that will help us with permutations. If we have a list of three objects, then the digits of the first 3! (6) factoradic numbers will give us a way of taking the three objects from their original order and producing all 6 permutations of the three objects, 1 permutation per factoradic number. The first factoradic number will help produce the first permutation, the second factoradic number will help produce the second permutation, etc. To put it generally, the ith factoradic number will give us a way to find the ith permutation of a set of n objects, where i <= n!.

The algorithm I showed in the previous post shows how a factoradic number helps to produce the permutations. Try going back to the algorithm and see if it makes sense now. One thing to keep in mind is that the factoradic array holds all the digits of a single factoradic number, not an array of several factoradic numbers. In other words, each int in the factoradic array corresponds to a digit of a single factoradic number. The method call that I mentioned above would place the digits of the next factoradic number into the factoradic array.
Post Reply