prograMing: tree and indexes
- To: mathgroup@smc.vnet.net
- Subject: [mg10851] prograMing: tree and indexes
- From: "Xah" <xah@best.com>
- Date: Wed, 11 Feb 1998 18:32:24 -0500
- Organization: Venus & Xah Love Factory
Here's another tree related recreational prograMing problem. In this
message, a solution to a given problem is given. Reader is asked to
supply alternative approches.
The problem:
Write a function FullArrayIndexSet such that
FullArrayIndexSet[{i1,i2,...},(Heads->False)] returns a complete index
set for an array of given dimensions {i1,i2,...}. The option
Heads->True will consider Heads as parts of the array (and generate
their indexes).
Description:
Suppose {a,b,c} is the given index, and we have Heads->True. We want to
generate all the following: {0,0,0}<=({i},{i,j},{i,j,k})<={a,b,c}.
For example, FullArrayIndexSet[{2,2,2},Heads->True] should return
{{0},{1},{2},{0,0},{0,1},{0,2},{1,0},{1,1},{1,2},{2,0},{2,1},{2,2},{0,0,0},{
0,
0,1},{0,0,2},{0,1,0},{0,1,1},{0,1,2},{0,2,0},{0,2,1},{0,2,2},{1,0,0},{1,0,
1},{1,0,2},{1,1,0},{1,1,1},{1,1,2},{1,2,0},{1,2,1},{1,2,2},{2,0,0},{2,0,
1},{2,0,2},{2,1,0},{2,1,1},{2,1,2},{2,2,0},{2,2,1},{2,2,2}}
(not necessarily in that order, but let's suppose this is the order we
want.)
The result of FullArrayIndexSet[indexes,Heads->False] can be specified
neatly in terms of FullArrayIndexSet[indexes,Heads->True] by the
definition: FullArrayIndexSet[indexes_List,
Heads->False]:=(DeleteCases[#,{___,0,__},{1,-1}]&)@
FullArrayIndexSet[indexes,Heads->True];
One Solution:
Clear[FullArrayIndexSet];
FullArrayIndexSet::"usage"=
"FullArrayIndexSet[{i1,i2,...},(Heads->False)] returns a complete
index set \
for an array of given dimensions {i1,i2,...}. The option Heads->True
will \ consider Heads as parts of the array (and generate their
indexes). Example: \
FullArrayIndexSet[{2,3},Heads->False]";
Options[FullArrayIndexSet]={Heads->False};
FullArrayIndexSet[indexes_List]:=FullArrayIndexSet[indexes,Heads->False];
FullArrayIndexSet[indexes_List,Heads->True]:=
Composition[Union,FixedPoint[DeleteCases[#,{},{1,-1}]&,#]&,
Flatten[#,Length@indexes-1]&]@
Outer[List,Sequence@@(Append[Range[0,#],{}]&/@indexes),
Sequence@@Table[1,{Length@indexes}]];
FullArrayIndexSet[indexes_List,
Heads->False]:=(DeleteCases[#,{___,0,__},{1,-1}]&)@
FullArrayIndexSet[indexes,Heads->True];
This is a clever but not exemplary solution. A more clear coding that
shows the underlying algorithm is desired. An exemplary coding should
build up the list cleanly. Build-in function like Array or MapIndexed
should not be used because they averts the programing challenge at
heart. (The use of Outer as in the above solution is also hackish as
you might have suspected.)
For the case of Heads->False, it would also be interesting to see a
function that generate the list cleanly. (instead of deleting parts
afterwards)
Mathematica gurus: join in!
Xah, xah@best.com
http://www.best.com/~xah/Wallpaper_dir/c0_WallPaper.html
"When an orginazation becomes large and powerful, individuals must
exercise distrust. e.g. Don't trust government."