Hi, I just started working with java and I have probably an easy problem to solve.
I've made an array and I want to fill it with random integers from 0-39. Each integer can be used only once.
Here's the code:
for (i=0; i<40; i++)
{
kup[i] = (int)(Math.random() * 40);
for (j=0; j<40; j++)
{
if (j != i)
{
while (kup[i] == kup[j])
{
kup[i] = (int)(Math.random() * 40);
}
}
}
}
Hi, I have this (efficient) code to make a random permutation:
public static void permute(int[] a) {
for (int i = 0; i < a.length; i++) {
// Pick a random index in i ... a.length-1
int k = i + (int) (Math.random() * (a.length - i));
// Swap.
int temp = a[i];
a[i] = a[k];
a[k] = temp;
}
}
Call it like this:
kupt[i] = new int[40];
for (i=0; i<40; i++) {
kup[i] = i;
}
permute(kup);
For each position i in your array it randomly chooses one of the remaining elements and swaps it with the one at position i.
This one is guaranteed to be a random permutation (well if Math.random() is good...) in only 40 swaps.
If you keep swapping two randomly selected elements, I think in theory you should keep swapping them infinitely long to generate a real random permutation...
Message was edited by:
Strider80
> > You should do several hundred swaps.
>
> No you don't; read all about Knuth's or Fisher-Yates'
> shuffle:
> http://en.wikipedia.org/wiki/Shuffling_playing_cards
>
In an ideal world, yes you are right. I think the key phrase in the wiki is "Providing that the random numbers are unbiased". If the numbers are unbiased then just 48 swaps will be needed. I implemented a Knuth type of swap for my Bridge Hand dealer using java.util.Random and got some real strange distributions. By just swapping random pairs several hundred times the strangeness disappeared. I put it down to the fact that that java.util.Random is just based on a simple congruence generator and is not very random.
Of course it could be that I just implemented it wrongly!
> Of course it could be that I just implemented it wrongly!
Well, first of all Bridge players should all be defenestrated head first,
but the java.util.Random() class sure passes quite a few 'randomness
tests'.
Are you sure you implemented Knuth's shuffle algorithm correctly?
For n cards you don't need more than n swaps no matter what those
stuffy nosed superstituous, brain deficient, overweight, ugly, funny
smelling. cheating and bluffing Bridge playing oldtimers say about it ;-)
kind regards,
Jos
> > Of course it could be that I just implemented it
> wrongly!
>
> Well, first of all Bridge players should all be
> defenestrated head first,
No point. We are twisted enough.
> but the java.util.Random() class sure passes quite a
> few 'randomness
> tests'.
>
> Are you sure you implemented Knuth's shuffle
> algorithm correctly?
No! It is simple enough but No I'm not sure.
> For n cards you don't need more than n swaps no
> matter what those
> stuffy nosed superstituous, brain deficient,
> overweight, ugly, funny
> smelling. cheating and bluffing Bridge playing
> oldtimers say about it ;-)
You have been looking at my CV!
One point that came up in a study a few years ago is that the average manual card shuffle
is not very good. Maybe I just want a 'not very good' shuffle!
He probably has done so already but if not I think the OP should just ignore my post.
> One point that came up in a study a few years ago is that the average
> manual card shuffle is not very good. Maybe I just want a 'not very
> good' shuffle!
A couple of months ago I read in the newspaper that bridge players at
a tournament were complaining about the "weird" order of the computer
generated card decks; their claim was that "a human would never deal
like that" ;-)
kind regards,
Jos
> > One point that came up in a study a few years ago
> is that the average
> > manual card shuffle is not very good. Maybe I just
> want a 'not very
> > good' shuffle!
>
> A couple of months ago I read in the newspaper that
> bridge players at
> a tournament were complaining about the "weird" order
> of the computer
> generated card decks; their claim was that "a human
> would never deal
> like that" ;-)
>
:-) Exactly!
> A couple of months ago I read in the newspaper that
> bridge players at
> a tournament were complaining about the "weird" order
> of the computer
> generated card decks; their claim was that "a human
> would never deal
> like that" ;-)
>
One of the "weird" things I found was that a 'computer dealt' bridge hand containing 9 of a suit was not uncommon but playing a the club it happens very rarely (though I did have 9 spades in one hand on Monday).
> One of the "weird" things I found was that a 'computer dealt' bridge
> hand containing 9 of a suit was not uncommon but playing a the club
> it happens very rarely (though I did have 9 spades in one hand
> on Monday).
This is how I shuffle by hand (more or less)import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class Shuffle {
private static Random rand= new Random(System.currentTimeMillis());
// remove a chunk from the front of a list
private static List<Integer> chunk(List<Integer> hand, int max) {
max= Math.min(hand.size(), rand.nextInt(max));
List<Integer> chunk= new ArrayList<Integer>(hand.subList(0, max));
hand.removeAll(chunk);
return chunk;
}
private static List<Integer> mergeShuffle(List<Integer> deck, int mid, int max) {
// 0 .. mid-1 for the lefthand
mid= deck.size()/2+rand.nextInt(2*mid)-mid;
List<Integer> leftHand= new ArrayList<Integer>(deck.subList(0, mid));
// the rest is for the righthand
deck.removeAll(leftHand);
List<Integer> rightHand= new ArrayList<Integer>(deck);
deck.clear();
// merge them together
while (leftHand.size() != 0 && rightHand.size() != 0) {
deck.addAll(chunk(leftHand, max));
deck.addAll(chunk(rightHand, max));
}
deck.addAll(leftHand);
deck.addAll(rightHand);
return deck;
}
public static List<Integer> mergeShuffle(List<Integer> deck, int n, int mid, int max) {
for (int i= 0; i < n; i++)
deck= mergeShuffle(deck, mid, max);
return deck;
}
public static List<Integer> newDeck() {
List<Integer> deck= new ArrayList<Integer>();
for (int i= 0; i < 52; deck.add(i++));
return deck;
}
public static void main(String[] args) {
System.out.println(mergeShuffle(newDeck(), 5, 5, 5));
}
}
kind regards,
Jos
> This is how I shuffle by hand (more or less)
:-) I don't see you handling the CardsDroppedOnFloorException or the method pickupCardsFromFloor(). This method must be heavily optimized because it is a frequently used method (at least it is by me).
P.S. My Son shuffles cards left handed and it hurts to watch. How can your approach be modified for left handed use?
> > This is how I shuffle by hand (more or less)
>
> :-) I don't see you handling the
> CardsDroppedOnFloorException or the method
> pickupCardsFromFloor(). This method must be heavily
> optimized because it is a frequently used method (at
> least it is by me).
The pickupCardsFromFloor() method comes in very handy with my
throwEverythingInTheAirShuffle(); but I wanted to keep that one for a
next reply ;-)
> P.S. My Son shuffles cards left handed and it hurts to watch. How can
> your approach be modified for left handed use?
He only uses one hand for that? Don't trust him: he keeps the good cards
for himself I'm telling you ;-)
kind regards,
Jos (< would *never* cheat at *any* card game ;-)
> > The pickupCardsFromFloor() method comes in very handy
> > with my throwEverythingInTheAirShuffle(); but I wanted to
> > keep that one for a next reply ;-)
> >
>
> :-) Have a good Christmas Jos.
Same to you Sabre (and everybody else of course).
kind regards,
Jos (fridge totally stuffed; let the party commence ;-)
