Algorithms for combinations of 5 numbers in 50

[Ribeiro Alvo]

Greetings everyone

I would like to know which, or which algorithms to generate 5 numbers in 50 without repetition (Euromillions Game).
I have my own, and I know some, mostly for spreadsheets.

[Stuart McLachlan]

I'd probably go with a Knuth shuffle. it''s been discussed in detail in various threads. here's one such (see Post #7):

https://forum.powerbasic.com/forum/u...umbers-or-text

[Ribeiro Alvo]

I'm talking about combinations (nCm) instead of permutations (nPm).

[David Roberts]

Hypergeometric distribution

[Ribeiro Alvo]

David

Thanks for the sugestion. But that's not quite what I'm talking about.
I further add that, my algorithm chooses the 5 numbers, always, in only 5 steps, without repetitions. That is, it does not require cycles to control repetitions.

[Stuart McLachlan]

I'm talking about combinations (nCm) instead of permutations (nPm).

Just do a Knuth shuffle on an array of the numbers 1-50 and take the first five. It's just like shuffling a deck of cards (essentially an array of 52 values ) and dealing the first five. Orstirring up fifty lottery balls and taking the first five that come up.

Exactly what you asked for "5 numbers in 50 without repetition (Euromillions Game)"

[Ribeiro Alvo]

Okay Stuart, but which, or which algorithms in PB, to do that ?

[Stuart McLachlan]

#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN () AS LONG
 ? RandomDRAW(5,50)
END FUNCTION

FUNCTION RandomDraw (Selections AS LONG, Outof AS LONG) AS STRING
DIM nums(1 TO OutOf) AS LONG
LOCAL i,j AS LONG
LOCAL strNumbers AS STRING

'Get numbers into array
FOR i= 1 TO Outof: nums(i) = i:NEXT

'Knuth shuffle array
RANDOMIZE TIMER
FOR i = 1 TO OutOf-1 : j = RND(i,Outof) : SWAP nums(i), nums(j) : NEXT i

'Get requested numbers
FOR i = 1 TO Selections
    strNumbers += STR$(nums(i)) & "  "
NEXT
FUNCTION = TRIM$(strNumbers)
END FUNCTION

[David Roberts]

Rnd is no good for 50 numbers and can only fully shuffle 12 numbers having only an internal state of 32 bits. For 50 numbers we need an internal state of just over 214 bits. Mersenne Twister will walk it.

[Stuart McLachlan]

I agree with David. From a link in the earlier quoted thread:

https://www.i-programmer.info/programming/theory/2744-how-not-to-shuffle-the-kunth-fisher-yates-algorithm.html

If you consider using a good algorithm like Knuth Fisher-Yates to shuffle a deck of 52 cards then in principle every arrangement of the deck, i.e. 52! sequences, should occur equally often - but wait! The random number generator is usually only based on 64-bit arithmetic which means it repeats at most after "only" 2⁶⁴, which means that it can't generate more than this number of unique sequences and as 2⁶⁴ << 52! this approach is doomed to fail.

That is, the Knuth Fisher-Yates shuffle will miss out a lot of arrangements of the deck and will not produce a casino quality shuffle because of the limitations of the random number generator in use.

One possible approach is to reseed the generator at each shuffle,

Whether that approach is valid with PB is moot. It depends on how Bob wrote the PRNG. If in fact it is an algorithm with just one "ring" of numbers with the seed just determining the entry point, that is true. If different seeds generate different "rings", then that approach may be valid.

[Mark Hunter]

PowerBasic code for Combinations

[Ribeiro Alvo]

Here is my own algorithm:

#COMPILE EXE
#DIM ALL

REM mCn By Ribeiro Alvo 2019
FUNCTION PBMAIN () AS LONG

 LOCAL i AS BYTE
 LOCAL j,m,n AS STRING
 m=CHR$(1 TO 50)
 RANDOMIZE TIMER

 FOR i=1 TO 5
  j=MID$(m,RND(1,51-i),1)
  m=STRDELETE$(m,ASC(j),1)
  n + = STR$(ASC(j)) & "  "
 NEXT

 ? n

END FUNCTION

[Stuart McLachlan]

Ribeiro, that's a neat solution to the question. Guess I was overthinking it

[Ribeiro Alvo]

Bug removed.

#COMPILE EXE
#DIM ALL

REM mCn By Ribeiro Alvo 2019
FUNCTION PBMAIN () AS LONG

 LOCAL i AS BYTE
 LOCAL j,m,n AS STRING
 m=CHR$(1 TO 50)
 RANDOMIZE TIMER

 FOR i=1 TO 5
  j=MID$(m,RND(1,51-i),1)
  m=LEFT$(m,INSTR(m,j)-1)+RIGHT$(m,51-i-(INSTR(m,j)))
  n + = STR$(ASC(j))
 NEXT

 ? n

END FUNCTION

[Stuart McLachlan]

I liked your use of STRDELETE$(). It's going to be more efficient than LEFT$,INSTR$,RIGHT$,INSTR$
You just need to store the random string position to re-use.

FUNCTION PBMAIN () AS LONG
    LOCAL i,r AS LONG
    LOCAL m,n AS STRING
    m=CHR$(1 TO 50)
    RANDOMIZE TIMER
    FOR i=1 TO 5
        r = RND(1,51-i)
        n += STR$(ASC(MID$(m,r,1)))
        m = STRDELETE$(m,r,1)
    NEXT
   ? n
END FUNCTION

[Ribeiro Alvo]

Stuart

I did some tests, and with the STRDELETE$ function, repetitions appear. Which should not happen.
That's why I made the new approach.
Also because the INSTR function is more transverse to BASIC.

[Stuart McLachlan]

Stuart

I did some tests, and with the STRDELETE$ function, repetitions appear. Which should not happen.
That's why I made the new approach.
Also because the INSTR function is more transverse to BASIC.

That's because you miss-used STRDELETE$()

STRDELETE$(m,ASC(j),1) frequently will not remove the desired character after the first iteration because (for example) CHR$(27) is not in position 27 any longer if any lower value has been removed. See my modification above.

[Kerry Farmer]

When I did this I found my random number in the 50 and then deleted it and found my next random number in the 49 and so on.

Well I can understand it and it works for me.

i had no special need to be fast

[Stuart McLachlan]

Incidentally, there are only 254,251,200 possible combinations so using RND in this situation is probably quite sufficient

[Stuart McLachlan]

When I did this I found my random number in the 50 and then deleted it and found my next random number in the 49 and so on.

Well I can understand it and it works for me.

i had no special need to be fast

That's what the code above does