Selection with Replacement

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. 

     

We receive a few cents from each purchase.  Thanks

 


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa® Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa® 365 Puzzlers  Calendar 2017

Mensa® 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

Problem Description

Here is a program that extends the ideas of Permutes 2 to selection with replacement.  We use the analogy of selecting balls from a bag.  Users define the number of balls in the bag, the number to select, and the labels on the balls.   Balls may be selected with or without replacement of each ball drawn before the next is drawn, and whether or not the order in which the balls are selected is important.   If the balls are labeled with numbers, the program will select single random samples or all possible samples which sum to a given number;  

Background & Techniques

Let's we examine the various ways to select balls.  Thee are two decisions to be made:

  1. Do we replace the ball after each draw or not.?
  2. Are the drawn balls to be considered as a sequence or a subset? (Note that with replacement, we'll have to just keep a record rather than the actual balls drawn since the same ball may "appear" several times in the a single sequence or subset.)

Most probability studies require knowledge of the total number of possible outcomes from  trials.   The total number of outcomes for the four combinations of the "replace-no replace", "sequence (order)-subset (no order)" decisions  is shown in the following table.

Select R from N Order is significant         (sequences) Order is not significant   (subsets)
Without replacement

1.

    N!    

(N-R)!

2.

        N!         

(N-R)! x R!

With replacement

3.

NR

4.

    (N+R-1)!    

(N-1)! x R!

Number of Outcomes selecting R form N

Notes:

  1.  If we select  R balls from N without replacing the ball after each draw and order is significant then we have N choices for the first ball, N-1 choices for the second, N-2 for the third, etc.  down to N-(R-1).  The product of all of these can be written  as N! / (N-R)! . This is the number permutations of N object taken R at a time.  (X!, called X factorial  is shorthand notation for the product of all integers from 1 to X.)
  2. If selecting without replacement and order is not significant then we are looking for the number of subsets of N things takes R at a time.  This is the number of combinations and reduces the number of permutations by a factor of R!  (For example if selecting 3 items, each XYZ set will appear 3! or 6 times [XYZ, XZY, YXZ, YZX, ZXY, and ZYX] which will reduce to a single outcome in the combinations case.  So we reduce the number of permutations by a factor of R! ( by dividing by R!) and the formula is N! /  ((N-R)! x R!)

  3. When we allow replacement, and order is significant, then we have N choices for each of the R selections or NR arrangements altogether. 

  4. The last possibility, ball replacement and order not significant is interesting.  If we denote this count as C(N,R) then the count can be defined recursively as 
    bullet

    C(1,X)=1

    bullet

    C(X,1)=1 for X>1

    bullet

    C(X,Y)=C(X-1,Y)+C(X,Y-1) for X>1, Y>1

    This number also turns out to be the number of combinations of N+R-1 things taken R at a time!   That's the formula displayed in the table above.  Why this is true is a puzzlement to me. 

Programmer's notes

Last July, viewer Peter presented the problem  of drawing sets of numbered balls from a bag which summed to a predetermined sum.  Recently a viewer raised the question again and even added a GetNextComboWithRep  procedure to our TCombosSet class in the Combo.pas unit.    That prompted me to finish the job by adding GetNextPermutationWithRep procedure and updating the GetCount function to return the NumberofSubsets field with total subset counts for each type.

 NumberOfSubsets is calculated in TComboset by the Setup  procedure and returned by the GetCount function.  The formulas listed in the table above are used to compute the values.

Running/Exploring the Program 

bulletDownload source
bulletDownload  executable

Suggestions for Further Explorations

Random samples displayed when "numeric balls sum to a value " are  drawn from the first 100,000 samples.   For some options, there may be 10 billion outcomes to check, clearly impractical.  Any way to make a truly random sample without enumerating all possibilities?  

Original Date: October 5, 2004 

Modified: May 15, 2018

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright © 2000-2018, Gary Darby    All rights reserved.