Board Logo
« SHUFFLING (Cards, Questions, Images) »

Welcome Guest. Please Login or Register.
Jan 18th, 2018, 3:51pm


Conforums Terms of Service | Membership Rules | Home | Search | Recent Posts | Notification | Format Your Message | Installation FAQ

This board is not meant for general discussion, it is meant for posting articles to help others.
For general discussions use the appropriate board, which best describes your problem area.

« Previous Topic | Next Topic »
Pages: 1 2 3  Notify Send Topic Print
 veryhotthread  Author  Topic: SHUFFLING (Cards, Questions, Images)  (Read 1868 times)
Welopez
Moderator
ImageImageImageImageImage


member is offline

Avatar

Never let your beliefs get in the way of learning.


PM

Gender: Male
Posts: 4407
xx Re: SHUFFLING (Cards, Questions, Images)
« Reply #15 on: May 14th, 2012, 10:05pm »

An excellent routine, Gearce. It works in JB with no need for a SORT command. I think it could also be modified to work using a multi-Dim array, with CARDS in the first dimension and USED in the second.

It looks similar to the shuffle routine Wilf Heys contributed to the JB newsletter... well, similar but different. I love it!

I've saved it to my hard drive and intend to play around with it a little. I also believe it will easily lend itself to multiple decks, two, three, four, and five if the user wants to go that far.

Thanks for contributing. smiley
User IP Logged

JB 1.01
Win7 64bit, 4 GB RAM, Pentium 6200@2.13 GHz (laptop)
WinXP, 1 GB RAM, Intel N270@1.6 GHz (netbook)
wayne
Full Member
ImageImageImageImage


member is offline

Avatar




PM

Gender: Male
Posts: 388
xx Re: SHUFFLING (Cards, Questions, Images)
« Reply #16 on: Sep 12th, 2015, 04:56am »

Shuffling cards is relatively easy.

After loading your array, just go through it and swap cards randomly.

Code:
For x = 1 to 52 ' go through the deck card by card

