help me with this prog problem

[z0mb13]

OK I already posted this in 2 other forums (OT and software), but still I havent find the right answer
So Ill try my luck here

Given a deck of nCards unique cards, cut the deck iCut cards from top and perform a perfect shuffle. A perfect shuffle begins by putting down the bottom card from the top portion of the deck followed by the bottom card from the bottom portion of the deck followed by the next card from the top portion, etc., alternating cards until one portion is used up. The remaining cards go on top. The problem is to find the number of perfect shuffles required to return the deck to its original order. Your function should be declared as:

static long shuffles(int nCards,int iCut);

Find the result of shuffles(1002,101)

any hints of the algorithm???

I know I can just do the algorithm over and over again until it becomes the original deck, however, there MUST be a much more elegant solution

any help?

TIA

EDIT: no this is NOT a HW problem

 

[heliomphalodon]

This ought to get you started:

First, I guess we're assuming that the cut-point 'iCut' is constant.

Each of your (cut-then-shuffle) operations is a permutation of the cards. You only need to look at the first such permutation to determine the number of permutation operations required to restore the original order. This number is the "period" of the permutation.

One way to determine the period of a permutation is to decompose it into cycles. Once this is done, it is a simple matter to compute the period of the permutation -- it is the least-common-multiple of the lengths of all the cycles.

Suppose that you have two arrays
int before[nCards]; and
int after[nCards];
where before[j] = j for 0 <= j < nCards.

Then do your cut-then-shuffle operation on the before[] array and place the results in the after[] array.

Now suppose that you have another array
int cycleID[nCards];
Start by setting cycleID[0] = 0;

For each i where 0 <= i < nCards you can scan through the after[] array looking for i. Suppose that you find it in position j, by which I mean that after[j] == i. Then set cycleID[j] = i; and rescan the after[] array, now looking for j. Suppose you find it in position k, so after[k] == j. Then set cycleID[k] = i. (Yes, i not j.) Continue in this fashion until you have closed the cycle. Then move on to the next undetermined index in cycleID[] and trace out its cycle. Continue until you have determined the cycleID[] array completely.

Finally scan through the cycleID[] array and determine the length of each cycle, and compute the LCM of the lengths. That's the number you seek.

OK, I know it's not as pretty as Knuth would do it, but I don't want to steal your fun by writing the code for you.

 

[z0mb13]

I am sorry, but I still dont get why and how ur solution works

what is the cycle thing that you are seeking? and how does finding least common multiple helps??

also whos Knuth??

 

[heliomphalodon]

Well, let's consider a very simple example.

Suppose that we have a permutation P of 7 elements like this:

{ 0, 1, 2, 3, 4, 5, 6 } is mapped by P to
{ 2, 5, 0, 6, 1, 3, 4 } . Think of that as one pass of "cut-and-shuffle".

This permutation can be written as a product of cycles:
P = (0, 2)(1, 5, 3, 6, 4) which means that 0->2->0 and 1->5->3->6->4->1

The cycleID array would look like this:
{ 0, 1, 0, 1, 1, 1, 1 } because 0 and 2 are in cycle #0, while the remaining elements are in cycle #1.

The lengths of the cycles are 2 and 5, and LCM(2, 5) equals 10 so the permutation P must be applied 10 times to restore the original order.

The fundamental facts involved are:
1) any permutation may be decomposed into a product of cycles (and this decomposition is unique in a certain sense)
2) the period of a permutation is the LCM of the lengths of its cycles.

No offense, but if you don't understand those facts, you can't understand the algorithm.

"Knuth" is, of course, Donald Knuth, author of The Art of Computer Programming. As I recall, he presents an algorithm for performing the decomposition-into-cycles of an arbitrary permutation in a single pass through what I have called the after[] array. The algorithm that I sketch is embarassingly crude compared to his.

 

[z0mb13]

wow is this like grad level math or cs theory??

I've never come across this during my CS undergrad at UCB

 

[heliomphalodon]

