Announcement

Collapse
No announcement yet.

Algorithms for combinations of 5 numbers in 50

Collapse
X
  • Filter
  • Time
  • Show
Clear All
new posts

  • Algorithms for combinations of 5 numbers in 50

    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.

  • #2
    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

    Comment


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

      Comment


      • #4
        Hypergeometric distribution

        Comment


        • #5
          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.

          Comment


          • #6
            Originally posted by Ribeiro Alvo View Post
            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)"

            Comment


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

              Comment


              • #8
                Code:
                #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

                Comment


                • #9
                  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.

                  Comment


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

                    https://www.i-programmer.info/progra...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" 264, which means that it can't generate more than this number of unique sequences and as 264 << 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.

                    Comment


                    • #11
                      PowerBasic code for Combinations
                      Politically incorrect signatures about immigration patriots are forbidden. Googling “immigration patriots” is forbidden. Thinking about Googling ... well, don’t even think about it.

                      Comment


                      • #12
                        Here is my own algorithm:

                        Code:
                        #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
                        Last edited by Ribeiro Alvo; 16 Mar 2019, 11:39 PM. Reason: Optimization

                        Comment


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

                          Comment


                          • #14
                            Bug removed.

                            Code:
                            #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
                            Last edited by Ribeiro Alvo; 17 Mar 2019, 05:40 AM. Reason: Small correction

                            Comment


                            • #15
                              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.

                              Code:
                              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

                              Comment


                              • #16
                                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.

                                Comment


                                • #17
                                  Originally posted by Ribeiro Alvo View Post
                                  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.

                                  Comment


                                  • #18
                                    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

                                    [I]I made a coding error once - but fortunately I fixed it before anyone noticed[/I]
                                    Kerry Farmer

                                    Comment


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

                                      Comment


                                      • #20
                                        Originally posted by Kerry Farmer View Post
                                        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

                                        Comment

                                        Working...
                                        X