(bi)annual WebDip Gunboat tournament?
(bi)annual WebDip Gunboat tournament?
Seems like the annual WebDip gunboat tourney is past due for another run!?
I think last one was 2015, even though tourney page shows 2010.
I think last one was 2015, even though tourney page shows 2010.
- ghug
- Bronze Donator
- Posts: 18377
- Joined: Mon Mar 20, 2017 3:51 pm
- Location: Seattle
- Karma: 11693
- Contact:
Re: (bi)annual WebDip Gunboat tournament?
I'm thinking about starting one up in a month or two. Feel free to use this space to discuss format and such. I'm not sure what the gunboat community is into these days.
Re: (bi)annual WebDip Gunboat tournament?
Awesome, ghug!
I think the rules on the tourney page from 2010 (http://tournaments.webdiplomacy.net/gunboat-tournament) are a good place to start, with a few suggested changes:
Previously:
"Within each 7 player group, 7 games will be played, with each player getting to play each power once.
Suggested changes to this format:
That makes it far to easy to deduce which player is playing which power after the early games finish. Would change that to randomly assigning countries, with no player playing the same country more than twice!
Also, don't really need 7 games per round. Could do 4 or 5 games per round. But even with just 4-5 games per round, keep the random assignment with no more that two games as one country, because otherwise it's still too easy to deduce that one player is not Turkey or Italy for example, after some games finish.
Previously:
"The first round will be a group stage with a hard cap of 42 players.
Suggested changes to this format:
Could adapt total entrants and games per round based on interest. For example, 5 groups of 7, and then have 2 wild-cards with next highest point totals.
Also, I would recommend changing the tie-breakers:
Previously
Final round will prioritize solos.
- 1 point for a solo victory
- No points for draws, survives, or defeats
Tiebreakers in the group stage will be as follows:
1. Number of solos
2. Number of draws
3. Number of survives
4. Total number of centers after completion of 7 games in group stage.
Tiebreakers in the finals:
1. Total number of centers after completion of final round.
2. Number of draws
3. Number of survives
Suggested changes:
Final round will prioritize solos. (This is an iteresting twist that could stay)
- 1 point for a solo victory
- No points for draws, survives, or defeats
Tiebreakers in the group stage will be as follows:
1. Number of solos
2. Number of 2-WAY draws
3. Number of 3-WAY draws
4. Number of 4-WAY draws
5. Number of 5-WAY draws
6. Number of 6-WAY draws (with such a low priority on this, hopefully lame 6-way draws won't happen)
(Survives should never count for anything!)
4. Total number of centers after completion of 7 games in group stage.
Tiebreakers in the finals:
Same changes as suggested new tiebreakers for group stage!
I think the rules on the tourney page from 2010 (http://tournaments.webdiplomacy.net/gunboat-tournament) are a good place to start, with a few suggested changes:
Previously:
"Within each 7 player group, 7 games will be played, with each player getting to play each power once.
Suggested changes to this format:
That makes it far to easy to deduce which player is playing which power after the early games finish. Would change that to randomly assigning countries, with no player playing the same country more than twice!
Also, don't really need 7 games per round. Could do 4 or 5 games per round. But even with just 4-5 games per round, keep the random assignment with no more that two games as one country, because otherwise it's still too easy to deduce that one player is not Turkey or Italy for example, after some games finish.
Previously:
"The first round will be a group stage with a hard cap of 42 players.
Suggested changes to this format:
Could adapt total entrants and games per round based on interest. For example, 5 groups of 7, and then have 2 wild-cards with next highest point totals.
Also, I would recommend changing the tie-breakers:
Previously
Final round will prioritize solos.
- 1 point for a solo victory
- No points for draws, survives, or defeats
Tiebreakers in the group stage will be as follows:
1. Number of solos
2. Number of draws
3. Number of survives
4. Total number of centers after completion of 7 games in group stage.
Tiebreakers in the finals:
1. Total number of centers after completion of final round.
2. Number of draws
3. Number of survives
Suggested changes:
Final round will prioritize solos. (This is an iteresting twist that could stay)
- 1 point for a solo victory
- No points for draws, survives, or defeats
Tiebreakers in the group stage will be as follows:
1. Number of solos
2. Number of 2-WAY draws
3. Number of 3-WAY draws
4. Number of 4-WAY draws
5. Number of 5-WAY draws
6. Number of 6-WAY draws (with such a low priority on this, hopefully lame 6-way draws won't happen)
(Survives should never count for anything!)
4. Total number of centers after completion of 7 games in group stage.
Tiebreakers in the finals:
Same changes as suggested new tiebreakers for group stage!
-
- Posts: 88
- Joined: Tue Jan 02, 2018 5:20 pm
- Location: North Dakota
- Contact:
Re: (bi)annual WebDip Gunboat tournament?
I definitely like those rules changes chluke, except for one modification.
I think the winner should be:
1. Number of solos
2. Lowest sum of draw sizes
For instance, we played four games and I was defeated once, drew with 3, drew with 3, and drew with 4. My sum of draw size is 3+3+4=10. This still prioritizes smaller draw sizes but eliminates the problem I foresee as demonstrated below.
First games all end in a three or more size draw. So, a player in the last game who was defeated in the previous games knows they have to win or get a better draw than three. If they draw three there will probably be another player who drawed a different time. So this player purposefully tries to eliminate the third to last player while risking the leader soloing for the purpose of getting a two-way draw. I don't think this would be fair to other players who would have otherwise had a better overall series of games.
I think the winner should be:
1. Number of solos
2. Lowest sum of draw sizes
For instance, we played four games and I was defeated once, drew with 3, drew with 3, and drew with 4. My sum of draw size is 3+3+4=10. This still prioritizes smaller draw sizes but eliminates the problem I foresee as demonstrated below.
First games all end in a three or more size draw. So, a player in the last game who was defeated in the previous games knows they have to win or get a better draw than three. If they draw three there will probably be another player who drawed a different time. So this player purposefully tries to eliminate the third to last player while risking the leader soloing for the purpose of getting a two-way draw. I don't think this would be fair to other players who would have otherwise had a better overall series of games.
-
- Posts: 88
- Joined: Tue Jan 02, 2018 5:20 pm
- Location: North Dakota
- Contact:
Re: (bi)annual WebDip Gunboat tournament?
1. Number of solos
2. Lowest sum of draw sizes
3. Survives
4. SC count
5. Bribes for the mods
2. Lowest sum of draw sizes
3. Survives
4. SC count
5. Bribes for the mods
Re: (bi)annual WebDip Gunboat tournament?
solo=6/1
2w=5/2
3w=4/3
4w=3/4
5w=2/5
6w=1/6
7w=0/7
(6;2.5;1.33;0.75;0.4;0.16;0)
Alternately,
solo=6/1+1=7.00
2w=5/2+1=3.50
3w=4/3+1=2.33
4w=3/4+1=1.75
5w=2/5+1=1.40
6w=1/6+1=1.16
7w=0/7+1=1.00
The first option priorizes solos, and it is very dificult a player with less solos than another to end up higher ranked.
Also note that the first round doesn't need to be made in groups of 7, any number of players is admitted, 7 games (A/E/F/G/I/R/T).
The top seven play seven more games, same points system.
2w=5/2
3w=4/3
4w=3/4
5w=2/5
6w=1/6
7w=0/7
(6;2.5;1.33;0.75;0.4;0.16;0)
Alternately,
solo=6/1+1=7.00
2w=5/2+1=3.50
3w=4/3+1=2.33
4w=3/4+1=1.75
5w=2/5+1=1.40
6w=1/6+1=1.16
7w=0/7+1=1.00
The first option priorizes solos, and it is very dificult a player with less solos than another to end up higher ranked.
Also note that the first round doesn't need to be made in groups of 7, any number of players is admitted, 7 games (A/E/F/G/I/R/T).
The top seven play seven more games, same points system.
-
- Posts: 88
- Joined: Tue Jan 02, 2018 5:20 pm
- Location: North Dakota
- Contact:
Re: (bi)annual WebDip Gunboat tournament?
Looks similar to an abstruse tax bracket. However, it seems like a reliable way to sort out ties.
- ghug
- Bronze Donator
- Posts: 18377
- Joined: Mon Mar 20, 2017 3:51 pm
- Location: Seattle
- Karma: 11693
- Contact:
Re: (bi)annual WebDip Gunboat tournament?
It's not trivial to admit any number of players and have them all play each country once, just FYI.
-
- Posts: 77
- Joined: Sun Dec 31, 2017 2:19 am
- Karma: 5
- Contact:
Re: (bi)annual WebDip Gunboat tournament?
Can solos with Englad count as more?
Kidding, but 7 games per round seems like quite a few games going on at once, or are they spaced out one after the other?
Kidding, but 7 games per round seems like quite a few games going on at once, or are they spaced out one after the other?
-
- Posts: 6908
- Joined: Fri Oct 20, 2017 2:11 pm
- Location: possibly Britain
- Karma: 9624
- Contact:
Re: (bi)annual WebDip Gunboat tournament?
I would like the system where we all get to play each country once, except if you can design a system where I get to play France, Austria, and Italy twice, and Germany once. Then I would like that system more.
I have no real rules related feedback except to weight for solos.
I have no real rules related feedback except to weight for solos.
Re: (bi)annual WebDip Gunboat tournament?
@Ghug, it can be handmade, and I believe it is easier with at least 43 players (6*7+1, you play 7 boards against 6 different players):
Once you know the number of confirmed players, fill the square matrix first (number of players x number of games; np=ng), with AEFGIRT values, each row and each column accepting only one of each seven letter values, and then randomly assign a player number to each player.
Or, well, just need a little help from one of our mathematicians, we have a few good ones over here (hint hint, hey ya).
W.r.t. points system, note the first option should be sum zero (a player contribute with one point, thus an elimination is worth -1), and in the 2nd one each game grants a total of 7 points. As previously noted, the sum-zero priorizes solos, so it is preferable.
Once you know the number of confirmed players, fill the square matrix first (number of players x number of games; np=ng), with AEFGIRT values, each row and each column accepting only one of each seven letter values, and then randomly assign a player number to each player.
Or, well, just need a little help from one of our mathematicians, we have a few good ones over here (hint hint, hey ya).
W.r.t. points system, note the first option should be sum zero (a player contribute with one point, thus an elimination is worth -1), and in the 2nd one each game grants a total of 7 points. As previously noted, the sum-zero priorizes solos, so it is preferable.
-
- Gold Donator
- Posts: 264
- Joined: Tue Jan 02, 2018 2:51 pm
- Location: Texas
- Karma: 607
- Contact:
Re: (bi)annual WebDip Gunboat tournament?
I strongly urge a scoring system that values draws, such as the one suggested by CCR.
- I think that a scoring system that treats all outcomes other than "solo win" as equal encourages a style of play that one rarely sees in high-level gunboat games.
- I think it is reasonable to say that a player who got eliminated twice and made one solo win is as good a gunboat player as the player who played three games to a 3-way draw.
- I also think that devaluing the draw further tilts an already unbalanced game.
-
- Posts: 88
- Joined: Tue Jan 02, 2018 5:20 pm
- Location: North Dakota
- Contact:
Re: (bi)annual WebDip Gunboat tournament?
CCR wrote: ↑Mon Feb 05, 2018 10:05 am@Ghug, it can be handmade, and I believe it is easier with at least 43 players (6*7+1, you play 7 boards against 6 different players):
Once you know the number of confirmed players, fill the square matrix first (number of players x number of games; np=ng), with AEFGIRT values, each row and each column accepting only one of each seven letter values, and then randomly assign a player number to each player.
Or, well, just need a little help from one of our mathematicians, we have a few good ones over here (hint hint, hey ya).
W.r.t. points system, note the first option should be sum zero (a player contribute with one point, thus an elimination is worth -1), and in the 2nd one each game grants a total of 7 points. As previously noted, the sum-zero priorizes solos, so it is preferable.
Or this java program...
webdiplomacy is welcome to use this for any tournament, ghug.
/**
*
* @author jared
*/
import java.util.Arrays;
import java.util.Collections;
public class DiplomacyTournament {
private String[] listOfPlayers;
DiplomacyTournament(String[] listOfPlayers)
{
this.listOfPlayers = listOfPlayers;
}
public String[] countryArray()
{
String[] returnStringArray = new String[listOfPlayers.length];
for(int i = 0; i < listOfPlayers.length; i++)
{
returnStringArray = listOfPlayers;
}
return returnStringArray;
}
public static void main(String[] args) {
//43 is number of players
String[] playerList = new String[43];
//where you would initialize playerList
//for example purposes only
for(int i = 0; i < playerList.length; i++)
{
playerList = "Player " + (i + 1);
}
//for example purposes only
DiplomacyTournament dt = new DiplomacyTournament(playerList);
String[] austria = dt.countryArray();
String[] russia = dt.countryArray();
String[] france = dt.countryArray();
String[] turkey = dt.countryArray();
String[] germany = dt.countryArray();
String[] italy = dt.countryArray();
String[] england = dt.countryArray();
boolean sentinel = true;
while(sentinel)
{
sentinel = false;
Collections.shuffle(Arrays.asList(russia));
for(int i = 0; i < playerList.length; i++)
{
if(austria.equals(russia))
{
sentinel = true;
break;
}
}
}
sentinel = true;
while(sentinel)
{
sentinel = false;
Collections.shuffle(Arrays.asList(france));
for(int i = 0; i < playerList.length; i++)
{
if(austria.equals(france) || russia.equals(france))
{
sentinel = true;
break;
}
}
}
sentinel = true;
while(sentinel)
{
sentinel = false;
Collections.shuffle(Arrays.asList(turkey));
for(int i = 0; i < playerList.length; i++)
{
if(austria.equals(turkey[i]) || russia[i].equals(turkey[i]) || france[i].equals(turkey[i]))
{
sentinel = true;
break;
}
}
}
sentinel = true;
while(sentinel)
{
sentinel = false;
Collections.shuffle(Arrays.asList(germany));
for(int i = 0; i < playerList.length; i++)
{
if(austria[i].equals(germany[i]) || russia[i].equals(germany[i]) || france[i].equals(germany[i]) || turkey[i].equals(germany[i]) )
{
sentinel = true;
break;
}
}
}
sentinel = true;
while(sentinel)
{
sentinel = false;
Collections.shuffle(Arrays.asList(italy));
for(int i = 0; i < playerList.length; i++)
{
if(austria[i].equals(italy[i]) || russia[i].equals(italy[i]) || france[i].equals(italy[i]) || turkey[i].equals(italy[i]) || germany[i].equals(italy[i]) )
{
sentinel = true;
break;
}
}
}
sentinel = true;
while(sentinel)
{
sentinel = false;
Collections.shuffle(Arrays.asList(england));
for(int i = 0; i < playerList.length; i++)
{
if(austria[i].equals(england[i]) || russia[i].equals(england[i]) || france[i].equals(england[i]) || turkey[i].equals(england[i]) || germany[i].equals(england[i]) || italy[i].equals(england[i]) )
{
sentinel = true;
break;
}
}
}
for(int i = 0; i < playerList.length; i++)
{
System.out.println("Game " + (i + 1) );
System.out.println("\tAustria: " + austria[i]);
System.out.println("\tRussia: " + russia[i]);
System.out.println("\tFrance: " + france[i]);
System.out.println("\tTurkey: " + turkey[i]);
System.out.println("\tGermany: " + germany[i]);
System.out.println("\tItaly: " + italy[i]);
System.out.println("\tEngland: " + england[i]);
}
}
}
-
- Posts: 88
- Joined: Tue Jan 02, 2018 5:20 pm
- Location: North Dakota
- Contact:
Re: (bi)annual WebDip Gunboat tournament?
Example output for 23 players:
Game 1
Austria: Player 1
Russia: Player 17
France: Player 11
Turkey: Player 5
Germany: Player 12
Italy: Player 14
England: Player 21
Game 2
Austria: Player 2
Russia: Player 16
France: Player 6
Turkey: Player 7
Germany: Player 19
Italy: Player 23
England: Player 5
Game 3
Austria: Player 3
Russia: Player 21
France: Player 8
Turkey: Player 1
Germany: Player 14
Italy: Player 20
England: Player 9
Game 4
Austria: Player 4
Russia: Player 10
France: Player 1
Turkey: Player 8
Germany: Player 3
Italy: Player 12
England: Player 11
Game 5
Austria: Player 5
Russia: Player 2
France: Player 9
Turkey: Player 21
Germany: Player 4
Italy: Player 11
England: Player 17
Game 6
Austria: Player 6
Russia: Player 1
France: Player 7
Turkey: Player 18
Germany: Player 9
Italy: Player 17
England: Player 23
Game 7
Austria: Player 7
Russia: Player 8
France: Player 19
Turkey: Player 4
Germany: Player 23
Italy: Player 10
England: Player 20
Game 8
Austria: Player 8
Russia: Player 19
France: Player 2
Turkey: Player 12
Germany: Player 10
Italy: Player 22
England: Player 7
Game 9
Austria: Player 9
Russia: Player 18
France: Player 14
Turkey: Player 6
Germany: Player 1
Italy: Player 21
England: Player 22
Game 10
Austria: Player 10
Russia: Player 23
France: Player 5
Turkey: Player 22
Germany: Player 16
Italy: Player 8
England: Player 13
Game 11
Austria: Player 11
Russia: Player 14
France: Player 17
Turkey: Player 15
Germany: Player 6
Italy: Player 7
England: Player 10
Game 12
Austria: Player 12
Russia: Player 9
France: Player 4
Turkey: Player 16
Germany: Player 20
Italy: Player 5
England: Player 15
Game 13
Austria: Player 13
Russia: Player 7
France: Player 22
Turkey: Player 9
Germany: Player 18
Italy: Player 6
England: Player 19
Game 14
Austria: Player 14
Russia: Player 20
France: Player 3
Turkey: Player 13
Germany: Player 21
Italy: Player 2
England: Player 1
Game 15
Austria: Player 15
Russia: Player 22
France: Player 20
Turkey: Player 14
Germany: Player 11
Italy: Player 3
England: Player 6
Game 16
Austria: Player 16
Russia: Player 15
France: Player 13
Turkey: Player 2
Germany: Player 17
Italy: Player 9
England: Player 18
Game 17
Austria: Player 17
Russia: Player 4
France: Player 23
Turkey: Player 11
Germany: Player 2
Italy: Player 18
England: Player 3
Game 18
Austria: Player 18
Russia: Player 6
France: Player 15
Turkey: Player 17
Germany: Player 8
Italy: Player 19
England: Player 12
Game 19
Austria: Player 19
Russia: Player 12
France: Player 21
Turkey: Player 10
Germany: Player 13
Italy: Player 1
England: Player 16
Game 20
Austria: Player 20
Russia: Player 11
France: Player 10
Turkey: Player 3
Germany: Player 22
Italy: Player 16
England: Player 8
Game 21
Austria: Player 21
Russia: Player 5
France: Player 16
Turkey: Player 20
Germany: Player 15
Italy: Player 13
England: Player 14
Game 22
Austria: Player 22
Russia: Player 13
France: Player 18
Turkey: Player 23
Germany: Player 5
Italy: Player 4
England: Player 2
Game 23
Austria: Player 23
Russia: Player 3
France: Player 12
Turkey: Player 19
Germany: Player 7
Italy: Player 15
England: Player 4
Game 1
Austria: Player 1
Russia: Player 17
France: Player 11
Turkey: Player 5
Germany: Player 12
Italy: Player 14
England: Player 21
Game 2
Austria: Player 2
Russia: Player 16
France: Player 6
Turkey: Player 7
Germany: Player 19
Italy: Player 23
England: Player 5
Game 3
Austria: Player 3
Russia: Player 21
France: Player 8
Turkey: Player 1
Germany: Player 14
Italy: Player 20
England: Player 9
Game 4
Austria: Player 4
Russia: Player 10
France: Player 1
Turkey: Player 8
Germany: Player 3
Italy: Player 12
England: Player 11
Game 5
Austria: Player 5
Russia: Player 2
France: Player 9
Turkey: Player 21
Germany: Player 4
Italy: Player 11
England: Player 17
Game 6
Austria: Player 6
Russia: Player 1
France: Player 7
Turkey: Player 18
Germany: Player 9
Italy: Player 17
England: Player 23
Game 7
Austria: Player 7
Russia: Player 8
France: Player 19
Turkey: Player 4
Germany: Player 23
Italy: Player 10
England: Player 20
Game 8
Austria: Player 8
Russia: Player 19
France: Player 2
Turkey: Player 12
Germany: Player 10
Italy: Player 22
England: Player 7
Game 9
Austria: Player 9
Russia: Player 18
France: Player 14
Turkey: Player 6
Germany: Player 1
Italy: Player 21
England: Player 22
Game 10
Austria: Player 10
Russia: Player 23
France: Player 5
Turkey: Player 22
Germany: Player 16
Italy: Player 8
England: Player 13
Game 11
Austria: Player 11
Russia: Player 14
France: Player 17
Turkey: Player 15
Germany: Player 6
Italy: Player 7
England: Player 10
Game 12
Austria: Player 12
Russia: Player 9
France: Player 4
Turkey: Player 16
Germany: Player 20
Italy: Player 5
England: Player 15
Game 13
Austria: Player 13
Russia: Player 7
France: Player 22
Turkey: Player 9
Germany: Player 18
Italy: Player 6
England: Player 19
Game 14
Austria: Player 14
Russia: Player 20
France: Player 3
Turkey: Player 13
Germany: Player 21
Italy: Player 2
England: Player 1
Game 15
Austria: Player 15
Russia: Player 22
France: Player 20
Turkey: Player 14
Germany: Player 11
Italy: Player 3
England: Player 6
Game 16
Austria: Player 16
Russia: Player 15
France: Player 13
Turkey: Player 2
Germany: Player 17
Italy: Player 9
England: Player 18
Game 17
Austria: Player 17
Russia: Player 4
France: Player 23
Turkey: Player 11
Germany: Player 2
Italy: Player 18
England: Player 3
Game 18
Austria: Player 18
Russia: Player 6
France: Player 15
Turkey: Player 17
Germany: Player 8
Italy: Player 19
England: Player 12
Game 19
Austria: Player 19
Russia: Player 12
France: Player 21
Turkey: Player 10
Germany: Player 13
Italy: Player 1
England: Player 16
Game 20
Austria: Player 20
Russia: Player 11
France: Player 10
Turkey: Player 3
Germany: Player 22
Italy: Player 16
England: Player 8
Game 21
Austria: Player 21
Russia: Player 5
France: Player 16
Turkey: Player 20
Germany: Player 15
Italy: Player 13
England: Player 14
Game 22
Austria: Player 22
Russia: Player 13
France: Player 18
Turkey: Player 23
Germany: Player 5
Italy: Player 4
England: Player 2
Game 23
Austria: Player 23
Russia: Player 3
France: Player 12
Turkey: Player 19
Germany: Player 7
Italy: Player 15
England: Player 4
- ghug
- Bronze Donator
- Posts: 18377
- Joined: Mon Mar 20, 2017 3:51 pm
- Location: Seattle
- Karma: 11693
- Contact:
Re: (bi)annual WebDip Gunboat tournament?
Thanks, ZaZ! Forgive me if I'm misinterpreting, but are you shuffling each list until it has no collisions? Isn't that going to be really slow with high numbers of players?
Maybe it's better to do it more as a tree-based search like one would solve a sudoku. I can take a look at it when I get some free time.
Maybe it's better to do it more as a tree-based search like one would solve a sudoku. I can take a look at it when I get some free time.
-
- Posts: 88
- Joined: Tue Jan 02, 2018 5:20 pm
- Location: North Dakota
- Contact:
Re: (bi)annual WebDip Gunboat tournament?
Yes, that is exactly what it is doing ghug. Someone correct me if I'm wrong, but there should always be a solution.
Runtime for a 1000 players was 1 second. 10000 was 8 seconds. You only start to see real issues when you get to the millions.
I'm not familiar with tree-based searches. I'm in school and I'm taking Data Structures and Algorithms right now, so that'll be covered in a few months. :D
Runtime for a 1000 players was 1 second. 10000 was 8 seconds. You only start to see real issues when you get to the millions.
I'm not familiar with tree-based searches. I'm in school and I'm taking Data Structures and Algorithms right now, so that'll be covered in a few months. :D
- ghug
- Bronze Donator
- Posts: 18377
- Joined: Mon Mar 20, 2017 3:51 pm
- Location: Seattle
- Karma: 11693
- Contact:
Re: (bi)annual WebDip Gunboat tournament?
I think it will always work, though the worst case is factorial time. If it's running that fast in practical usage though, I think we're fine.
Can you shoot that to the mods in an email so that they have it on record with nice indentation and such?
Can you shoot that to the mods in an email so that they have it on record with nice indentation and such?
-
- Posts: 88
- Joined: Tue Jan 02, 2018 5:20 pm
- Location: North Dakota
- Contact:
Re: (bi)annual WebDip Gunboat tournament?
I thought you were on the mod team, actually. I sent them an email.
I'm wondering how you get factorial time. Is it factorial time because the shuffle method goes through a sort of loop and there are n-factorial orderings an n-sized array? I don't know the source code, but I'm guessing it's similar to a Fisher-Yates algorithm which runs random number swaps through a for-loop using random numbers. If that's the case, then it is worst-case infinite because the shuffling could loop through the random number generation without reaching every ordering, thus possibly never reaching a valid ordering. This is...purely theoretical of course.
The reason it works in practice is that as n gets larger the probability of having no collisions after a shuffle increases. There may be more pigeons, but there are more holes for the pigeons. I might have to dig into the math here. This algorithm doesn't make it easy to calculate probability. A simple test of my code showed 8 is actually the worst for number of iterations of the last shuffle.
I'm wondering how you get factorial time. Is it factorial time because the shuffle method goes through a sort of loop and there are n-factorial orderings an n-sized array? I don't know the source code, but I'm guessing it's similar to a Fisher-Yates algorithm which runs random number swaps through a for-loop using random numbers. If that's the case, then it is worst-case infinite because the shuffling could loop through the random number generation without reaching every ordering, thus possibly never reaching a valid ordering. This is...purely theoretical of course.
The reason it works in practice is that as n gets larger the probability of having no collisions after a shuffle increases. There may be more pigeons, but there are more holes for the pigeons. I might have to dig into the math here. This algorithm doesn't make it easy to calculate probability. A simple test of my code showed 8 is actually the worst for number of iterations of the last shuffle.
- ghug
- Bronze Donator
- Posts: 18377
- Joined: Mon Mar 20, 2017 3:51 pm
- Location: Seattle
- Karma: 11693
- Contact:
Re: (bi)annual WebDip Gunboat tournament?
That's a good point, bogosort only actually has a bounded worst case if you cheat and make it deterministic.
We benefit from our table only expanding in one dimension here, really. It's not as likely to get collisions when there are only seven countries.
We benefit from our table only expanding in one dimension here, really. It's not as likely to get collisions when there are only seven countries.
Who is online
Users browsing this forum: No registered users and 100 guests