Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

"Randomly" seeding an array  RSS feed

 
Paul Peterson
Ranch Hand
Posts: 104
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm new to java and had an assignment that I want to take to a higher level. We had to write a black jack program and I quickly realized that the assignment we were given just used random numbers to generate the cards without regard for the composition of the deck. I wanted to incorporate a six deck shoe into the game for more realism. My thought was to loop through from 0 to 311 for the 312 cards in the deck and I tried a switch statement to make sure that no more than 24 of each card value (4 cards per deck times six cards) were used. The first couple of attempts contained SERIOUS logic errors and ended up in infinite loops. The code below, almost works, but by the fifth deck it begins to fail and assign a 0 rather than the card number (1 (ace) - 10, jack -11, queen-12, king-13). this is just a rough attempt. Once I can figure out what is wrong with my logic, I'll go back and make it pretty.



This is the output from one iteration of this code:

1 9 2 11 1 4 11 7 10 8 6 3 11 7 2 2 12 12 13 7 10 9 6 4 5 3 13 8 13 5 9 2 2 8 11 3 3 6 11 9 12 9 6 7 7 9 4 11 3 9 11 10
5 3 4 9 3 1 13 3 5 3 3 6 13 9 12 7 5 11 13 10 10 9 13 10 4 13 6 2 5 4 1 10 7 4 7 5 10 6 10 5 11 12 9 9 2 12 11 5 3 13 1 7
9 13 10 3 12 1 9 13 9 12 5 10 3 10 3 4 5 2 9 4 12 3 11 5 11 3 12 11 4 10 4 5 3 4 2 7 2 13 13 9 9 13 6 12 9 13 7 1 3 13 9 7
2 12 3 12 11 7 2 13 6 3 3 4 9 3 5 12 12 8 1 8 5 7 7 13 1 10 9 10 3 8 10 13 11 8 0 11 12 4 2 1 4 7 10 10 6 7 11 12 10 1 11 0
11 10 7 1 2 11 8 2 11 11 8 6 12 13 7 8 4 7 4 13 1 10 7 2 9 8 5 4 1 4 8 0 0 4 10 11 5 7 4 12 7 0 8 2 5 1 6 0 12 4 10 0
0 0 4 5 0 12 8 0 0 5 2 0 8 1 8 0 5 0 0 6 5 0 0 0 8 0 0 0 8 0 1 0 0 8 8 2 8 12 0 0 0 0 6 0 1 8 2 12 1 0 0 13

I look forward to learning from you.
 
Norm Radder
Ranch Foreman
Posts: 2240
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Another way would be to put the cards into a List and use the Collections class's shuffle method.
 
Stefan Evans
Bartender
Posts: 1836
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
0 is never a number that you assign into the array - and yet there are values in there that are zero.

That isn't your intention, so the question to ask yourself then: how can that be the case?

Hint: If you change your "random number" to always return the number '1' what path does it follow through the code on the 25th '1' ?




 
Paul Peterson
Ranch Hand
Posts: 104
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I haven't worked with the List for quite some time, and would mess things up further that way I fear.

I didn't try to assign a 0 to the array. I think that is part of the error with my switch statement.
 
Stefan Evans
Bartender
Posts: 1836
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Agreed - you didn't assign 0 to the array.
Nothing in your code ever puts a 0 there.

They all start at zero when you create the array though.
Do you ALWAYS assign a value into the array before moving on to the next index number?





 
Norm Radder
Ranch Foreman
Posts: 2240
28
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For easier testing I suggest there be fewer loops made when executing by making these changes:
Also

Also add some print statements to show the variables values as the code executes and to show if or when the default clause is executed.

 
Campbell Ritchie
Marshal
Posts: 55751
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Do you mean you want a random array or do you want to randomise the List of cards? The two are different; you cannot randomise cards with a truly random array.
 
