[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:

Re: [Java] Nodes (Circularly Linked Lists)

Post by Wesley »

This is getting really exciting. I think I'm starting to understand factoradics more. But how would I generate the next factoradic?

Once I have the pointers, I think I might be able to move my nodes into a new permutation list.

Oh, and I don't have to have the first node static. If this works for nodes, then I can move them all around.

You say ALL of this can be done in a single for loop? How so? Wouldn't it be better to have methods that you would call for the next factoradic and factorial?
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 »

I'm glad to see that your starting to see the light!

About the for loop, I meant that the entire algorithm could be enclosed in one for loop. But that doesn't exclude the possibility of having other for loops within the body of the main for loop. And yes, you would probably want to have a method that calculates the next factoradic number, but remember that you could call this method from within the body of the main for loop. Here's some very generic pseudocode that may clarify things:

Code: Select all

for i from 1 to (n-1)!
     set perms list to null
     get next factoradic number in factoradic array
     for j from 1 to factoradic.length
          extract the factoradic[j]th node from cities
          add this node to end of perms
     end for j
     calculate the path using perms
end for i
As for how to generate the factoradic numbers, you should do some research on factoradic and see if you can come up with something on your own. If you have any experience with binary or hex, then factoradic shouldn't be too difficult for you. Also, for more help with factoradic, you could look at the C# code that King Harold suggested in a previous post (don't worry: C# is a lot like Java).
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 going to try and run through the possible permutations of 3 cities using factoradic. So, don't we take from the original set of elements every time we compute the new factoradic permutation?

We begin with:

Permutation 1:
0 0 0
A B C

Permutation 2:
0 1 0
A C B

Permutation 3:
1 0 0
B A C

Permutation 4:
1 1 0
B C A

Permutation 5:
2 0 0
C A B

Permutation 6:
2 1 0
C B A


So, if we had A, B, C, D, E, F; the following would be true?

Permutation 3*5! + 4*4! + 1*3! + 0*2! + 1*1! + 0*0! = 463:
3 4 1 0 1 0
D F B A E C


Am I going on the correct path? I'm getting started on my factoradic method. I think I will simply convert from the decimal position (after calculating how many factoradic permutations are possible) to the factoradic position. I don't really like looking at other code. Getting the idea is the important part. If one can't write their own code, why be a computer programmer?
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 »

Yep, you got it. Wow, you learn fast; I'm impressed!
I don't really like looking at other code. Getting the idea is the important part. If one can't write their own code, why be a computer programmer?
I partially agree with you here. Certainly a programmer should be able to solve any problem that they take on, but sometimes the best solution is to use somebody else's. For example, most likely you have used System.out.print(blah) before, but you certainly didn't write this method, nor are you required to understand how it works. It's prewritten code like this that makes a programmer's life much easier, allowing the programmer to focus on other tasks specific to the given problem.

Having said that, I also understand the urge to code everything yourself just for the challenge and the thrill of problem solving. You and I are alike in that respect ; )
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 »

Yeah, I should've rephrased what I said about seeing other people's code. What I was referring to were the people (usually students) who go snooping around for code to pass along as their "original" homework.

I think I almost have it. I only have to debug my code now. But it being 3:00am, I think I better go to bed, since I have a 6 mile tempo run in the morning for Cross-Country practice :shockedsad:...
ImageImage
ImageImage
Image
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... I'm not quite sure where I've gone wrong. Can anyone else spot it?

Code: Select all

		// c is the decimal permutation
		// count is the number of elements
		// factoradic() stores the correct permutation in factArray
		// all of the nodes are loaded in the order they were in the file and are linked to first
		for (int i=0; i <= c; i++) {
			copy = first;
			perms = null;
			factoradic(count, i);
			// find the best permutation
			for (int j=0; j < factArray.length; j++) {
				tmp = copy;
				for (int k=0; k < factArray[j]; k++) {
					tmp2 = tmp;
					tmp = tmp.next;
					tmp3 = tmp.next;
				}
				tmp2.next = tmp3;
				// load nodes into perms, one at a time
				current = tmp;
				if (perms == null) {
					perms = current;
					current.next = perms;
				} else {
					tmp4 = perms.next;
					while (tmp4.next != perms) {
						tmp4 = tmp4.next;
					}
					tmp4.next = current;
					current.next = perms;
				}
			}
			// check distance of perms; if it is better than bestDelta, we store perms into bestTour
			if (distance2() < bestDelta) {
				bestTour = perms;
				bestDelta = distance2();
			}
		}
ImageImage
ImageImage
Image
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 »

I'm not sure how many errors there are with that code, but I just noticed one that I don't know how to fix. When I invoke the following code:

Code: Select all

copy = first;
I'm not actually creating a separate node list, but both first and copy are pointing to the same node list.

Any ideas on how to make a direct copy of a node list rather than pointing to the same reference?
ImageImage
ImageImage
Image
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 got everything to work, EXCEPT the copying of nodes part. I just want to make separate node lists rather than having all of the nodes reference the same list.

I don't know how to do it!!! It drives me nuts!

I will email one of my professors and see if he has any insight.
ImageImage
ImageImage
Image
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 »

YES!!!

I have accomplished the task! That sure took a long time! Debugging is the worst.

If anyone would like to try out the program, I will post it for a minimal time somewhere. Or I could just post up the .class files and leave out the code. But if anyone is interested, I will be happy to let you look at the code somehow.

I can't allow my colleague students to access the code.
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 »

Good job, Wesley. I wouldn't mind taking a look at your code. How about I pm you my email address?
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 »

No problem.

My code is quite inefficient and is kinda messy, but it sufficeth me to have the problem figured out!

When I mentioned in my email to my professor how I had implemented my brute force algorithm, he was asking me to send him my solution. I think "factoradics" sparked his interest. He was very excited.

I didn't; however, implement the brute force algorithm the way I intended. I didn't want to use arrays whatsoever, but I don't think it's possible. Of course, it would be possible if you could have separate node lists rather than all the nodes referencing from the same list.

Go ahead and PM me your email address.

EDIT: Oh, and polarBody, thanks for all the help! I don't think any of this would be possible without you. And King Harold, don't think I forgot about you. I love this forum!
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 »

Glad to help. Actually, this has been a learning experience for me, as well. I've never worked with the Traveling Salesman Problem before, and before a couple days ago, I had never even heard of factoradic numbers (good call, King Harold). This has all been really interesting.
King Harold
Calc King
Posts: 1513
Joined: Sat 05 Aug, 2006 7:22 am

Re: [Java] Nodes (Circularly Linked Lists)

Post by King Harold »

Thanks guys, I'm glad all that time I spend reading wiki pages wasn't completely wasted lol
Post Reply