When I took my undergraduate degree (at Reed College in the late 1970's) these results were derived in introductory group theory, which a Math major would probably take as a sophomore. As a CS major, you might not cover such material. But for a CS major to not know of Donald Knuth, well, that's frightening. :Q Again, I mean no offense, but what can your instructors at Cal be thinking? :frown:

 

[z0mb13]

hahahaha

no actually the name Knuth rings a bell, maybe I just totally forgot about him

 

[heliomphalodon]

Well, I couldn't resist coding this up.
Mind you, it could be made much faster,
but I tried to stick as closely as I could to
the algorithm that I outlined in
my first post to this thread.

Sadly, the formatting is destroyed
when it is posted here, but of course
you could run it through a C-beautifier

An ANSI C compiler should take it just as it is...

/*
* shuffles.c
*
* find the period of a certain kind of permutation
*
* this program is just a toy, it has many limitations
* it is written to be relatively clear, not efficient
*
* shuffles(1002, 101) = 1517137304
*
*/

#include <stdio.h>

extern int atoi ( const char * ) ;
extern void exit ( int ) ;

extern int main ( int , char ** ) ;

static long gcd ( long , long ) ;
static long lcm ( long , long ) ;
static void initialize ( int ) ;
static void cutshuffle ( int , int ) ;
static int locate ( int , int * , int ) ;
static long shuffles ( int , int ) ;

#define BIGCARD 32767

static int before[BIGCARD] ;
static int after[BIGCARD] ;
static int cycleID[BIGCARD] ;

static long
gcd(a, b)
long a ;
long b ;
{
long r ;

if (a <= 1)
return 1 ;
else if (b <= 1)
return 1 ;
else {
while (0 != b) {
r = a % b ;
a = b ;
b = r ;
}
return a ;
}
}

static long
lcm(a, b)
long a ;
long b ;
{
if (a == 0)
return 0 ;
else if (b == 0)
return 0 ;
else if (a == 1)
return b ;
else if (b == 1)
return a ;
else {
a /= gcd(a, b) ;
return a * b ;
}
}

static void
initialize(topcard)
int topcard ;
{
int j ;

for (j = 0 ; j < topcard ; ++j) {
before[j] = j ;
cycleID[j] = -1 ;
}
}

static void
cutshuffle(topcard, cutdepth)
int topcard ;
int cutdepth ;
{
int j ;
int k ;
int m ;
int split ;

j = 0 ;
k = split = topcard - cutdepth ;
m = 0 ;

if (split < cutdepth) {
while (j < split) {
after[m++] = before[k++] ;
after[m++] = before[j++] ;
}
while (k < topcard)
after[m++] = before[k++] ;
}
else if (split == cutdepth)
while (m < topcard) {
after[m++] = before[k++] ;
after[m++] = before[j++] ;
}
else {
while (k < topcard) {
after[m++] = before[k++] ;
after[m++] = before[j++] ;
}
while (j < split)
after[m++] = before[j++] ;
}
}

static int
locate(what, where, limit)
int what ;
int *where ;
int limit ;
{
int j ;

for (j = 0 ; j < limit ; ++j)
if (where[j] == what)
return j ;
return -1 ;
}

static long
shuffles(nCards, iCut)
int nCards ;
int iCut ;
{
int j ;
int k ;
int thisID ;
int length ;
long period ;

initialize(nCards) ;
cutshuffle(nCards, iCut) ;

while ((thisID = locate(-1, cycleID, nCards)) != -1)
for (j = thisID ; cycleID[j] == -1 ; j = locate(j, after, nCards))
cycleID[j] = thisID ;

period = 1L ;
for (thisID = 0 ; thisID < nCards ; ++thisID)
if (locate(thisID, cycleID, nCards) != -1) {
for (length = k = 0 ; k < nCards ; ++k)
if (cycleID[k] == thisID)
++length ;
period = lcm(period, (long)length) ;
}

return period ;
}

extern int
main (ac, av)
int ac ;
char **av ;
{
int nCards ;
int iCut ;
char *myname ;

if (ac != 3) {
(void)fprintf(stderr, "Usage: %s nCards iCut\n", *av) ;
exit(1) ;
return 1 ;
}

myname = *av ;
nCards = atoi(*++av) ;
iCut = atoi(*++av) ;

if (nCards < 1) {
(void)fprintf(stderr, "%s: error: nCards must be greater than zero\n", myname) ;
exit(1) ;
return 1 ;
}
if (nCards > BIGCARD) {
(void)fprintf(stderr, "%s: implementation limit: nCards may not exceed %d\n", myname, BIGCARD) ;
exit(2) ;
return 2 ;
}
if (iCut < 0) {
(void)fprintf(stderr, "%s: error: iCut must be at least zero\n", myname) ;
exit(1) ;
return 1 ;
}
if (iCut > nCards) {
(void)fprintf(stderr, "%s: error: iCut may not exceed nCards\n", myname) ;
exit(1) ;
return 1 ;
}

(void)fprintf(stdout, "shuffles(%d, %d) = %ld\n", nCards, iCut, shuffles(nCards, iCut)) ;

exit(0) ;
return 0 ;
}

 

[heliomphalodon]

Well, sorry to say my code has an error. On the machine that I was using, a "long" is 32 bits. It turns out that the answer to your original question about shuffles(1002, 101) requires a larger variable. :Q

My algorithm is still correct, the only change needed is that all my "long" data types need to be "long long" instead.

The correct answer (really, this time) is shuffles(1002, 101) = 5812104600 I think it would have taken you quite a long time to brute-force this through repeated shuffling...

Even with 64-bit integer data types, the program cannot compute shuffles(11111, 1111) correctly due to overflow in the lcm() function.

 

[capybara]

fwiw, isnt there a more elegant recursive solution?

 

[z0mb13]

Originally posted by: capybara
fwiw, isnt there a more elegant recursive solution?

enlighten us!...

 

[heliomphalodon]

Originally posted by: capybara
fwiw, isnt there a more elegant recursive solution?

Talk is cheap -- let's see this solution! I'll venture to guess that it'll have trouble if it has to recurse to 5812104600 levels.

What I'd most like to see is a simple closed-form function of nCards and iCut that gives directly the period of the resulting permutation.

 

[z0mb13]

OK I tried to write ur code in Java, however there must be something I am doing wrong, I keep getting 1 for the result..


public class Shuffle {

private int nCards;
private int iCut;
private int before[];
private int after[];
private int cycleID[];

static long gcd(long a,long b)
{
long r ;

if (a <= 1)
return 1 ;
else if (b <= 1)
return 1 ;
else {
while (0 != b) {
r = a % b ;
a = b ;
b = r ;
}
return a ;
}
}




static long lcm(long a,long b)
{
if (a == 0)
return 0 ;
else if (b == 0)
return 0 ;
else if (a == 1)
return b ;
else if (b == 1)
return a ;
else {
a /= gcd(a, b) ;
return a * b ;
}
}


public Shuffle(int nCards,int iCut) {
nCards = nCards;
iCut = iCut;

before = new int[nCards];
after = new int[nCards];
cycleID = new int[nCards];
}

public void initialize() {
for(int i = 0; i < nCards; i++) {
before = i;
cycleID = i;
}
}

public void shuffleOnce() {
int split = nCards - iCut;
int j=0;
int k=0;
int m=0;

if(split < iCut) {
while (j < split) {
after[m++] = before[k++];
after[m++] = before[j++];
}
while (k < nCards)
after[m++] = before[k++] ;
}
else if(split == iCut) {
while (m < nCards) {
after[m++] = before[k++] ;
after[m++] = before[j++] ;
}
}
else {
while (k < nCards) {
after[m++] = before[k++] ;
after[m++] = before[j++] ;
}
while (j < split)
after[m++] = before[j++] ;
}
}

public int locate(int what,int where[],int limit) {
int j ;
for (j = 0 ; j < limit ; j++)
if (where[j] == what)
return j ;
return -1 ;
}



public long shuffle() {
initialize();
shuffleOnce();

int j,k,thisID,length;
long period;

while ((thisID = locate(-1, cycleID, nCards)) != -1)
for (j = thisID ; cycleID[j] == -1 ; j = locate(j, after, nCards))
cycleID[j] = thisID ;


period = 1L ;
for (thisID = 0 ; thisID < nCards ; ++thisID)
if (locate(thisID, cycleID, nCards) != -1) {
for (length = k = 0 ; k < nCards ; ++k)
if (cycleID[k] == thisID)
++length ;
period = lcm(period, (long)length) ;
}

return period;
}



public static void main (String[] args) {
if(args.length != 2) {
System.out.println("Usage: java Shuffle <nCards> <iCut>");
System.exit(1);
}

int numCards = Integer.parseInt(args[0]);
int cutSize = Integer.parseInt(args[1]);

System.out.println("numCards is "+numCards+" cutSize is "+cutSize);

Shuffle s = new Shuffle(numCards, cutSize);

long result = s.shuffle();

System.out.println("Result is " + result);
}
}

 

[heliomphalodon]

Originally posted by: z0mb13
OK I tried to write ur code in Java, however there must be something I am doing wrong, I keep getting 1 for the result..

Wish I could help, but I'm an old K&R C-codin' man. To me, "java" is an alternate spelling of "slow".

When I first ran my program, it didn't print the value of shuffles(), all I got was "shuffles(1002, 101) ="
I thought my algorithm was broken, so I put in some code to display the arrays after initialization, then after the first shuffle, then prior to the LCM calculation. What I finally noticed was that nothing was wrong with the algorithm, but that I had "%l" rather than "%ld" in my fprintf() format string. I suggest that you do the same kind of thing -- looking at the arrays will show you if the algorithm is broken. Similarly, if you put a print statement in the lcm() function, you can see whether the calculation of the period is proceeding correctly (and also if it's overflowing). Try some simple cases like shuffles(10, 1) and shuffles(10, 10).

Have fun!

 

[TerryMathews]

Originally posted by: heliomphalodon

Originally posted by: capybara
fwiw, isnt there a more elegant recursive solution?

Talk is cheap -- let's see this solution! I'll venture to guess that it'll have trouble if it has to recurse to 5812104600 levels.

What I'd most like to see is a simple closed-form function of nCards and iCut that gives directly the period of the resulting permutation.

A ha, but if you carefully laid out your recursion, you could take advantage of the tail call optimization, therefore keeping the stack at a static size throughout the recursion.

Don't look at me, I have my own homework to do.

 

[RossGr]

I guess I do not understand the word elegant, here we have a beautiful solution which requires 1 shuffle and then inspect the deck to compute an explicit solution. You really think anything recursive can be more elegant then that! Recursive is not elegant it is brute force.

 

[Codewiz]

Originally posted by: RossGr
I guess I do not understand the word elegant, here we have a beautiful solution which requires 1 shuffle and then inspect the deck to compute an explicit solution. You really think anything recursive can be more elegant then that! Recursive is not elegant it is brute force.

Recusion just makes for nice clean looking code. Yes it is elegant but hell if I am going to use it if I want speed.

 

[heliomphalodon]

Originally posted by: Codewiz
Recursion just makes for nice clean looking code.
Yes it is elegant but hell if I am going to use it if I want speed.

I must protest that my code, when properly formatted, actually does look nice and clean.
Besides -- not only does it work, it's the only implementation displayed so far.

I'm genuinely curious as to how one would do this recursively.
Can anyone post even a sketch of such an algorithm?

 

[PowerMacG5]

If it can be done relatively normally (when I say normally, I mean not requiring an obscene number of lines of code, to do something that can be done in a few lines with recursion), I personally prefer a non-recursive apporach, that a recursive approach. If the recursion gets too deep, and dince you are using a long long, you can easily run out of memory. Yes, recursion is easier, and requires less coding in some circumstances, bus as previously said, it is a brute force method. A non-recursive algorithm may be longer, more drawn out, but to me it is more elegant, functional, and faster on my computers. The recursion requires it to finish the entire recursive call, until it actually uses the data retrieved by the recursion. In a non-recursive algorithm, you use the data as it comes to you. I find a well planned out pseudo-code beforehand, or an outline, can make it a lot easier to visualize the approach.

 

[heliomphalodon]

Bump, because I still want to see a recursive solution.

 

[PowerMacG5]

Originally posted by: heliomphalodon
Bump, because I still want to see a recursive solution.

I'm going to second that, because I want to see it too.

 

[heliomphalodon]

OK, I've found and implemented a recursive algorithm. I must admit, it's pretty but it generates segmentation violations as its stack overflows. I also implemented the naive iterative algorithm just for laughs. I made minor changes to the original code so that the calling sequence for the shuffles() function could be the same regardless of the algorithm used, but it should still be pretty clear. If anyone cares to have a copy of the complete program, PM me with your email address and I'll be happy to send it along.

/*
* new function
*/

static int
restored(topcard, deck)
int topcard ;
int *deck ;
{
int j ;

for (j = 0 ; j < topcard ; ++j)
if (*deck++ != j)
return 0 ;
return 1 ;
}

/*
* recursive implementation
*/

static long long
shuffles(nCards, iCut, deck, tmp)
int nCards ;
int iCut ;
int *deck ;
int *tmp ;
{
cutshuffle(nCards, iCut, deck, tmp) ;

if (restored(nCards, tmp))
return 1 ;
else
return 1 + shuffles(nCards, iCut, tmp, deck) ;
}

/*
* iterative implementation
*/

static long long
shuffles(nCards, iCut, deck, tmp)
int nCards ;
int iCut ;
int *deck ;
int *tmp ;
{
long long period ;
int *swap ;

period = 0 ;

do {
++period ;
cutshuffle(nCards, iCut, deck, tmp) ;
swap = deck ; deck = tmp ; tmp = swap ;
} while (!restored(nCards, deck)) ;

return period ;
}

 

[z0mb13]

The recursive implementation IMO is just like the naive way of doing this (shuffle, check if it is back to original, shuffle again, chek again etc)

The shuffle once and check for the period is much better IMO

 

[heliomphalodon]

Originally posted by: z0mb13
The recursive implementation IMO is just like the naive way of doing this (shuffle, check if it is back to original, shuffle again, check again etc)

The shuffle once and check for the period is much better IMO

Yes, and neither the recursion nor the iteration has any real chance of answering the original question.
Of the three algorithms displayed, only the inspection implementation can do that!

 

[z0mb13]

it seems that u are VERY knowledagble of programming in general...

what do u do in life??