Campbell Ritchie
Marshal
Posts: 55751
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can get a random array out of an object of the Random class with its ints method. That returns an IntStream, and you can get an array simply by using one of the IntStreams's methods.Now you can count whether you have any of the numbers over 24, using a technique similar to that shown for a Map in the Java™ Tutorials. Since 312 ÷ 52 = 6, you will probably find your array contains less than 24 of anything. If you do have over 24, you can always try again.
If, however you want an array up to 13 which will contain exactly 24 of everything, (312 ÷ 13 = 24), you are on a hiding to nothing. That is not random, but shuffling your cards. You can test to see whether you have 24 of everything and repeat the creation of a “random” array until you do get 24 of each, but you have 312! permutations and it will take about 934193462387 years to get 24 of each. If you don't believe me about the duration, try it, and phone when the 934193462387 years are up and tell me I was mistaken

What you want to do is to shuffle a List of cards. You might do well to make your cards from enumerated types. You will have to read the Java™ Tutorials section and the Java® Language Specification (=JLS) section. That is one of the few JLS sections one can easily understand (at least partially).
Briefly, iterate your 24 × 13 = 312 cards; for each get a random number 0‑311 and swap the card in your current position with the card in the random position. That will run in linear time and you can probably iterate the whole 312 several times in 1ms.
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul Peterson wrote:I haven't worked with the List for quite some time, and would mess things up further that way I fear.

It shouldn't. But if you absolutely have to work with arrays:Not a List in sight (although there's an implicit one in that final line), and you don't even need a Random object because Collections.shuffle() takes care of it.
Your shoe array does have to be an Integer[] though, not an int[].

CS 101: Don't re-invent the wheel.

HIH

Winston
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:You can get a random array out of an object of the Random class with its ints method. That returns an IntStream, and you can get an array simply by using one of the IntStreams's methods.

Except I don't think that will do what Paul wants. His array of 312 MUST contain precisely six of every integer between 0 and 51, so applying a randomiser at creation time is too early.

Winston
 
Norm Radder
Ranch Foreman
Posts: 2240
28
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
At what point should a student move past using arrays to using all these advanced classes and methods? I think a good understanding of how to use an array is a requirement for a progammer.
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Norm Radder wrote:At what point should a student move past using arrays to using all these advanced classes and methods? I think a good understanding of how to use an array is a requirement for a progammer.

Good question. Arrays are fundamental "building-block" structures in computer science, and if you rush past them too quickly, you might miss out on things like the 'heap' (or indeed 'stack') property.

However, in Java there is very little difference between an array, and the kind of "fixed" List returned by Arrays.toList() - except that the latter can do LOTS more stuff.
Lists also have the added advantage of being "re-ifable" - which basically means that they are entirely compatible with Java generics - whereas arrays have many "gotchas" when it comes to generics.

So my answer is (as it usually is in CS): it depends what you need. As a Java data structure, Lists offer much more "functionality"; but you're not likely to understand them unless you first know about arrays.

HIH

Winston
 
Campbell Ritchie
Marshal
Posts: 55751
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:. . . Except I don't think that will do what Paul wants. His array of 312 MUST contain precisely six of every integer between 0 and 51 . . .
I came to that conclusion myself, but I thought he wanted twenty‑four of each of thirteen numbers. Agree; you have to create the array and then randomise it later.

Does Collections#shuffle() have the power to shuffle such a large List? Does any computerised method have that power? There is something in Bloch and Gafter Java Puzzlers, page 233‑237. It says that my method will introduce bias into the shuffle, but Collections#shuffle with a normal Random object will find only 2.3×10⁻⁴⁷% of all possible permutations for a 52‑card pack. It has to do with the difference between 2⁶⁴, which is the size of seed and 52! which is the number of permutations in a pack. According to SpeedCrunch, 52! = 8.06581751709438785717×10⁶⁷ and 312! = 2.10202660512637835935×10⁶⁴⁴, which is a lot bigger than 2⁶⁴ (18446744073709551616).
So, yes, you can shuffle that pack with Collections#shuffle, but it lacks the power to find nearly every permutation, and if you do want every permutation, you would have to add a few dozen digits to my guess about the duration.

Or: use Collections#shuffle and nobody will notice the shortcomings of that method. Bloch and Gafter refer you to Knuth §3.4.2 too.
 
Norm Radder
Ranch Foreman
Posts: 2240
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
His array of 312 MUST contain precisely six of every integer between 0 and 51, so applying a randomiser at creation time is too early.