temp = card(x) ' load the card at the current position in the deck, so you don't lose it
position = int((rnd(1) * 52) + 1 ' pick a random position in the deck
card(x) = card(position) ' replace the card at the current position with the randomly selected one
card(position) = temp ' put the card you replaced back into the deck at the random position

next ' repeat until you run out of cards
 
« Last Edit: Sep 12th, 2015, 05:00am by wayne » User IP Logged

bplus
Senior Member
ImageImageImageImageImage


member is offline

Avatar




PM

Gender: Male
Posts: 1255
xx Re: SHUFFLING (Cards, Questions, Images)
« Reply #17 on: Sep 12th, 2015, 10:32am »

Why not just randomly draw from deck?
User IP Logged

B+
ezprogramming
Guest
xx Re: SHUFFLING (Cards, Questions, Images)
« Reply #18 on: Sep 12th, 2015, 11:14am »

on Sep 12th, 2015, 10:32am, bplus wrote:
Why not just randomly draw from deck?

There's a standard algorithm for shuffling: it's called the Knuth (or Fisher-Yates) shuffle and there are details here:

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

I would always advise using a standard algorithm rather than 'rolling your own' to ensure you don't accidentally introduce a statistical bias.
User IP Logged

wayne
Full Member
ImageImageImageImage


member is offline

Avatar




PM

Gender: Male
Posts: 388
xx Re: SHUFFLING (Cards, Questions, Images)
« Reply #19 on: Sep 12th, 2015, 11:56am »

From the linked article:

Quote:
To shuffle an array a of n elements (indices 0..n-1):
for i from n − 1 downto 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a(j) and a(i)


That's what mine does.
User IP Logged

Rod
Administrator
ImageImageImageImageImage


member is offline

Avatar

Graphics = Goosebumps!


PM

Gender: Male
Posts: 3151
xx Re: SHUFFLING (Cards, Questions, Images)
« Reply #20 on: Sep 12th, 2015, 1:08pm »

Yep, kcdan posted the routine a little earlier.
User IP Logged

ezprogramming
Guest
xx Re: SHUFFLING (Cards, Questions, Images)
« Reply #21 on: Sep 12th, 2015, 1:58pm »

on Sep 12th, 2015, 11:56am, wayne wrote:
That's what mine does.

Actually I don't think it does. The Wikipedia algorithm has:

Code:
 j ← random integer such that 0 ≤ j ≤ i 

whereas I think yours is equivalent to:

Code:
 j ← random integer such that 0 ≤ j ≤ n-1 

It's a subtle difference, but I wouldn't be at all surprised if it's an important one.
User IP Logged

bplus
Senior Member
ImageImageImageImageImage


member is offline

Avatar




PM

Gender: Male
Posts: 1255
xx Re: SHUFFLING (Cards, Questions, Images)
« Reply #22 on: Sep 12th, 2015, 4:02pm »

on Sep 12th, 2015, 11:14am, ezprogramming wrote:
There's a standard algorithm for shuffling: it's called the Knuth (or Fisher-Yates) shuffle and there are details here:

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

I would always advise using a standard algorithm rather than 'rolling your own' to ensure you don't accidentally introduce a statistical bias.


Yes, tried and true is safe.

Here is what I have been using, let me know if you think it is smokin' or needs to be incinerated.

Code:
'Dealcard test.txt for JB 2015-09-12 MGA/B+

again$=" "
while again$=" "
    dim DECK(52)
    count=0
    for i=1 to 55
        x=Dealcard()
        print x;" ";
        count=count+1
        if count mod 13=0 then print
    next
    print
    input "Enter spacebar to see another sample.";again$
wend

function Dealcard()
   'returns number 1 - 52 of card not dealt out from DECK array DIM in main code
   'returns 0 if DECK is empty
    CARDX=int(52*rnd(1))+1
    if DECK(CARDX)=1 then 'card already drawn deal with it!
        LIMIT=0    'in case calling program tries to overdraw from deck
        DIRECTION=rnd(1) 'flip coin heads we go up, tails down for next card available
        if DIRECTION<.5 then DIRECTION=-1 else DIRECTION=1
        while DECK(CARDX)=1
            CARDX=CARDX+DIRECTION
            if CARDX>52 then CARDX=1
            if CARDX<1 then CARDX=52
            LIMIT=LIMIT +1
            if LIMIT=53 then exit while 'deck empty
        wend
    end if
    if LIMIT>52 then
        Dealcard=0
    else
        DECK(CARDX)=1
        Dealcard=CARDX
    end if
end function
 


Similar code has been posted at another forum, no criticism so far.
User IP Logged

B+
tsh73
JB-Supporter


member is offline

Avatar




PM

Gender: Male
Posts: 3636
xx Re: SHUFFLING (Cards, Questions, Images)
« Reply #23 on: Sep 13th, 2015, 03:09am »

Quote:
It's a subtle difference, but I wouldn't be at all surprised if it's an important one.

Damn I never thought it could be *that* important!
I really should store that snippet somewhere.
See for 4 cards, set "wiki=1" on or off (comment out)
Code:
n=4
randomize .5

wiki = 1
if wiki = 1 then
    print "'modern shuffle by Wikipedia"
else
    print "'simple shuffle"
end if


dim a(n)
fact = 1
for i = 1 to n
    fact = fact*i
next
print fact
global nPerms

dim perm$(fact)

print "Filling permutations array"
res$=permutation$("", left$("0123", n))
list$=" "
for i = 1 to fact
    list$=list$;perm$(i);" ";using("##",i);" "
next
'print ">";list$;"<"

print "Experimenting..."
dim count(fact)

nn=10000
for k = 1 to nn

    'sinle shuffle
    for i = 0 to n-1
        a(i)=i
    next
'wiki = 1
if wiki = 1 then
    'modern shuffle by Wikipedia"
    for i = n-1 to 1 step -1
        j=int(rnd(0)*(i+1)) ' 0 <= j <= i
        tmp=a(i):a(i)=a(j):a(j)=tmp
    next
else
    'simple shuffle"
    for i = 1 to n-1
        j=int(rnd(0)*n) ' 0 <= j <= n-1
        tmp=a(i):a(i)=a(j):a(j)=tmp
    next

end if
    'wrap to single number
    p$=""
    for i=0 to n-1
        p$=p$;a(i)
    next
    pp=instr(list$, p$)
    num = val(mid$(list$, pp+5, 2))
    'print k, p$,
    'print ">";mid$(list$, pp+5, 2);"<"
    count(num)= count(num)+1
next

for i = 1 to fact
    print i, perm$(i), count(i), using("##.####",count(i)/nn*100)
next

Function permutation$(pre$, post$)
'Note the variable nPerms must first be stated as a global variable.
    lgth = Len(post$)
    If lgth < 2 Then
        nPerms = nPerms + 1
        perm$(nPerms) = pre$;post$
    Else
        For i = 1 To lgth
            tmp$=permutation$(pre$+Mid$(post$,i,1),Left$(post$,i-1)+Right$(post$,lgth-i))
        Next i
    End If
End Function
 

Code:
'modern shuffle by Wikipedia
24
Filling permutations array
Experimenting...
1             0123          443            4.4300
2             0132          386            3.8600
3             0213          417            4.1700
4             0231          417            4.1700
5             0312          422            4.2200
6             0321          428            4.2800
7             1023          396            3.9600
8             1032          391            3.9100
9             1203          379            3.7900
10            1230          441            4.4100
11            1302          426            4.2600
12            1320          415            4.1500
13            2013          438            4.3800
14            2031          411            4.1100
15            2103          419            4.1900
16            2130          407            4.0700
17            2301          428            4.2800
18            2310          466            4.6600
19            3012          411            4.1100
20            3021          386            3.8600
21            3102          396            3.9600
22            3120          428            4.2800
23            3201          436            4.3600
24            3210          413            4.1300
 

Code:
'simple shuffle
24
Filling permutations array
Experimenting...
1             0123          596            5.9600
2             0132          810            8.1000
3             0213          770            7.7000
4             0231          735            7.3500
5             0312          627            6.2700
6             0321          625            6.2500
7             1023          308            3.0800
8             1032          338            3.3800
9             1203          279            2.7900
10            1230          750            7.5000
11            1302          466            4.6600
12            1320          355            3.5500
13            2013          162            1.6200
14            2031          310            3.1000
15            2103          312            3.1200
16            2130          308            3.0800
17            2301          325            3.2500
18            2310          473            4.7300
19            3012          167            1.6700
20            3021          167            1.6700
21            3102          170            1.7000
22            3120          302            3.0200
23            3201          343            3.4300
24            3210          302            3.0200
 


Changing
Code:
'j=int(rnd(0)*(i+1)) ' 0 <= j <= i
 

to Code:
j=int(rnd(0)*n) ' 0 <= j <= n-1
 

in Wiki method makes is as bad as simple method :(

EDIT
actually it's covered in "Implementation errors" section in Wiki article :(
« Last Edit: Sep 13th, 2015, 03:15am by tsh73 » User IP Logged

Q: "And if I took your codes and compile them, and sell them for a profit"?
A: Go ahead. I had my share of good then I coded it for fun, if you can make better use of it - please do.
(enjoying JB 1.01 on WinXP, netbook and desktop)
tsh73
JB-Supporter


member is offline

Avatar




PM

Gender: Male
Posts: 3636
xx Re: SHUFFLING (Cards, Questions, Images)
« Reply #24 on: Sep 13th, 2015, 03:36am »

bPlus,
Quote:
Here is what I have been using, let me know if you think it is smokin' or needs to be incinerated.

I tried to incorporate your code in same test program
Code:
n=4
randomize .5

dim a(n)
fact = 1
for i = 1 to n
    fact = fact*i
next
print fact
global nPerms

dim perm$(fact)

print "Filling permutations array"
res$=permutation$("", left$("0123", n))
list$=" "
for i = 1 to fact
    list$=list$;perm$(i);" ";using("##",i);" "
next
'print ">";list$;"<"

print "Experimenting..."
dim count(fact)

nn=10000
for k = 1 to nn

    'sinle shuffle
    'bplus code
    dim DECK(n)
    for i=0 to n-1
        x=Dealcard()
        a(i)=x-1
    next

    'wrap to single number
    p$=""
    for i=0 to n-1
        p$=p$;a(i)
    next
    pp=instr(list$, p$)
    num = val(mid$(list$, pp+5, 2))
    'print k, p$,
    'print
    'print ">";mid$(list$, pp+5, 2);"<"
    count(num)= count(num)+1
next

for i = 1 to fact
    print i, perm$(i), count(i), using("##.####",count(i)/nn*100)
next

Function permutation$(pre$, post$)
'Note the variable nPerms must first be stated as a global variable.
    lgth = Len(post$)
    If lgth < 2 Then
        nPerms = nPerms + 1
        perm$(nPerms) = pre$;post$
    Else
        For i = 1 To lgth
            tmp$=permutation$(pre$+Mid$(post$,i,1),Left$(post$,i-1)+Right$(post$,lgth-i))
        Next i
    End If
End Function

function Dealcard()
   'returns number 1 - 52 of card not dealt out from DECK array DIM in main code
   'returns 0 if DECK is empty
    CARDX=int(4*rnd(1))+1
    if DECK(CARDX)=1 then 'card already drawn deal with it!
        LIMIT=0    'in case calling program tries to overdraw from deck
        DIRECTION=rnd(1) 'flip coin heads we go up, tails down for next card available
        if DIRECTION<.5 then DIRECTION=-1 else DIRECTION=1
        while DECK(CARDX)=1
            CARDX=CARDX+DIRECTION
            if CARDX>4 then CARDX=1
            if CARDX<1 then CARDX=4
            LIMIT=LIMIT +1
            if LIMIT=5 then exit while 'deck empty
        wend
    end if
    if LIMIT>4 then
        Dealcard=0
    else
        DECK(CARDX)=1
        Dealcard=CARDX
    end if
end function
 

Here's results for nn=100000 in LBB (just because it's faster)
yours
Code:
'simple shuffle
24
Filling permutations array
Experimenting...
1             0123          4693           4.6930
2             0132          4656           4.6560
3             0213          3068           3.0680
4             0231          3122           3.1220
5             0312          4756           4.7560
6             0321          4765           4.7650
7             1023          4747           4.7470
8             1032          4656           4.6560
9             1203          4610           4.6100
10            1230          4672           4.6720
11            1302          3208           3.2080
12            1320          3197           3.1970
13            2013          3069           3.0690
14            2031          3122           3.1220
15            2103          4696           4.6960
16            2130          4576           4.5760
17            2301          4659           4.6590
18            2310          4629           4.6290
19            3012          4755           4.7550
20            3021          4781           4.7810
21            3102          3222           3.2220
22            3120          3039           3.0390
23            3201          4681           4.6810
24            3210          4621           4.6210

 

Wikipedia
Code:
'modern shuffle by Wikipedia
24
Filling permutations array
Experimenting...
1             0123          4220           4.2200
2             0132          4183           4.1830
3             0213          4121           4.1210
4             0231          4134           4.1340
5             0312          4087           4.0870
6             0321          4134           4.1340
7             1023          4229           4.2290
8             1032          4217           4.2170
9             1203          4244           4.2440
10            1230          4124           4.1240
11            1302          4104           4.1040
12            1320          4115           4.1150
13            2013          4170           4.1700
14            2031          4162           4.1620
15            2103          4121           4.1210
16            2130          4141           4.1410
17            2301          4178           4.1780
18            2310          4192           4.1920
19            3012          4154           4.1540
20            3021          4271           4.2710
21            3102          4212           4.2120
22            3120          4211           4.2110
23            3201          4148           4.1480
24            3210          4128           4.1280

 

Now, either I broke your code - check it - or it's worse then Wikipedia shuffle.
« Last Edit: Sep 13th, 2015, 03:39am by tsh73 » User IP Logged

Q: "And if I took your codes and compile them, and sell them for a profit"?
A: Go ahead. I had my share of good then I coded it for fun, if you can make better use of it - please do.
(enjoying JB 1.01 on WinXP, netbook and desktop)
bplus
Senior Member
ImageImageImageImageImage


member is offline

Avatar




PM

Gender: Male
Posts: 1255
xx Re: SHUFFLING (Cards, Questions, Images)
« Reply #25 on: Sep 13th, 2015, 2:32pm »

Thank you tsh73,

for taking time and interest in my question. I had just cleared the decks, so to speak, to start investigating this issue in depth.

Just glancing at the results output, I assume the goal is to get flat 4.1... or 4.2... in the forth output column which I assume is, or represents, an even distribution of cards over very large sampling.

I haven't studied the testing code yet but I bet it will give me some idea of what will be expected from a proper test.

At moment I have one big (to me) question. Is the RANDOMIZE .5 necessary? The reason I ask is because I read Help file on RANDOMIZE and it said that that is used to get a specific set on random numbers over and over again. The same set of random numbers is not so random to me. I don't know anything about what requirements the statistical test requires but my intuition tells me this is not right random wise.


EDIT: BTW I wasn't going to mention this but speaking of:
Quote:
Here's results for nn=100000 in LBB (just because it's faster)
I tried LBB (not the latest version I don't think because a new version was announced at another forum right after I tried LBB to speed up ez's code for nth pi decimal and found it inaccurate for last digits in 10 digit request for n=20 along with reporting digits with E9.

I tried it, "just because it IS faster."

?

EDIT 2: I just checked dates. I posted my LBB snapshot 2015-09-10 and the LBB 3.02 announcement was 2015-09-11, random?

EDIT 3: Oh you changed the code for Dealcard function, yikes! No that won't work because LIMIT is based on DECK size and CARDX assignment is also based on DECK size.
« Last Edit: Sep 13th, 2015, 4:03pm by bplus » User IP Logged

B+
ezprogramming
Guest
xx Re: SHUFFLING (Cards, Questions, Images)
« Reply #26 on: Sep 13th, 2015, 5:19pm »

on Sep 13th, 2015, 2:32pm, bplus wrote:
I tried LBB to speed up ez's code for nth pi decimal and found it inaccurate for last digits in 10 digit request for n=20 along with reporting digits with E9.

Good catch (why didn't you report it to me at the time?). It's very easily fixed, change the output line as follows:

Code:
    PRINT "Decimal digits of PI at position "; D; ": "; STR$(INT(acc * 10^C)) 

LBB is in fact much more accurate than JB in this application and can reliably find more consecutive digits of PI - probably 14 or so rather than 10 - but displaying the output in 'E' notation clearly isn't helpful in this case.

Richard.
User IP Logged

bplus
Senior Member
ImageImageImageImageImage


member is offline

Avatar




PM

Gender: Male
Posts: 1255
xx Re: SHUFFLING (Cards, Questions, Images)
« Reply #27 on: Sep 13th, 2015, 6:33pm »

on Sep 13th, 2015, 5:19pm, ezprogramming wrote:
Good catch (why didn't you report it to me at the time?). It's very easily fixed, change the output line as follows:

Code:
    PRINT "Decimal digits of PI at position "; D; ": "; STR$(INT(acc * 10^C)) 

LBB is in fact much more accurate than JB in this application and can reliably find more consecutive digits of PI - probably 14 or so rather than 10 - but displaying the output in 'E' notation clearly isn't helpful in this case.

Richard.


Well that was ez!

Why didn't I report at time? I was going to post about it in that thread and decided to double check my facts right after I posted. I had forgotten, it was while using LBB that I encountered the E9, so when I checked with JB and it was correct, I was eager to "correct" my post. Later I did remember where the E9 code came from but by then I had changed the post a couple times... if anyone was paying attention they would wonder...

I hold you in highest respect, you are tried and true and really it is safe just to assume I am wrong and your code is correct and I am missing something. Of course, if I don't say anything, I don't learn anything, like that the fix was so ez!

Anyway, I am going back to researching a proper test of Dealcard function, it is getting interesting. Really it does not matter if it is incinerator material (well maybe a little), I just want to know why.
User IP Logged

B+
tsh73
JB-Supporter


member is offline

Avatar




PM

Gender: Male
Posts: 3636
xx Re: SHUFFLING (Cards, Questions, Images)
« Reply #28 on: Sep 14th, 2015, 01:11am »

Hello bplus,
Quote:
Is the RANDOMIZE .5 necessary? The reason I ask is because I read Help file on RANDOMIZE and it said that that is used to get a specific set on random numbers over and over again. The same set of random numbers is not so random to me. I don't know anything about what requirements the statistical test requires but my intuition tells me this is not right random wise.

Actually, that's leftover from debugging.
But it has it's purpose - if you run program as is, you'll get exactly same results as mine.
Quote:
Oh you changed the code for Dealcard function, yikes! No that won't work because LIMIT is based on DECK size and CARDX assignment is also based on DECK size.

Sure I did.
There 8*10^67 shuffles of 52 cards, and only 24 for 4 cards.
So I changed it to work for 4 cards.
52 to 4, 53 to 5.
Dit I broke it?
If not - is there reason it works bad for 4 cards but will work good for 52 cards?
User IP Logged

Q: "And if I took your codes and compile them, and sell them for a profit"?
A: Go ahead. I had my share of good then I coded it for fun, if you can make better use of it - please do.
(enjoying JB 1.01 on WinXP, netbook and desktop)
wayne
Full Member
ImageImageImageImage


member is offline

Avatar




PM

Gender: Male
Posts: 388
xx Re: SHUFFLING (Cards, Questions, Images)
« Reply #29 on: Sep 14th, 2015, 03:17am »

Quote:
To shuffle an array a of n elements (indices 0..n-1):
for i from n − 1 downto 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a(j) and a(i)


I'll admit that going from indices 0 to n-1 and then counting down from n-1 to 1 doesn't make sense to me. Seems like it could possibly leave the lowest card unmoved.
Also, the whole ≤ thing doesn't make much sense, either. I realize that it is there to force a card to be moved; it can't remain in its original position. But that defeats true randomness. To be truly random, the possibility has to exist that the deck could end up in its original configuration. The odds against that would be astronomically high, but it needs to be possible.
(Even with the ≤ bit, it is still possible for a later operation to put the card back to its original position - but only if it was placed lower in the deck.)

Mine goes through all 52 indices (well, it excludes the 53rd index, which is 0) and swaps them with randomly selected cards.
This means that the further you progress through the deck, the greater probability that you are swapping a card that has already been moved. As you pass the halfway-point, you are more likely to swap the card that has already been moved with another card that has already been moved. Sort of like a triple-shuffle.
Up to three shuffles in one pass! There's efficiency for you!
« Last Edit: Sep 14th, 2015, 03:27am by wayne » User IP Logged

Pages: 1 2 3  Notify Send Topic Print
« Previous Topic | Next Topic »

Conforums Terms of Service | Membership Rules | Home | Search | Recent Posts | Notification | Format Your Message | Installation FAQ

Donate $6.99 for 50,000 Ad-Free Pageviews!

| |

This forum powered for FREE by Conforums ©
Sign up for your own Free Message Board today!
Terms of Service | Privacy Policy | Conforums Support | Parental Controls