Search
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).
|
| |
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:
- Do we replace the ball after each draw or not.?
- 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:
- 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.)
-
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!)
-
When we allow replacement, and order is
significant, then we have N choices for each of the R
selections or NR arrangements altogether.
-
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
 |
C(1,X)=1 |
|
C(X,1)=1 for X>1 |
|
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
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
|
|
|