I disagree. The code (with my fixes) generates 4*number-of-decks (24) of the integers between 1 and 13 (Ace to King)
 
Mike Simmons
Ranch Hand
Posts: 3090
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Norm Radder wrote:
His array of 312 MUST contain precisely six of every integer between 0 and 51, so applying a randomiser at creation time is too early.

I disagree. The code (with my fixes) generates 4*number-of-decks (24) of the integers between 1 and 13 (Ace to King)

Without analyzing it too carefully... I agree that the code can or should be able to achieve the desired shuffle, assuming no other subtle bugs. However, it does become increasingly inefficient as the shuffle progresses. Imagine what things are like on the last time through the outer loop, when i = 311. All but one of the card types have been used up, having 24 cards of that type already placed. One type has only 23 cards placed. You keep looping through the inner loop and switch statement, trying to generate, by luck, the value of the missing card - until eventually it succeeds. This shouldn't be necessary. Collections.shuffle() does this much more easily, selecting a new card at each iteration choosing only from among the cards not yet chosen.

Of course, for a Java learner, coding this sort of thing yourself and gradually working through the bugs and inefficiencies can be a useful learning experience. But other than for learning purposes, simply calling Collections.shuffle() makes a lot more sense.
 
Campbell Ritchie
Marshal
Posts: 55751
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mike Simmons wrote:. . . Collections.shuffle() does this much more easily, . . .
It will also do it within the foreseeable lifetime of the Earth
 
Norm Radder
Ranch Foreman
Posts: 2240
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
for a Java learner, coding this sort of thing yourself and gradually working through the bugs and inefficiencies can be a useful learning experience.

I agree and think that is much more important for the OP than a solution that does
it within the foreseeable lifetime of the Earth

Writing more efficient code will come with experience.

Speaking of the OP, where is he? We've sort of taken this thread over.
 
Mike Simmons
Ranch Hand
Posts: 3090
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:
Mike Simmons wrote:. . . Collections.shuffle() does this much more easily, . . .
It will also do it within the foreseeable lifetime of the Earth

Well, you may be overestimating the inefficiency of the posted code. Each time it tries to pick a card, it has at least a 1/13 chance of success. It won't take a modern computer *that* long to achieve this 312 times.
 
Norm Radder
Ranch Foreman
Posts: 2240
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok, I've often thought some of the java methods weren't very efficient. I added a timer for the OPs code (with my mods) and the code from the post at Today 7:56:05 AM
The OP's code takes 1/2 the time of the Collections.shuffle code.


Even when I removed the asList call, the shuffle always took longer. But not 2X
 
Mike Simmons
Ranch Hand
Posts: 3090
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hunh - that's surprising. I'm guessing that mostly comes from using primitives in an array rather than objects in a List, and not having to pre-populate the array. I'm thinking that it would be considerably faster to take the shuffle() algorithm and modify it to operate on an int[] array. Thanks for the report.
 
Piet Souris
Rancher
Posts: 1983
67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why does OP start with: ace = 1, two = 1, et cetera?

And I agree with Mike: OP's method is not that ineffcient (with a worst case of infinite though). The case why the #shuffle might be a tad slower is probably that it has to do 300+ switches.
But since the #shuffle takes so much less code than OP's method, I would prefer it nevertheless. The times that that shoe needs reshuffling are limited, I guess

For our advanced lovers: you could use the IntStream.generate method, with a suitable generator that produces a random(0, 312), then a random(0, 311) et cetera. It then takes two other tricks:
- map a number 0-311 onto a specific deck and card,
- how to interprete the generated numbers of this IntStream?

Edit: I was referring to Mike's previous reply
 
Mike Simmons
Ranch Hand
Posts: 3090
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Replacing Collections.shuffle with a custom int[] shuffle does speed it up, but not as much as I thought. The original (fixed) code is still maybe 20% faster on average. I'm now guessing that's because it doesn't have to randomly access the array - it just populates it once, all in consecutive fashion. The data it does have to keep track of is all on the stack, so faster than retrieving from the heap. Just guessing, though.

Anyway, I shouldn't get too preoccupied with speed. Collections.shuffle() has two other big advantages: it's concise, and most importantly, it's very well tested.

