An algorithm to compute all full-span sub arrays of a regular array

ABSTRACT

We present an algorithm that explicitly generates all full-span regular sub arrays of a given N dimensional regular array. By explicit, we mean that we generate the N-dimensional indexes of the j-dimensional sub array cells that make up each j-dimensional sub array. The algorithm can be viewed as generating all j-dimensional full span sub arrays for fixed j, for j = 0 to j = N. We first list some lemmas and definitions, and then give the algorithm that is based upon the knowledge gained from a new expansion [1] and [2]. There is an alternate combinatorial argument yielding the same algorithm.First we give an heuristic summary and then a more detailed example use. In the algorithm, we use APL-C-Java order in the indexes, i.e., right-to-left (RTL). However, essentially the same algorithm (except for transpositions) holds for left-to-right (LTR) order as used in FORTRAN. In the exposition, we use mathematical notation, which is LTR.There is a Java 1.4 code and an APL WS available. The Java code requires an interactive input of the dimension of the original array and its shape vector. The APL WS contains FNS that work the same way, and others that can be used as callable sub FNS. An appendix exhibits the APL code that computes this algorithm for a given j.

REFERENCES

• 1: Ronald I. Frank , Fred Grossman, Regular array expansions in null arrays, with applications: zero is not nothing, 2002
• 2: Ronald I. Frank, A generating function that counts the combinatorial full-span sub array structure of a regular array with some applications to APL, Proceedings of the 2003 conference on APL: stretching the mind, p.63-69, June 11-14, 2003, San Diego, California [doi>10.1145/882067.882076]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Theory

Keywords:
APL, algorithm, array decomposition, array structure, full span sub array, regular array