[MacPerl] prograMing: CompleteIndexSet

[Xah Lee <xah@best.com>]

I have a every interesting
academic-type programing problem involving array generation, and am
interested to see creative results.

Here's the problem:

Write the function CompleteIndexSet.

CompleteIndexSet([index1, index2,...]) returns a modified version of
input in which indexes that can be inferred from other indexes are
deleted. Indexes are of the form [n1,n2,n3,...] where the n are
non-negative integers. The result should be sorted by indexes'
length. If tied, then the entries in the indexs. The result should not 
contain duplicates.

Definition:
Suppose indexA = {'begin...', n, m != 0} where 'begin...' stands for
its beginning sequence. indexA implies any sequence {'begin...', n, x
< m}. Suppose indexB = {'begin...', n, 0}, then indexB implies
{'begin...', n}.

Here's one sample algorithm: Suppose one of the given index is
{a,b,c,d}. If the last digit is not 0, then generate {a,b,c,d-1}. If
the last digit is 0, then generate {a,b,c}. Add the new element into a 
result list. Now take new element as input and repeat the process
until it becomes {}. Now do the above with every given index. Now
eliminate duplicates and {} in the result list. The result is as
desired.

Here are some sample inputs and outputs. (from Mathematica)

In[86]:=
CompleteIndexSet[{{3}}]

Out[86]=
{{},{0},{1},{2},{3}}

In[87]:=
CompleteIndexSet[{{3},{3}}]

Out[87]=
{{},{0},{1},{2},{3}}

In[88]:=
CompleteIndexSet[{{3,2}}]

Out[88]=
{{},{0},{1},{2},{3},{3,0},{3,1},{3,2}}

In[89]:=
CompleteIndexSet[{{3,2,0}}]

Out[89]=
{{},{0},{1},{2},{3},{3,0},{3,1},{3,2},{3,2,0}}

In[90]:=
CompleteIndexSet[{{3,0,1}}]

Out[90]=
{{},{0},{1},{2},{3},{3,0},{3,0,0},{3,0,1}}

In[91]:=
CompleteIndexSet[{{0,0,3}}]

Out[91]=
{{},{0},{0,0},{0,0,0},{0,0,1},{0,0,2},{0,0,3}}

In[92]:=
CompleteIndexSet[{{3,2},{1,1}}]

Out[92]=
{{},{0},{1},{2},{3},{1,0},{1,1},{3,0},{3,1},{3,2}}

In[93]:=
CompleteIndexSet[{{3,2},{1,1},{5}}]

Out[93]=
{{},{0},{1},{2},{3},{4},{5},{1,0},{1,1},{3,0},{3,1},{3,2}}

(The empty braces represent the root node. We can ignore it in
Perl. Of course, the result in perl's CompleteIndexSet should be of
the form [[a1,a2,...],[b1,b2,...],...].)

---

I'm mostly interested in code quality with respect to time and space
complexity. If you think about it, it is not trivial to avoid
accumulating indexes already generated. An input like

CompleteIndexSet([100,100,100],[100,100,100],[100,100,100]) will send
a dump algorithm to space limits. There should be no assumption on
input, except they are syntactically correct. (we need not do error
checking.)

I'll come up and post a solution of my own this weekend, and hope
 to compare notes with your code.

Enjoy!

 Xah, xah@best.com
 http://www.best.com/~xah/PageTwo_dir/more.html
 >They fight! They bite! They fight and bite and fight!
 >Fight fight fight! Bite bite bite!
 >The Itchy and Scratchy Show!

PS
Here's the Mathematica code that generated the samples.

CompleteIndexSet[indexes_List]:=
  Union[Flatten[
      Map[(FixedPointList[
              Replace[#,{frest___,x_}:>If[x=!=0,{frest,x-1},{frest}]]&,#]&),
        indexes],1]]


***** Want to unsubscribe from this list?
***** Send mail with body "unsubscribe" to mac-perl-request@iis.ee.ethz.ch