To the original poster: after fixing other bugs previously noted... there seems to be a lot of repetition in the code shown. Do we really need 13 nearly-identical case blocks? Isn't there a way to write a single block of code that handles any of the 13 possible values?
 
Carey Brown
Bartender
Posts: 2998
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:Does Collections#shuffle() have the power to shuffle such a large List? Does any computerised method have that power? There is something in Bloch and Gafter Java Puzzlers, page 233‑237. It says that my method will introduce bias into the shuffle, but Collections#shuffle with a normal Random object will find only 2.3×10⁻⁴⁷% of all possible permutations for a 52‑card pack. It has to do with the difference between 2⁶⁴, which is the size of seed and 52! which is the number of permutations in a pack. According to SpeedCrunch, 52! = 8.06581751709438785717×10⁶⁷ and 312! = 2.10202660512637835935×10⁶⁴⁴, which is a lot bigger than 2⁶⁴ (18446744073709551616).
So, yes, you can shuffle that pack with Collections#shuffle, but it lacks the power to find nearly every permutation, and if you do want every permutation, you would have to add a few dozen digits to my guess about the duration.

Or: use Collections#shuffle and nobody will notice the shortcomings of that method. Bloch and Gafter refer you to Knuth §3.4.2 too.

I was reading up on 52 card shuffles recently and noted that: a) there are roughly 8E+64 unique combinations, and b) a standard "rifle" shuffle should be done at least 7 times in order to statistically yield a deck with not patterns left from the original unsorted deck.

So, Collections.shuffle() can not generate 52! unique patterns. Would calling Collections.shuffle() multiple times fix that? Or is the seed just too small? Or could you use a new seed for each call to shuffle()?
Edit: Or is there an implementation of a random number generator with a sufficiently long seed?
 
Campbell Ritchie
Marshal
Posts: 55751
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey Brown wrote:. . . Or is the seed just too small? Or could you use a new seed for each call to shuffle()?
Use a new Random object with a different seed a few times. If you need seven riffles to shuffle a pack of 52 completely, when you are shuffling 52 cards at a time, you are going to need lots more goes to shuffle your 52 cards completely one at a time. You might get rid of all the patterns, but your 52! goes, That's 8.06581751709438785717×10⁶⁷, and to cover all those possibilities with a 64‑bit seed is going to take a long time, so you might as well shuffle a few times and forget about statistical correctness.

I presume nobody will be betting thousands on this game
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey Brown wrote:So, Collections.shuffle() can not generate 52! unique patterns. Would calling Collections.shuffle() multiple times fix that?

Nope.

Or is the seed just too small?

Yup.

Or could you use a new seed for each call to shuffle()?

You could, but it might well make things worse.

Edit: Or is there an implementation of a random number generator with a sufficiently long seed?

Several, but Java's main one is SecureRandom.

The fact is that just because shuffle() can't produce all 312! (actually quite a bit less because of the repeated cards) possible combinations (and I'm not sure if even SecureRandom can do that) doesn't mean that it's necessarily bad. The shuffle algorithm guarantees that each card has a roughly equal chance of ending up in any particular position, and the only way it could be of any use to a player would be if there was any advantage in knowing that a particular combination of all 312 cards can't happen, which seems doubtful.

Winston
 
Paul Peterson
Ranch Hand
Posts: 104
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Norm Radder wrote:
His array of 312 MUST contain precisely six of every integer between 0 and 51, so applying a randomiser at creation time is too early.

I disagree. The code (with my fixes) generates 4*number-of-decks (24) of the integers between 1 and 13 (Ace to King)


This is what I was looking for. Yes, I do want 312 cards total, 24 of each value.

Thank you!
 
Norm Radder
Ranch Foreman
Posts: 2240
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How are you doing with the project? Did you try what I suggested in my post of 6/8/2016 6:51:47 AM
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul Peterson wrote:This is what I was looking for. Yes, I do want 312 cards total, 24 of each value.

Erm, not unless you're using a different kind of deck from the rest of the world.

There are indeed 13 values, but there are also 4 suits, making a total of 52 cards; so a 6-deck show may contain 24 Aces, but it will contain only (and exactly) six A♥.

Winston
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!