Search

 
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 X_{i}, 0<=i<=N1
then X_{i} = 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 x_{0}
= 2 and there are 2 zeroes in the sequence; X_{1}=1 and there is only a
single 1 in the sequence; x_{2}=2 and there are two "2"s, X_{3}=X_{4}=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 nonzero
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 N1 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 nonzero members and they are: X_{0}=N4,
X_{1}=2, X_{2}=1 and X_{N4}=1. How
about proving this?
Original Date: May 1, 2007 
Modified:
July 29, 2017 

