FullArrayIndexSet

By Xah Lee. Date:

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)

2005-09

If you have a question, put $5 at patreon and message me.