Hi, gw-ga:
The 96 solutions you found agree with the ones my programs found.
My original program enforced a narrower range of solutions, namely
that not only is the lowest order bit set first, as in your solutions,
but in fact the order in which bits are first toggled agrees with the
order of the bit locations (1 bit first, 2 bit before 4 bit, 8 bit
last). With this restriction there are only 16 solutions. The 96
seen in your programs output correspond to the 3! = 6 times as many
solutions obtained by permuting the high order three bits (uniformly,
among all codes).
Here is a short Prolog program that can compute all 96 of the 4 bit
solutions:
distCodeBits(16,_,_,_,_,M,M) :- !.
distCodeBits(J,L0,L1,L2,L3,M,P) :-
not(L0 = [_,_,_,_|_]),
changeBit(1,M,N),
I is J + 1,
distCodeBits(I,[J|L0],L1,L2,L3,N,P).
distCodeBits(J,L0,L1,L2,L3,M,P) :-
not(L1 = [_,_,_,_|_]),
changeBit(2,M,N),
I is J + 1,
distCodeBits(I,L0,[J|L1],L2,L3,N,P).
distCodeBits(J,L0,L1,L2,L3,M,P) :-
not(L2 = [_,_,_,_|_]),
changeBit(4,M,N),
I is J + 1,
distCodeBits(I,L0,L1,[J|L2],L3,N,P).
distCodeBits(J,L0,L1,L2,L3,M,P) :-
not(L3 = [_,_,_,_|_]),
changeBit(8,M,N),
I is J + 1,
distCodeBits(I,L0,L1,L2,[J|L3],N,P).
changeBit(B,[H|T],[Hb,H|T]) :-
Hb is H xor B,
not(is_member(Hb,T)).
given the "goal" of satisfying:
distCodeBits(1,[0],[],[],[],[1],M).
The idea is that the first argument "counts" up to 16, and at each
step before the last, a new "bit change" is alotted to one of the four
bit positions. These allocations are "remembered" in the lists held
in the next four arguments, while the resulting codes are added
sequentially to the list in the next to last argument. When the final
count 16 is reached, the final argument gets bound to the same list
represented in the next to last argument, and we're done. Prolog has
a mechanism called "backtracking" which allows it to find all the
solutions with no additional programming.
My first program's approach to searching for solutions was an attempt
to cut down on the size of the search space by focusing on the limited
possibilities for the bits in the least significant position. It then
proceeded basically to determine all the bits in the 2's position, the
4's position, the 8's position.
However when I began to think about scaling up to the 8 bit case, the
number of possibilities for all bits in the least significant position
expands by roughly nine orders of magnitude, from 25 possibilities in
the 4 bit case (for just the first bits!) to what I suspect turns out
to be:
121 * 121 * 61 * 61 * 21 * 21 = 24,025,310,001
possibilities for the first column of bits.
Cutting down the total size of the search space is not necessarily the
immediate concern in trying to find solutions quickly. More important
is usually the introduction of constraint checks early in the search
which tend to knock out large swaths of "search space" that would
eventually turn out to be untenable.
In this respect I found, after exercising "ingenuity" in the first
version of my program, that there was a natural advantage to the
structure of a "brute force" program, partly realized in the version
shown above, in being able to do those "knockout" checks earlier on in
the search.
The "ingenuity" of my first approach finds its way into the framework
of the "brute force" approach in what I hope will turn out to be a
nice way to tackle the 8 bit approach. I'll post an update this
weekend when I get some computational results.
regards, mathtalk-ga |
,
0 Comments
)