Re: Card Sets

[SMcNeill]

Give this a test run, and you can see what the problem is:

Code: [Select]

RANDOMIZE TIMER
DIM SHARED numCards AS INTEGER
numCards = 52

DIM SHARED maxSets AS LONG
maxSets = 80000

DIM SHARED Ruscell(maxSets) AS STRING

DIM SHARED Code AS STRING
FOR a = 97 TO 122: Code = Code + CHR$(a): NEXT
FOR a = 65 TO 90: Code = Code + CHR$(a): NEXT

DIM t AS LONG
DIM p AS SINGLE
DIM total AS LONG

DIM test AS STRING
DIM Cardset AS STRING

Ruscell(1) = newSet
total = 2

LOCATE 24, 2: PRINT "Loading....";

DO
    Cardset = newSet
    LOCATE 1, 1: PRINT Cardset
    test = "Good"
    FOR t = 1 TO total - 1
        IF Cardset = Ruscell(t) THEN
            test = "Bad"
            PRINT total, t, "MATCH"
            SLEEP
            EXIT FOR
        END IF
    NEXT

    IF test = "Good" THEN
        Ruscell(total) = Cardset
        total = total + 1
    END IF

    p = (100 * total) / maxSets
    COLOR _RGB(218, 165, 32)
    LOCATE 24, 38: PRINT USING "###%"; p;

    COLOR _RGB(192, 192, 192)
    LOCATE 24, 74: PRINT USING "##,###"; total;

    p = (80 * total) / maxSets
    COLOR _RGB(218, 165, 32)
    LOCATE 25, 1: PRINT STRING$(p, 219);
LOOP UNTIL total = maxSets
END

FUNCTION newSet$
    DIM temp AS STRING
    DIM Cards AS STRING

    card = 1
    WHILE card <> numCards + 1
        tag = INT(numCards * RND) + 1
        temp = MID$(Code, tag, 1)

        IF INSTR(Cards, temp) = 0 THEN
            Cards = Cards + temp
            card = card + 1
        END IF
    WEND

    newSet = Cards
END FUNCTION

For you first 71,142 sets, you don't generate any duplicate values.  At set number 71,143, you simply get repeat cycles and generate the same lists endlessly over and over...

Remember, RND only generates a pseudo-random set of numbers for us, based off a formula, and it repeats itself in a cyclic pattern.  That's what you're seeing here.  What you need is a different method to shuffle the card pattern, without repeating the same sets over time.  I'll play around and see what I can come up with to see if I can work around the issue.  :)

[bplus]

How many character (cards?) in a set?

If 52, then you are counting permutations = 52! different orderings of 52 different characters.

If counting how many "hands" of 5 characters, it is 52! / (5! * 47!) = 52 * 51 * 50 * 49 * 48 / 120 = 122,151,120


It is interesting to learn that RND is "exhausted" with 71+ K numbers. Something to keep in mind.

[bplus]

Code: QB64: [Select]

1. DIM r(10 ^ 5 + 1), idx AS _INTEGER64
2. FOR i = 0 TO 10 ^ 5
3.     IF i MOD 1000 = 0 THEN LOCATE 1, 1: PRINT i
4.     x = RND
5.     found = 0
6.     FOR j = 0 TO idx
7.         IF x = r(j) THEN found = -1: EXIT FOR
8.     NEXT
9.     IF found = 0 THEN idx = idx + 1: r(idx) = x
10. NEXT
11. PRINT idx
12. FOR i = 1 TO 50
13.     PRINT r(i),
14. NEXT

Well I am not getting any repeats in 100,000 calls to RND so I might be misunderstanding the repeating of results interpretation by Steve.

[SMcNeill]

Well I am not getting any repeats in 100,000 calls to RND so I might be misunderstanding the repeating of results interpretation by Steve.

It's repeating, but there's a lot more than 71,142 calls to RND happening before it repeats.

WHILE card <> numCards + 1
  tag = INT(numCards * RND) + 1
  temp = MID$(Code, tag, 1)
 
  IF INSTR(Cards, temp) = 0 THEN
    Cards = Cards + temp
    card = card + 1
  END IF
WEND

Notice the loop here.  We get a random number from 1 to 52, and assign that letter to our string -- as long as we haven't used it already.

To highlight how many times we're actually calling RND, before it repeats, try this code:

Code: [Select]

DIM SHARED numCards AS INTEGER
numCards = 52

DIM SHARED maxSets AS LONG
maxSets = 71142

DIM SHARED Ruscell(maxSets) AS STRING

DIM SHARED Code AS STRING
FOR a = 97 TO 122: Code = Code + CHR$(a): NEXT
FOR a = 65 TO 90: Code = Code + CHR$(a): NEXT

DIM t AS LONG
DIM p AS SINGLE
DIM total AS LONG

DIM test AS STRING
DIM Cardset AS STRING

Ruscell(1) = newSet
total = 2

LOCATE 24, 2: PRINT "Loading....";

DO
    Cardset = newSet

    test = "Good"
    FOR t = 1 TO total - 1
        IF Cardset = Ruscell(t) THEN test = "Bad"
    NEXT

    IF test = "Good" THEN
        Ruscell(total) = Cardset
        total = total + 1
    END IF

    p = (100 * total) / maxSets
    COLOR _RGB(218, 165, 32)
    LOCATE 24, 38: PRINT USING "###%"; p;

    COLOR _RGB(192, 192, 192)
    LOCATE 24, 74: PRINT USING "##,###"; total;

    p = (80 * total) / maxSets
    COLOR _RGB(218, 165, 32)
    LOCATE 25, 1: PRINT STRING$(p, 219);
LOOP UNTIL total = maxSets
END

FUNCTION newSet$
    DIM temp AS STRING
    DIM Cards AS STRING
    STATIC TOTAL AS _INTEGER64
    card = 1
    WHILE card <> numCards + 1
        tag = INT(numCards * RND) + 1
        temp = MID$(Code, tag, 1)
        TOTAL = TOTAL + 1
        IF INSTR(Cards, temp) = 0 THEN
            Cards = Cards + temp
            card = card + 1
        END IF
    WEND
    LOCATE 3, 1: PRINT TOTAL
    newSet = Cards
END FUNCTION

16,777,445...   more than 2^24 (which is 16,777,216), which shows where we've ran out of numbers in our RND "list" and have started to repeat them once again.

[bplus]

Hi Steve,

So [banned user] IS trying to generate and count unique random permutations of a deck, yikes! 52! of them!

And RND does repeat but only after 2^24 calls PLUS 200 +- ???

I don't see how more than 2^24 values can come out of RND given the formula/code you've shown (in QB64 code).
But it is reassuring that it wasn't limited to 71+ K.

[banned user] could put 52 numbers in a deck, shuffle the deck, and then draw out 52 by index to form a new number, test it with past numbers for uniqueness. That would save all that time randomly checking if he used the number yet from his deck. I would use a permutation generator like we did with that Lotto Game but not on 52! :)