Programming Puzzle

[oboeguy]

Originally posted by: chuckywang
I'm all ears for an algorithm that can do this with only one use of the random number generator.

Conceptually that's easy: there are n! permutations of the deck, generate a (pseudo-)random number between 1 and n! and come-up with a map from the number to a permutation. Heh, mathematician's answer there. The problem with that is that you probably don't have enough precision in a computer to exactly do 52!, and how long would computing the result of the mapping take? 😀

Edit: and I'll bet you'd have trouble finding a (pseudo)-random number generator that could give you 52! different answers. So from an information-theoretical point of view, you're SOL.

 

[tikwanleap]

Originally posted by: oboeguy

Originally posted by: chuckywang
I'm all ears for an algorithm that can do this with only one use of the random number generator.

Conceptually that's easy: there are n! permutations of the deck, generate a (pseudo-)random number between 1 and n! and come-up with a map from the number to a permutation. Heh, mathematician's answer there. The problem with that is that you probably don't have enough precision in a computer to exactly do 52!, and how long would computing the result of the mapping take? 😀

Edit: and I'll bet you'd have trouble finding a (pseudo)-random number generator that could give you 52! different answers. So from an information-theoretical point of view, you're SOL.

Damn 52! is huge!

52 ! = 8.06581752 × 10^67

http://www.google.com/search?sourceid=n...&rls=GGLD,GGLD:2004-28,GGLD:en&q=52%21

 

[tikwanleap]

Originally posted by: tikwanleap

Originally posted by: oboeguy

Originally posted by: chuckywang
I'm all ears for an algorithm that can do this with only one use of the random number generator.

Conceptually that's easy: there are n! permutations of the deck, generate a (pseudo-)random number between 1 and n! and come-up with a map from the number to a permutation. Heh, mathematician's answer there. The problem with that is that you probably don't have enough precision in a computer to exactly do 52!, and how long would computing the result of the mapping take? 😀

Edit: and I'll bet you'd have trouble finding a (pseudo)-random number generator that could give you 52! different answers. So from an information-theoretical point of view, you're SOL.

Damn 52! is huge!

52 ! = 8.06581752 × 10^67

http://www.google.com/search?sourceid=n...&rls=GGLD,GGLD:2004-28,GGLD:en&q=52%21

Well, if you have a humongous lookup table with all the permutations of 52 cards then the mapping wouldn't be a problem. 😛😀

 

[Dissipate]

Originally posted by: HBalzer

Originally posted by: Dissipate
Here is an interesting programming puzzle you might want to try:

You want to program a card game that uses a standard deck of 52 playing cards. In order to program such a game you have to simulate a deck of cards being dealt one by one off the top of a virtual deck. Hence, you must write a function that shuffles the deck of cards before the cards are dealt.

So an array of integers from 1 - 52 is passed into your function Shuffle(). Shuffle() then randomizes the location of all the numbers in the array to simulate the deck of cards being thoroughly shuffled. The only things you have to work with are the array itself and a random number generator, plus some integer variables to use as placeholders and of course standard loops.

Explain the algorithm of the Shuffle() function.

What school are you attending?

UCSD

 

[oboeguy]

Originally posted by: tikwanleap

Originally posted by: tikwanleap

Originally posted by: oboeguy

Originally posted by: chuckywang
I'm all ears for an algorithm that can do this with only one use of the random number generator.

Conceptually that's easy: there are n! permutations of the deck, generate a (pseudo-)random number between 1 and n! and come-up with a map from the number to a permutation. Heh, mathematician's answer there. The problem with that is that you probably don't have enough precision in a computer to exactly do 52!, and how long would computing the result of the mapping take? 😀

Edit: and I'll bet you'd have trouble finding a (pseudo)-random number generator that could give you 52! different answers. So from an information-theoretical point of view, you're SOL.

Damn 52! is huge!

52 ! = 8.06581752 × 10^67

http://www.google.com/search?sourceid=n...&rls=GGLD,GGLD:2004-28,GGLD:en&q=52%21

Well, if you have a humongous lookup table with all the permutations of 52 cards then the mapping wouldn't be a problem. 😛😀

That would require O(n!) time to create... ouch.

 

[DaShen]

Originally posted by: chuckywang
Randomly generate a number from 1-52. Put that card as the first card in your shuffled deck. Randomly generate a number from 1-51. Put that card as the second card in your shuffled deck. Etc...

That doesn't work Unless you are assured of the "random" number being the topmost value on the list. 😉 and iterative inserts into the array are not efficient. Better to have the deck already in the array and switch the cards around a certain number of times.

 

[chuckywang]

Originally posted by: DaShen

Originally posted by: chuckywang
Randomly generate a number from 1-52. Put that card as the first card in your shuffled deck. Randomly generate a number from 1-51. Put that card as the second card in your shuffled deck. Etc...

That doesn't work Unless you are assured of the "random" number being the topmost value on the list. 😉 and iterative inserts into the array are not efficient. Better to have the deck already in the array and switch the cards around a certain number of times.

I don't know what you mean by being assured of the random number being the topmost value in the list, but it should work. I agree it's probably not the best or most efficient way, but it should work.

 

[dabuddha]

I've done this for a blackjack game I wrote in Java and do your own damned homework 😀

 

[mugs]

