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
This program will generate "Magic Sequences". .A
Magic Sequence of length N has the property that each value in the series
represents the number of times that its rank (position number) relative to
zero, appears in the sequence. If the elements are represented by Xi, 0<=i<=N-1
then Xi = the number of occurrences of "i" in the sequence.
So for sequences of length 5, one (and only) example is [2,1,2,0,0], magic because x0
= 2 and there are 2 zeroes in the sequence; X1=1 and there is only a
single 1 in the sequence; x2=2 and there are two "2"s, X3=X4=0 and
there are no "3"s or "4"s.
Background & Techniques
A viewer wrote recently asking about a program to generate "Magic
Sequences".
He included code that calculated the sequence of length 7 by nesting loops 7
levels deep, each level generating a digit position. Clearly he felt
that there must be a better. Probably so.
There does not seem to be much literature on sequences with this property
and they appear to degenerate into a predictable pattern rather soon so are
perhaps not so interesting from a mathematical standpoint but did make a
good programming exercise.
I generalized the code to produce three additional ways to calculate
sequences for a given N. Each method is faster than the preceding version.
Method 1 simply counts in base N and checks each to see if it is
"magic". [00001, 00002, 00003, 00004, 00010 ,..., 21200, ..., 44444,
44445] for N=5, for example.
The next two methods take advantage of the fact that the sum of the non-zero
elements of a sequence form an partition of N. (Each value in the sequence
represents the count of a particular value and there are N of these values
altogether, so the sum must equal N.) So we might as well start with the
integer partitions of N.
Method 2 generates integer partitions of N, checks that one of the
values
equals the number of zeros in the sequence and then expands the
sequence with zeros and permutes the last N-1 digits looking for magic
sequences. For N=7, the partition {1,1,2,3} is a potential solution since it
contains 4 numbers so there must be 3 zeros in the sequence and we have a 3
in the partition that can occupy the 1st position. Method
2 then permutes the remaining 6 sequence members, {1,1,2,0,0,0}, checking
for than would complete a valid magic sequence. This requires
checking 6!=720 possibilities.
Method 3 improves on Method 2 by permuting the potential position where
the digits of each partition might appear in the sequence. so in the
N=7 case, we only check the number of places
that {2,1,1} can be inserted into the last 6 positions. This requires
that only (6!/3!)=6*5*4=120 patterns be checked.
Notes for programmers
 | From the programming perspective, our TIntPartition class in unit
UIntPartition2 and TComboset class in the UComboV2
library unit makes generating the partitions and permutations quite easy.
Each of these units initializes a default instance of the class (DefPartition
for TIntpartition and Combos for TComboSet) which avoids
creating our own. |
| There is a commented version of a procedure for Method 1
(Button1Click) which works
as literally described above, counting in base N. The
equivalent, but faster, procedure actually used is a version of the TComboset
NextLexRepRPermute function which generates permutations
with repeats. For permuting N of N items, this is equivalent to
counting in Base N. |
| Run times for each method are displayed, making the it easy to
determine the effect of changes on speed. |
Running/Exploring the Program
Suggestions for Further Explorations
Other enhancements to increase speed?
For the math types, it appears that for N>6, there
is only a single sequence with four non-zero members and they are: X0=N-4,
X1=2, X2=1 and XN-4=1. How
about proving this?
|
Original Date: May 1, 2007 |
Modified:
May 11, 2018 |
|
|
