Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# Re-arrange these numbers!

David Duran
Ranch Hand
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
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 ]

John Lee
Ranch Hand
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
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
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
Posts: 1873
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
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
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 ]