I have a problem that I have been trying to figure out by hand (for some
time now). I may just simply not know the right logic with which to
approach it, or it may be something best suited for a computer to
iterate through the possibilities to find the best solutions. If
computer iteration is the best approach, I would like to do it in Perl.
(I won't have access to my Perl books for a while though, so I'm
having to do the best I can without them.)
The data set has 41 units consisting of "A", "B", and "C":
("A" and "C" can *not* be beside each other within a unit.)
AAAA AAAB AABA AABB AABC ABAA ABAB ABBA ABBB ABBC ABCB ABCC
BAAA BAAB BABA BABB BABC
BBAA BBAB BBBA BBBB BBBC BBCB BBCC BCBA BCBB BCBC BCCB BCCC
CBAA CBAB CBBA CBBB CBBC CBCB CBCC CCBA CCBB CCBC CCCB CCCC
These units should be coupled into pairs that have only one step
difference between them, like so:
AAAA or ABAA
BAAA BBAA
Each pair must progress only one step ("A" to "B", "B" to "C") into the
next pair:
(Regression ("C" toward "A") is not permitted.)
AAAA -> AAAB
BAAA -> BAAB
The progression must not cause one partner to transform into its mate (a
waste of time which can be avoided):
ABAA -X-> BBAA
BBAA ---> CBAA
Sometimes, skipping a step is necessary. Skipping from "A" to "C" takes
no more time than changing from "A" to "B". But each change requires
setup time. A pair does *not* automatically change together. Each unit
in the pair requires its own setup time. And each new pair requires
time for testing.
Skipping from "A" to "C" is permitted only when normal progression
cannot proceed. The skip can only happen to one unit in the pair
(wastes time but unavoidably):
AAAA AAAB ABAB ABBB ABCB ABCC CBCC CCCC 60 members
BAAA BAAB BBAB BBBB BBCB BBCC BCCC 61 members
121 members
In this case, BBCC stayed the same when ABCC changed to CBCC.
Each unit represents its own varying subset of members.
members in units
16 AAAA BBBB
12 AAAB AABB ABBB BAAA BBAA BBBA
10 AABA ABAA BABB BBAB
9 ABBA BAAB
8 ABAB BABA BBBC BBCB BCBB CBBB
6 AABC ABBC ABCB BCBA CBBA CBAA
5 BABC CBAB
4 BBCC BCCB CCBB CBCB CBBC BCBC
3 ABCC CCBA
2 BCCC CBCC CCBC CCCB
1 CCCC
295 Total
There are two goals which may have to have some sort of trade off. The
first goal wants to pack the most *members* into the first progression
(and subsequently the ones that follow). The second goal seeks the
fewest series of progressions. The first goal serves to preserve time
*and* resources whereas the second just the latter.
There *are* some obvious limitations:
(In terms of "changes", AAAA has 0 whereas CCCC has 8.)
0 1 2 3 4 5 6 7 8
AAAA AAAB AABB ABBB BBBB BBBC BBCC BCCC CCCC
AABA ABAB BABB ABBC BBCB BCBC CBCC
ABAA BAAB BBAB ABCB BCBB CBBC CCBC
BAAA ABBA BBBA BCBA CBBB BCCB CCCB
BABA AABC CBBA ABCC CBCB
BBAA CBAA BABC CCBA CCBB
CBAB
AABC can be preceeded *only* by AABB (or be the first in one series of
progressions). Likewise, CBAA can be preceeded *only* by BBAA. At
first, each of the following limits exist:
AABB -> AABC because AABC has no other single step precedent
BBAA -> CBAA (same reason)
ABBB -> ABCB (same reason)
BBBA -> BCBA (same reason)
BABC -> BBBC because BABC can proceed to no other
CBAB -> CBBB (same reason)
ABCC -> BBCC (same reason)
CCBA -> CCBB (same reason)
After those limitations are taken into account, these limitations pop up:
AABC -> ABBC because AABC and ABBC each have no other mate
CBAA -> CBBA (same reason)
These limitations exist even *before* removing any units from the pool.
The final 2 or 3 series of progressions may have only one unit each
(without a mate), wasting resources.
The problem is not as simple as it may first appear. Each time one unit
moves from the pool to a progression series, the limitations increase on
those remaining in the pool. Each time the limitations increase, the
goals become harder to achieve.
And on top of all that, sometimes the first letter is *not* permitted to
be "A". Sometimes it is *not* permitted to be "C". And in two other
cases, even though "A" or "B" is the first letter, the members of each
unit are reduced for another reason (not so easy to explain). And these
four cases each require a different set of progression series as each
one alters the distribution of the number of members (affecting the
success of the goals).
Is the easiest solution achievable only by a computer iterating through
the possibilities? At the moment, I cannot even conceive how to proceed
programming such a beast. Then again, I am still quite the novice in
Perl. I might be able to pull it off in BASIC. But even there, I don't
know how to begin. (Besides, I currently don't even have access to BASIC.)
(Often, just *trying* to explain a problem to someone else brings the
problem *and* its solution sharply into focus. I was hoping for that
effect on this one, but to no avail. It seems that I've already brought
the problem itself into sharp focus long ago. Putting it into words,
for the most part, came swiftly and easily.)
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
