aspose file tools*
The moose likes Beginning Java and the fly likes Other Shuffling question Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Other Shuffling question" Watch "Other Shuffling question" New topic
Author

Other Shuffling question

Keith Wong
Greenhorn

Joined: Jun 03, 2008
Posts: 7
I found this interesting question, any idea? Thanks.

Define a shuffle of a deck of cards as follows: take the top card of the deck and put it on the bottom. Take the next top card and set it on the table. Take the next top card and put in on the bottom of the original deck. Take the next top card and set it on top of the card on the table. Continue in this way until all of the cards are in the deck on the table.

Given a deck with n cards, write a Java program to determine the minimum number of shuffles it takes to return the deck to its original order. The program should accept the number of cards in the deck as an argument and return the result on system.out. You may use any data structures you like but try to minimize the amount of looping.

Provide answers for -1, 0, 1, 2, 10, 33, 51, 9999 cards.
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24166
    
  30

Hi,

Welcome to JavaRanch!

Turns out we don't like to do people's homework for them here at the Ranch. We're very happy to help you do it, though. So, what have you got so far? Where are you stuck?

I'm moving this off to our Beginner's forum, by the way.


[Jess in Action][AskingGoodQuestions]
Keith Wong
Greenhorn

Joined: Jun 03, 2008
Posts: 7
I able to got count on up to 500 cards in deck. That need 10.5 millions time to shuffle. Once the cards in a deck hitting ~2k. The program draw 100% CPU and keep running.

I had use linked List and do while loop next shuffle check by object ording like :
if (((Integer)cardsOnTable.get(i)).intValue() != i)

I found the 99% of shuffling and order check is around 0ms each time.

So the question is any smart guys here good on algorithms can do the shuffles multiple time instead of one-by-one. Or other suggestion.

Here is situation on 10 cards, that takes 21 shuffles back to original.

0123456789
4806297531
2347015968
0625489173
4709231856
2541068397
0928473615
4103256789
2846097531
0327415968
4605289173
2749031856
0521468397
4908273615
2143056789
0826497531
4307215968
2645089173
0729431856
4501268397
2948073615
0123456789

BTW, I hope I can back to school.

Thanks in advance for any suggestion.

Keith
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10916
    
  12

One of the problems with making improvements is you don't REALLY know where your program is slowing down. you can spend hours re-factoring the part you THINK slows it down, only to get a minor improvement.

One of the best places to start is to figure out what is taking so long... is it the shuffling or the checking the order?

there are various tools you can use, or even some java classes that may help. i'd start by analyzing what my program is actually doing first.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10916
    
  12

note that with some analysis, you can also figure out a pretty fast way to do the shuffle (i think...).

I believe it is possible to build each new shuffle fairly easily and efficiently, without going through the whole process of moving stuff around. i think you can pretty much simply remove the proper card from one linked list, and insert it into the other in the correct spot...

I'll leave it to you to think about how to do that.
Keith Wong
Greenhorn

Joined: Jun 03, 2008
Posts: 7


This is the one i am using. If there is any improvement? Thanks,

Keith
Nicholas Jordan
Ranch Hand

Joined: Sep 17, 2006
Posts: 1282
Look through the entire Collections Tool Suite, consider what the other posters have already told you. Remember Tim Toadie, The Roadie: "There's More Than One Way To Do It."
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19544
    
  16

Originally posted by Keith Wong:


This is the one i am using. If there is any improvement? Thanks,

Keith

I see two improvements:
1) use !isEmpty() instead of size() > 0. The method is there for a reason, and it could be faster. If not, it's mostly implemented as "size == 0" anyway.

2) This will fail if there is an odd number of cards on the stack. Check You have to check inside the loop as well:


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Gavin Tranter
Ranch Hand

Joined: Jan 01, 2007
Posts: 333
I do have two thoughtsL
Could recurssion help here?
Is there not a "pure" maths solution?
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19544
    
  16

Why use recursion if a simple loop will suffice? Remember, for recursion, you have a fresh set of variables for each call. That could lead to a java.lang.StackOverflowError even though there is no infinite loop if the nesting goes too deep.
Vilmantas Baranauskas
Ranch Hand

Joined: Dec 20, 2006
Posts: 89

2) This will fail if there is an odd number of cards on the stack. Check You have to check inside the loop as well:


No, it will not fail. You don't have to check inside the loop.


Author of <a href="http://www.newsinjector.com" target="_blank" rel="nofollow">NewsInjector</a>
Bill Cruise
Ranch Hand

Joined: Jun 01, 2007
Posts: 148

2) This will fail if there is an odd number of cards on the stack. Check You have to check inside the loop as well:


You don't have to check inside the loop. The first line in the loop removes the top card from the deck and puts in at the bottom, so when you're down to one card the deck remains unchanged.

I would look at how you're checking that the order of the deck has returned to the starting position. It's possible that the order has returned to normal but you're missing it by a bad order checking method that works for smaller lists. Would you post that method?
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19544
    
  16

You're both absolutely right of course. I just saw two removes after each other and thought that it was waiting for an error to occur. Of course I forgot all about the first removed element being reinserted again.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10916
    
  12

it might just also be that the number of shuffles grows exponentially... i'm not sure how to calculate it. it just might take a long time. you could put in a counter and print out something every thousand or ten thousand loops and see what's going on that way as well.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10916
    
  12

also, i don't think you need to really do all that deleting and inserting... here is a look at what happens:

Note that on the line with the star, we have basically removed every other element from the original list. if you start at the 'front' of the original list, you add the elements to the 'back' of the new list.

Then, our original list had 02468. as we go through, we AGAIN add every other element to the front of the new list (the 2, then the 6).

So, if you have a way to remove an element from the middle of the list, you can iterate across the original list, removing every other one, and add them to the front of the new list.

then, YOU CAN DO THAT AGAIN and again, until the original list is empty.

this saves you teh time of moving all those elements from the front to the back.

i don't KNOW that this will speed anything up, but it might...that's why you need to analyze WHERE things are slowing down.
Keith Wong
Greenhorn

Joined: Jun 03, 2008
Posts: 7
fred,
That is what I am experiencing now. If that is 10k cards, each shuffle logic cost 15-300ms each.

I also get the similar idea this morning before read yours. Now I will implement them, hope that works.

Thanks,
Keith
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Other Shuffling question
 
Similar Threads
Cards
Need help with constructor and fields
Card Shuffle Problem
String issue in Java code
How would i shuffle my deck of cards?