TOPICS
Search

Array


An array is a "list of lists" with the length of each level of list the same. The size (sometimes called the "shape") of a d-dimensional array is then indicated as m×n×...×p_()_(d). The most common type of array encountered is the two-dimensional m×n rectangular array having m columns and n rows. If m=n, a square array results. Sometimes, the order of the elements in an array is significant (as in a matrix), whereas at other times, arrays which are equivalent modulo reflections (and rotations, in the case of a square array) are considered identical (as in a magic square or prime array).

In the Wolfram Language, an array of depth n is represented using nested lists, and can be generated using the command Array[a, {i, j, ...}]. Similarly, the dimensions of an array can be found using Dimensions[t], and the command ArrayQ[expr] tests if an expression is a full array. Taking for example

  t=Array[a,{2,2,2,3}]

gives the depth-4 list

  {{{{a[1,1,1,1],a[1,1,1,2],a[1,1,1,3]},
     {a[1,1,2,1],a[1,1,2,2],a[1,1,2,3]}},
    {{a[1,2,1,1],a[1,2,1,2],a[1,2,1,3]},
     {a[1,2,2,1],a[1,2,2,2],a[1,2,2,3]}}},
   {{{a[2,1,1,1],a[2,1,1,2],a[2,1,1,3]},
     {a[2,1,2,1],a[2,1,2,2],a[2,1,2,3]}},
    {{a[2,2,1,1],a[2,2,1,2],a[2,2,1,3]},
     {a[2,2,2,1],a[2,2,2,2],a[2,2,2,3]}}}}

with dimensions {2, 2, 2, 3}.

In order to exhaustively list the number of distinct arrays of a given shape with each element being one of k possible choices, the naive algorithm of running through each case and checking to see whether it is equivalent to an earlier one is already just about as efficient as can be. The running time must be at least the number of answers, and this is so close to k^(mn...p) that the difference isn't significant.

However, finding the number of possible arrays of a given shape is much easier, and an exact formula can be obtained using the Pólya enumeration theorem. For the simple case of an m×n array, even this proves unnecessary since there are only a few possible symmetry types, allowing the possibilities to be counted explicitly. For example, consider the case of m and n even and distinct, so only reflections need be included. To take a specific case, let m=6 and n=4 so the array looks like

 a b c | d e f; g h i | j k l; - - - + - - -; m n o | p q r; s t u | v w x,
(1)

where each a, b, ..., x can take a value from 1 to k. The total number of possible arrangements is k^(24) (k^(mn) in general). The number of arrangements which are equivalent to their left-right mirror images is k^(12) (in general, k^(mn/2)), as is the number equal to their up-down mirror images, or their rotations through 180 degrees. There are also k^6 arrangements (in general, k^(mn/4)) with full symmetry.

In general, it is therefore true that

 {k^(mn/4)   with full symmetry; k^(mn/2)-k^(mn/4)   with only left-right reflection; k^(mn/2)-k^(mn/4)   with only up-down reflection; k^(mn/2)-k^(mn/4)   with only 180 degrees rotation,
(2)

so there are

 k^(mn)-3k^(mn/2)+2k^(mn/4)
(3)

arrangements with no symmetry. Now dividing by the number of images of each type, the result, for m!=n with m,n even, is

N(m,n,k)=1/4k^(mn)+(1/2)(3)(k^(mn/2)-k^(mn/4))+1/4(k^(mn)-3k^(mn/2)+2k^(mn/4))
(4)
=1/4k^(mn)+3/4k^(mn/2)+1/2k^(mn/4).
(5)

The number is therefore of order O(k^(mn)/4), with "correction" terms of much smaller order.


See also

Antimagic Square, Euler Square, Kirkman's Schoolgirl Problem, Latin Rectangle, Latin Square, Magic Square, Matrix, Mrs. Perkins's Quilt, Multiplication Table, Orthogonal Array, Perfect Square, Prime Array, Quotient-Difference Table, Room Square, Square Array, Stolarsky Array, Tensor, Truth Table, Vector, Wythoff Array

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Array." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Array.html

Subject classifications