This week's book giveaways are in the Java EE and JavaScript forums.
We're giving away four copies each of The Java EE 7 Tutorial Volume 1 or Volume 2(winners choice) and jQuery UI in Action and have the authors on-line!
See this thread and this one for details.
The moose likes Java in General and the fly likes Re-arrange these numbers! Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Re-arrange these numbers!" Watch "Re-arrange these numbers!" New topic
Author

Re-arrange these numbers!

David Duran
Ranch Hand

Joined: Feb 11, 2002
Posts: 122
I'm trying to build a program that will create a seeding arrangement similar to how tournaments are set up. The numbers here represent the seeding I start with. The second set is the order I want to achieve.
Unfortunately, I can't even think of how to do this. Obviously some algorithm is in order, hahaha. Any ideas? My brain is fried on this Friday...
8 player tournament:
1 2 3 4 5 6 7 8
1 8 4 5 3 6 2 7
16 player tournament:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 16 8 9 5 12 4 13 6 11 3 14 7 10 2 15
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
Usually for a single-elimination tournament you see something like this for round 1:

This means seed 1 plays seed 16, seed 2 plays seed 15, etc. The algorithm to arrange this should be easy enough to see - just put the first n/2 teams in different games, and the put the remaining n/2 teams into the same games, in reverse order.
If the higher-ranked seed (meaning the team with a lower seed number) wins each game, the next round looks like:

then

and finally

Of course, if a lower-ranked team beats a higher-ranked team, they take its place in subsequent rounds. I don't feel like making ASCII graphics for the complete tree, so I'll just let you imagine it.
Is this what you were thinking of, or are you looking for a different sort of tournament?
[ May 02, 2003: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, Twister
John Lee
Ranch Hand

Joined: Aug 05, 2001
Posts: 2545
Originally posted by David Duran:
I'm trying to build a program that will create a seeding arrangement similar to how tournaments are set up. The numbers here represent the seeding I start with. The second set is the order I want to achieve.
Unfortunately, I can't even think of how to do this. Obviously some algorithm is in order, hahaha. Any ideas? My brain is fried on this Friday...
8 player tournament:
1 2 3 4 5 6 7 8
1 8 4 5 3 6 2 7
16 player tournament:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 16 8 9 5 12 4 13 6 11 3 14 7 10 2 15

use recursion algorithm. break 1~8 to 1,8,4,5 and 3,6,2,7.
then break 1,8,4,5 to 1,8 and 4,5
when just 2 numbers left, write them out (lower seed first).
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
Don, how many times do you want us to read each of your posts? You keep reposting the same thing & deleting the old one so it shows up as "new". If you must increase your post count, can't you just continue flooding things like Word Association and Certification Results, rather than polluting "real" topics with this silliness? Some of us look for new posts in order to find posts that are, well, new.
David Duran
Ranch Hand

Joined: Feb 11, 2002
Posts: 122
Well, I'm dusting this off the shelf.
Jim, I understand your description, but I'm not sure if it quite solves my dilemma.
Here's what I do right now:
1. I grab an unsorted list of all the players in the tournament. It's an ArrayList of Player objects which contains fields for name and rank.
Original List: Name - Rank
John - 5
Bill - 2
Andy - 1
Ron - 8
Jen - 6
Alex - 4
Ron - 3
Don - 7
2. I sort them by their Rank in the order of highest -> lowest. Notice that in this example, the rank corresponds to their seeding position in the tournament, ie. Andy is the top seed
Andy - 1
Bill - 2
Ron - 3
Alex - 4
John - 5
Jen - 6
Don - 7
Ron - 8
3. *Here's where my problem comes in - Now I want to re-arrange the players into a new list so that it mirrors what the first round looks like. The number in the [] represents the index of the list or array which will hold the Player objects.
[0] Andy - 1
[1] Ron - 8
[2] Alex - 4
[3] John - 5
[4] Ron - 3
[5] Jen - 6
[6] Bill - 2
[7] Don - 7
----------------
In step 2, I can easily pair them up as you described just by looping through the list and maintaining two counters, one that starts at the beginning and one at the end. This looping gets me "Who plays Who"
What I'm really looking for is the placement in the list of the "Who plays Who" pairings. Did I make it clear?
If I can achieve Step 3, then I can just loop through the list and arrainge it into the first round of the bracket.
Maulin Vasavada
Ranch Hand

Joined: Nov 04, 2001
Posts: 1871
hi David,
i've a code that generates the ranks in the sequence they 'll appear in the first round of the selection...
i applied some logic and came up with this code. i am starting my index from 1 (so the first element in the array is -1) for simplicity and kept the array type as double but u can always modify the code to see if it has correct datatypes and all...

Here , number of players are assumed to be pow(2,N). so,
1. if we want 2 players we put N =1,
2. if we want 4 players we put N=2,
3. if we want 8 players we put N=3,
etc....
is this what u were looking for??
regards
maulin
Hung Tang
Ranch Hand

Joined: Feb 14, 2002
Posts: 148
Why not use a queue that supports dequeue from rear operation.
suppose you have a sorted queue with 1 2 3 4 5 6 7 8 and the front item is 8 and the rear item is 1.
In pseudo code, we could have something like this:

and to do it recursively...

This would not give you the order you want say 1,8,4,5,... but instead 1,8,2,7,... but all that requires is a change in your sorting process to have something like 1 4 3 2 7 6 5 8 before you pass your queue into the rearrangement method.
That's not too difficult to do.
good luck.
[ June 12, 2003: Message edited by: Hung Tang ]
David Duran
Ranch Hand

Joined: Feb 11, 2002
Posts: 122
Maulin, THANK YOU
That's exactly what I'm looking for. I was looking around the Internet yesterday for tournament seeding/ordering algorithms and came across this site which uses Javascript to come up with the correct ordering system (the the last half of the bracket needs to be reversed for display purposes).
http://www.crowsdarts.com/brackets/playoff-chart.html
I was about to go through his Javascript and convert the necessary parts to Java...
WHEW! Thanks a million my friend.
[ June 12, 2003: Message edited by: David Duran ]
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Re-arrange these numbers!