Originally posted by: chuckywang

Originally posted by: DaShen

Originally posted by: chuckywang
Randomly generate a number from 1-52. Put that card as the first card in your shuffled deck. Randomly generate a number from 1-51. Put that card as the second card in your shuffled deck. Etc...

That doesn't work Unless you are assured of the "random" number being the topmost value on the list. 😉 and iterative inserts into the array are not efficient. Better to have the deck already in the array and switch the cards around a certain number of times.

I don't know what you mean by being assured of the random number being the topmost value in the list, but it should work. I agree it's probably not the best or most efficient way, but it should work.

He means that unless your array collapses when you pull a value out of the middle, you're going to have problems.

Screw efficiency, you could write a terribly inefficient algorithm to do this and it'd still take an infantesimal amount of time. 🙂

 

[Rayden]

Originally posted by: Kyteland

Originally posted by: Rayden
I guess I was wrong when I specified O(n) time as it is actually O(1). I should have said O(n) or better.

And the sum should be:
0 + 1 + 2 + ... + n = (n)*(n+1)/2

Subtracting n numbers from (n)*(n+1)/2 is O(1)? 😕

Oops.

Here is an interesting problem. How would you write an algorithm to generate every permutation? I am TA'ing a class where the students are given 8 sorts and they have to run tests on them to determine what sort is what, ie big-oh. One of the sorts is n! and it creates every single permutation and tests to see if it is correct.

At first, it appears related to the card deck randomness, but it isn't.

 

[chuckywang]

Originally posted by: mugs

Originally posted by: chuckywang

Originally posted by: DaShen

Originally posted by: chuckywang
Randomly generate a number from 1-52. Put that card as the first card in your shuffled deck. Randomly generate a number from 1-51. Put that card as the second card in your shuffled deck. Etc...

That doesn't work Unless you are assured of the "random" number being the topmost value on the list. 😉 and iterative inserts into the array are not efficient. Better to have the deck already in the array and switch the cards around a certain number of times.

I don't know what you mean by being assured of the random number being the topmost value in the list, but it should work. I agree it's probably not the best or most efficient way, but it should work.

He means that unless your array collapses when you pull a value out of the middle, you're going to have problems.

Screw efficiency, you could write a terribly inefficient algorithm to do this and it'd still take an infantesimal amount of time. 🙂

Yeah, you would have to collapse the array for my algorithm to work.

 

[Dissipate]

Originally posted by: Rayden

Originally posted by: Kyteland

Originally posted by: Rayden
I guess I was wrong when I specified O(n) time as it is actually O(1). I should have said O(n) or better.

And the sum should be:
0 + 1 + 2 + ... + n = (n)*(n+1)/2

Subtracting n numbers from (n)*(n+1)/2 is O(1)? 😕

Oops.

Here is an interesting problem. How would you write an algorithm to generate every permutation? I am TA'ing a class where the students are given 8 sorts and they have to run tests on them to determine what sort is what, ie big-oh. One of the sorts is n! and it creates every single permutation and tests to see if it is correct.

At first, it appears related to the card deck randomness, but it isn't.

If the permutations form a symmetric group that is cyclic, just find the generator and compose it with itself n! times. 🙂

 

[Rayden]

Originally posted by: Dissipate

Originally posted by: Rayden

Originally posted by: Kyteland

Originally posted by: Rayden
I guess I was wrong when I specified O(n) time as it is actually O(1). I should have said O(n) or better.

And the sum should be:
0 + 1 + 2 + ... + n = (n)*(n+1)/2

Subtracting n numbers from (n)*(n+1)/2 is O(1)? 😕

Oops.

Here is an interesting problem. How would you write an algorithm to generate every permutation? I am TA'ing a class where the students are given 8 sorts and they have to run tests on them to determine what sort is what, ie big-oh. One of the sorts is n! and it creates every single permutation and tests to see if it is correct.

At first, it appears related to the card deck randomness, but it isn't.

If the permutations form a symmetric group that is cyclic, just find the generator and compose it with itself n! times. 🙂

Generator? The object is to write it yourself. I am not aware of any generators that take an array of size N and will permute it.

 

[Dissipate]

Originally posted by: Rayden

Originally posted by: Dissipate

Originally posted by: Rayden

Originally posted by: Kyteland

Originally posted by: Rayden
I guess I was wrong when I specified O(n) time as it is actually O(1). I should have said O(n) or better.

And the sum should be:
0 + 1 + 2 + ... + n = (n)*(n+1)/2

Subtracting n numbers from (n)*(n+1)/2 is O(1)? 😕

Oops.

Here is an interesting problem. How would you write an algorithm to generate every permutation? I am TA'ing a class where the students are given 8 sorts and they have to run tests on them to determine what sort is what, ie big-oh. One of the sorts is n! and it creates every single permutation and tests to see if it is correct.

At first, it appears related to the card deck randomness, but it isn't.

If the permutations form a symmetric group that is cyclic, just find the generator and compose it with itself n! times. 🙂

Generator? The object is to write it yourself. I am not aware of any generators that take an array of size N and will permute it.

No, I'm talking about a generator for the symmetric group of order N. Some of the sub-groups of symmetric groups are cyclic.

Info on symmetric groups:
Text

And an interesting fact regarding symmetric groups:

Text