Rubik cube
Colin Fahey

1. Software

rubikcube_100x100x100.jpg
Rubik cube
RubikCube2008June.zip
Rubik cube computer code (C# and C++ versions) and program ("exe");
4068277 bytes
MD5: 4e957e0ead66064183e9f7e04e618ec0

2. Definitions

"brick" : a (d)-dimensional, cube shaped object, having a volume of 1, and a center point, and an orientation, and other attributes.
"mechanism" : a (d)-dimensional object, with a center point, and an orientation, and a collection of bricks.
The bricks are attached to the mechanism.
The positions and orientations of the bricks can be expressed as positions and orientations relative to the center point and orientation of the mechanism.
"Rubik cube" : a mechanical puzzle formed by a cubic arrangement of bricks, spanning (n) bricks in each dimension, with (n>=1), for a total of (n*n*n) bricks.
The bricks are linked together in a manner that enables all (n*n) bricks in any plane parallel to two of the three dimensions can be rotated together in that plane, around the center of the set of (n*n) bricks in that plane.

3. Introduction

This document describes how the idea of the Rubik cube can be generalized to a (d)-dimensional mechanism with an arbitrary number of bricks along each dimension.
This document also includes an analysis of the Rubik cube and describes how humans and computers can solve the Rubik cube.
This document includes software that enables a person to visualize and manipulate a (d)-dimensional mechanism with an arbitrary number of bricks along each dimension.
For example, a 6-dimensional mechanism, with (3*5*7*11*13*17) bricks, can be displayed and manipulated.
A 19-dimensional mechanism can be displayed and manipulated.
For the special case of a 3-dimensional mechanism with (n*n*n) bricks, a huge mechanism of (4096*4096*4096) bricks can be displayed and manipulated.
This document also includes references to interesting projects related to the Rubik cube.

4. (d)-dimensional mechanism : attributes

4.1 (d)-dimensional cube

Consider a coordinate system in (d)-dimensional space, with (d) coordinates { x(0), x(1), ..., x(d-1) }.
A (d)-dimensional, axis-aligned cube is a set of points, (S), such that, given points (A) and (B), where (A[k] <= B[k]) for all 0 <= k <= (d-1), each point P = ( P[0], P[1], ..., P[d-1] ) in set (S) has (P[i] >= A[i]) and (P[i] <= B[i]) for all 0 <= i <= (d-1).
Each coordinate of point (A) represents the minimum permitted value of the corresponding coordinate of points within the cube.
Each coordinate of point (B) represents the maximum permitted value of the corresponding coordinate of points within the cube.
The center of the cube is located at a point C = ((A + B) / 2) in (d)-dimensional space.
The thickness of each dimension of the cube is given by D[i] = (B[i] - A[i]).
The (d)-dimensional volume of the (d)-dimensional, axis-aligned cube is: V = ( D[0] * D[1] * ... * D[d-1] ).
If an axis-aligned cube is assigned a set of (d) mutually-perpendicular vectors, { g(0), g(1), ..., g(d-1) }, when the cube is in a known "default" orientation relative to the external coordinate system, then any orientation of that cube can be specified or described by a matrix (G) where the columns of that matrix are the vectors { g(0), g(1), ..., g(d-1) }.
Each coordinate of each point (P) within an axis-aligned cube is bound by two extreme values; (P[i] >= A[i]) and (P[i] <= B[i]).
Consider points such that all coordinates are at extreme values; each point (P) is such that (P[i] == A[i]) or (P[i] == B[i]) for all 0 <= i <= (d-1).
Because each coordinate can be at one of two extremes (possibly not distinct), and because there are (d) coordinates, the number of combinations of extreme coordinates is (2^(d)).
Thus, a (d)-dimensional cube has (2^(d)) extreme points (some of which might not be distinct if the thickness in one or more dimensions is zero).

4.2 (d)-dimensional brick

A "(d)-dimensional brick" is a (d)-dimensional cube, with the attributes below:
(1) All thicknesses are equal to 1 unit of distance;
(2) Its center is located at point (BC) relative to an external coordinate system;
(3) Its orientation is described by a matrix (BG), consisting of mutually-perpendicular direction vectors { g(0), g(1), ..., g(d-1) } as columns, with each vector specified relative to an external coordinate system;
(4) A (d)-dimensional vector of integers, (BHD), specifies "default position indices";
(5) A (d)-dimensional vector of integers, (BH), specifies "current position indices".
The meaning and purpose of the "default position indices" and the "current position indices" are described in the section "The 'default configuration' of a (d)-dimensional mechanism".

4.3 (d)-dimensional mechanism

A "(d)-dimensional mechanism" is a collection of (d)-dimensional bricks in (d)-dimensional space, with the attributes below:
(1) Its center is located at point (PC) relative to an external coordinate system;
(2) Its orientation is described by a matrix, (PG), consisting of mutually-perpendicular direction vectors { g(0), g(1), ..., g(d-1) } as columns, with each vector specified relative to an external coordinate system;
(3) Its thicknesses (in numbers of bricks) in each dimension (when the mechanism is in its "default configuration") is given by the (d)-dimensional vector of integers (N), where (N[i] >= 1) for all 0 <= i <= (d-1).
(4) The center (BC) of each brick is specified relative to the mechanism coordinate system (relative to (PC) and (PG).
The orientation (BG) of each brick is specified relative to the mechanism coordinate system (relative to (PC) and (PG)).
The total number of bricks in the mechanism is given by: V = ( N[0] * N[1] * ... * N[d-1] ).

4.4 (d)-dimensional mechanism : "default configuration"

A (d)-dimensional mechanism in the "default configuration" has the attributes below:
(1) For each vector of integers (PH), such that (PH[i] >= 1) and (PH[i] <= N[i]) for all 0 <= i <= (d-1), there is an associated brick with the attributes below:
(a) The center of the brick, (BC), relative to the coordinate system of the mechanism ((PC) and (PG)), is such that BC[i] = (PH[i] - 1) - ((N[i] - 1)/2) = PH[i] - (N[i]/2) - (1/2);
(b) The orientation of the brick, (BG), relative to the coordinate system of the mechanism ((PC) and (PG)), is the "identity matrix" (BG[i,i]=1 for all 0 <= i <= (d-1), and BG[i,j]=0 for all (i != j) with 0 <= i <= (d-1) and 0 <= j <= (d-1).
All (d) direction vectors of the brick are positively aligned with the (d) coordinate axes of the mechanism;
(c) The brick is assigned "default position indices" of BHD = PH.
These indices indicate, in terms of a numbering of bricks in each dimension, where a brick is positioned in the default configuration of the mechanism.
These indices are constant for the given brick.
No other brick in the mechanism has the same set of index values;
(d) The brick is assigned "current position indices" of BH = PH.
These indices indicate, in terms of a numbering of bricks in each dimension, where a brick is currently positioned in the mechanism.
These indices will change if a brick is moved to a different position in the mechanism.
However, no other brick in the mechanism has the same set of index values.
( The "current position indices", (BH), of a brick are not constrained to satisfy (BH[i] >= 1) and (BH[i] <= N[i]) for all 0 <= i <= (d-1).
If a mechanism is such that (N[i] != N[j]) for one or more combinations of (i != j) with 0 <= i <= (d-1) and 0 <= j <= (d-1), then it is possible for a brick to be moved to a position such that the current position indices, (BH), of the brick have (BH[i] < 1) or (BH[i] > N[i]) for one or more 0 <= i <= (d-1). );
(2) The position of center of the mechanism, (PC), relative to an external coordinate system, is at a default position (example: PC = 0 (zero vector)).
The orientation of the mechanism, (PG), relative to an external coordinate system, is in a default orientation (example: PG = Identity(d)).

4.5 (d)-dimensional mechanism : surface and interior bricks

A "surface brick" is any brick with "default position indices", (BHD), such that (BHD[i] == 1) or (BHD[i] == N[i]) for any 0 <= i <= (d-1).
An "interior brick" is any brick that is not a "surface brick".
Because the classification of a brick as a "surface brick" or as an "interior brick" is based on the "default position indices" of the brick, the classification is a constant attribute of the brick.

4.6 (d)-dimensional mechanism : brick "default position similarity sets"

For a given brick in a mechanism, let (BHDIsMin) be a vector of integers such that, for each 0 <= i <= (d-1), BHDIsMin[i] = 1 if (BHD[i] == 1), and BHDIsMin[i] = 0 if (BHD[i] != 1).
For a given brick in a mechanism, let (BHDIsMax) be a vector of integers such that, for each 0 <= i <= (d-1), BHDIsMax[i] = 1 if (BHD[i] == N[i]), and BHDIsMax[i] = 0 if (BHD[i] != N[i]).
Each brick in the mechanism has corresponding vectors (BHDIsMin) and (BHDIsMax).
Bricks with the same pattern of values for their (BHDIsMin) vectors and for their (BHDIsMax) vectors are classified in to the same "default position similarity set".
A single integer number can contain the information contained in both the (BHDIsMin) vector and the (BHDIsMax) vector, essentially packing the bits in to an integer value.
The function below is one way of forming a "default position similarity set" numeric label:
public static long GetPositionSimilaritySetNumericLabel( H, N )
{
    // The result can be as high as ((2^(2*d))-1).
    // Thus, long (64-bit integer) can handle cases up to d=32 dimensions.
    long result = 0;
    int d = N.Count; // must be the same as H.Count
    for ( int i = 0; i <= (d - 1); i++ )
    {
        if (H[i]==1   ) { result += Int64Pow(2,((2*i)  )); }
        if (H[i]==N[i]) { result += Int64Pow(2,((2*i)+1)); }
    }
    return( result );
}
Thus, given (mechanism), (brick1), and (brick2), the bricks are in the same "default position similarity set" if (GetPositionSimilaritySetNumericLabel( brick1.BHD, mechanism.N ) == GetPositionSimilaritySetNumericLabel( brick2.BHD, mechanism.N )).
In a (d)-dimensional mechanism, all interior bricks, if any, belong to the same "default position similarity set".
For a (d)-dimensional mechanism of (3^d) or larger (((N[i]>=3) for all 0 <= i <= (d-1)), there are Combinations( d, k ) ways of choosing (k) extreme coordinates from among the (d) total coordinates.
Each of the (k) coordinates can be at one of two extremes.
Therefore, we have (2^(k)) ways of choosing specific extremes for the (k) extreme coordinates.
Therefore, a (d)-dimensional mechanism of (3^d) or larger has a number of sets of (k)-extreme-coordinates bricks with the same combination of extreme coordinates:
(2^(k)) * Combinations( d, k )

    = (2^(k)) * (Factorial(d) / (Factorial(k) * Factorial(d - k)));
For a (d)-dimensional mechanism of (3^d) or larger, the total number of "default position similarity sets" is (3^(d)).
This can be found by adding the total number of sets with (k)-extreme-coordinates for all 0 <= k <= d.
A three-dimensional mechanism of (3*3*3) or larger has 27 "default position similarity sets":
1 set of 0-extreme-coordinates bricks (interior bricks), 6 sets of 1-extreme-coordinate bricks ("face interiors"), 12 sets of 2-extreme-coordinates bricks ("edges"), and 8 sets of 3-extreme-coordinates bricks ("corners"). For a (3*3*3) mechanism, each set contains a single brick.
The image below shows "default position similarity sets" for various three-dimensional mechanisms.
In the image below, each similarity set is assigned a distinct color.
positionsimilaritysets.jpg
A four-dimensional mechanism of (3*3*3*3) or larger has 81 "default position similarity sets":
1 set of 0-extreme-coordinates bricks (interior bricks), 8 sets of 1-extreme-coordinate bricks ("face interiors"), 24 sets of 2-extreme-coordinates bricks, 32 sets of 3-extreme-coordinates bricks, and 16 sets of 4-extreme-coordinates bricks.
For a (3*3*3*3) mechanism, each set contains a single brick.
A (d)-dimensional mechanism with a thickness less than 3 in any dimension will have fewer than (3^(d)) "default position similarity sets", because some kinds of similarity sets will not exist.
For example, a (2*2*2) mechanism does not have any 0-extreme-coordinates bricks or 1-extreme-coordinate bricks.
If any thickness is equal to 1, then new kinds of (k)-extreme-coordinates bricks will appear.
For example, a (1*1*1) mechanism (a single brick) has a single 6-extreme-coordinates brick.

4.7 (d)-dimensional mechanism : brick orientation labels

Each brick in a mechanism has a list of "orientation labels", represented by a (d)-dimensional vector of integers (BL), such that (BL[i]==0) if axis (i) of a brick is unmarked, and (BL[i]==1) if axis (i) of a brick is marked, for all 0 <= i <= (d-1).
Each "interior brick" typically has no non-zero "orientation labels"; (BL[i] == 0) for all 0 <= i <= (d-1).
Each "surface brick" typically has one or more non-zero "orientation labels"; (BL[i] != 0) for one or more 0 <= i <= (d-1).
By default, each "surface brick" has "orientation labels" assigned such that (BL[i] == 1) if (BHD[i] == 1) or (BHD[i] == N[i]), and otherwise (BL[i] == 0), for all 0 <= i <= (d-1).
Thus, by default, an axis label is set if, when the brick is in its default position, the brick is at one of the two extremes (possibly identical) of that dimension of the mechanism.
A "surface brick" can have additional "orientation labels" applied when the cube is constructed.
Thus, even if a surface brick only has one extreme coordinate when it is at its default position, an additional label can be applied to the brick by the mechanism manufacturer.
A non-zero "orientation label" ((BL[i] != 0) for a particular 0 <= i <= (d-1)) makes the orientation of the corresponding brick axis (example: g(i)) significant, otherwise (if the axis label is zero), the orientation of the corresponding brick axis is not significant.

4.8 (d)-dimensional mechanism : "slices"

A "slice" of a (d)-dimensional mechanism is a 2-dimensional plane parallel to 2 of the axes of the mechanism.
A particular slice is described by specifying : the 2 axes parallel to the plane of the slice, and (d-2) coordinate values that specify the position of the plane relative to the remaining (d-2) mechanism axes.
A slice can be specified by Slice( a, b, H ), where (a), with 0 <= a <= (d-1), indicates the index of the coordinate axis of one of the two axes parallel to the slice plane, and (b), with (b != a) and 0 <= b <= (d-1), indicates the index of the coordinate axis of another of the two axes parallel to the slice plane, and the (d)-dimensional vector (H) indicates the position of the plane along the remaining (d-2) mechanism axes.
(The components H[a] and H[b] are ignored, and can be arbitrarily set to zero.)
A brick, (brick), in a mechanism, is within a slice, (slice), if ((brick).BH[i] == (slice).H[i]) for all 0 <= i <= (d-1) and (i != (slice).a) and (i != (slice).b).

4.9 (d)-dimensional mechanism : slice rotations

A "slice rotation" of a (d)-dimensional mechanism, given a specific slice, is the rotation of all bricks contained in the slice such that all bricks remain in the plane of the slice and the bricks rotate around the point (xa=0,xb=0) within the plane (where xa and xb are the coordinate axes within the plane of the slice).
A slice rotation can change the positions of some bricks in a mechanism.
A slice rotation can change the orientations of some bricks in a mechanism.
Slice rotations are the only way to change the positions or orientations of bricks within in a mechanism.
(The whole mechanism can be moved or rotated to alter viewing conditions.)
A slice rotation can be described by specifying a slice and by specifying an angle.
For example, we can represent a slice rotation by "R(a,b,H,k)", where (a) and (b) specify the axes parallel to the slice plane, and (H) specifies the position of the plane (using (d-2) of the (d) coordinate values), and (k) specifies the angle (in terms of a positive multiple of quarter turn increments; k = 1, 2, or 3).

4.10 (d)-dimensional mechanism : "solved" status

A (d)-dimensional mechanism is "solved" if, for one of the ((2^(d-1))*Factorial(d)) orientations of the whole mechanism, the oriented mechanism has all of the attributes below:
(1) For each brick, (brick), in the mechanism, (GetPositionSimilaritySetNumericLabel( brick.BH, mechanism.N ) == GetPositionSimilaritySetNumericLabel( brick.BHD, mechanism.N )); the position similarity set corresponding to the current position of a brick is the same as the position similarity set that the brick belongs to when the brick is in its default position.
Bricks can exchange positions with other bricks in the same position similarity set without changing the "solved" status of the mechanism.
(The brick current position indices mentioned here should be transformed in the same manner as the whole mechanism before doing this check.)
(2) For each brick, (brick), in the mechanism, ((brick).BG[i] == e(i)) for all 0 <= i <= (d-1) and (BL[i] != 0); if the axis is marked as significant (by a label), then the corresponding direction vector (column) of the orientation matrix must point in the positive direction along the appropriate axis, just as it did when the mechanism was in its default configuration.
(The brick orientation matrices mentioned here should be transformed in the same manner as the whole mechanism before doing this check.)
A mechanism in its "default configuration" is a "solved" mechanism.
However, there might be many more configurations of a mechanism that are also in a "solved" status.
( For example, for the classic (3*3*3) Rubik Cube, the 6 "face center" bricks can be given arbitrary orientations without affecting the "solved" status of the cube.
Larger cubes introduce the possibility of permuting some brick positions without affecting the "solved" status of the cube. )

5. Sequences of operations, and multiplication of operators

If (A), (B), and (C), represent actions or operations, and the concept of "do action (A), then (B), then (C)" is to be expressed, one method would be to write them in the order in which the actions are to be done: "A,B,C".
If an action, (A), is to be repeated (k) times, this could be expressed as "kA".
If a sequence of actions, "A,B", is to be repeated (k) times, this could be expressed as "k(A,B)".
Thus, the expression "3(A,B)C,4D,2(E,F)" could be interpreted as "A,B,A,B,A,B,C,D,D,D,D,E,F,E,F".
In some cases, doing operation (A) then operation (B) will create results that are generally different than doing operation (B) then operation (A); "A,B" is not generally equivalent to "B,A".
( For example, let (A) = "put on shoe", and let (B) = "put on sock". )
When "A,B" is not the same as "B,A", the operations (A) and (B) "do not commutate".
However, in mathematics, given a status (P) and an operation (A), the expression "A * P", often means "apply operation (A) to status (P) (to create a new status)".
Likewise, given a status (P), an operation (A), an operation (B), and an operation (C), the expression "C * B * A * P", often means "apply operation (A) to status (P) to create a new status, and then apply operation (B) to the new status to create yet another status, and then apply operation (C) to create the result status".
An operation, (B), can act on another operation, (A), to create a new operation, (F), which, when applied to a status, (P), will have the same effect as applying the operation (A) and operation (B) in sequence; "F = B * A" implies "F * P = B * A * P".
If a single operation (A) is to be repeated (k) times, this can be expressed as "A^k" ((A) to the (k) exponent).
If a sequence of operations "C*B*A" (A, then B, then C) is to be repeated (k) times, this can be expressed as "(C*B*A)^k".
For example, "((F*E)^2)*(D^4)*C*(B*A)^3" represents "F*E*F*E*D*D*D*D*C*B*A*B*A*B*A".
"(B*A)^k" is "B*A*B*A*...*B*A", and not "B^k * A^k" ("B*B*B*...*B * A*A*A*...*A"), because "B*A" is generally not the same as "A*B" ((A) and (B) do not generally commutate).
Therefore, we cannot arbitrarily change the order of the operators.
Given the two ways of representing the order of operations (natural order and mathematical order) of a sequence of operations, it is important to know which order of operations an expression represents.
If commas (",") are used in an expression, the order of the sequence of operations is unambiguous; the first operation in the comma-delimited sequence is the first to apply.
Likewise, if multiplication symbols (example: "*") are used in an expression, then the order of the sequence of operations is unambiguous; the right-most operation in a product is the first to apply.
However, some expressions do not include commas or multiplication symbols.
The order of operations in such expressions must be inferred by the context.

5.1 Permutations of 4 objects

Given 4 objects with the unique numeric labels { 1, 2, 3, 4 }, we can generate all 24 permutations through the use of the rearrangement operations below:
Z = [ 3, 4, 2, 1 ],   Z2 = [ 2, 1, 4, 3 ],   Zi = [ 4, 3, 1, 2 ],
Y = [ 2, 3, 4, 1 ],   Y2 = [ 3, 4, 1, 2 ],   Yi = [ 4, 1, 2, 3 ],
X = [ 3, 1, 4, 2 ],   X2 = [ 4, 3, 2, 1 ],   Xi = [ 2, 4, 1, 3 ]
The symbols { Z, Z2, Zi, Y, Y2, Yi, X, X2, Xi } are abbreviations for the rearrangement operations.
The diagram below shows how each permutation is directly linked to 9 other permutations by the 9 rearrangement operations { Z, Z2, Zi, Y, Y2, Yi, X, X2, Xi }.
permutation24.jpg
This is the same group structure as the 24 axis-aligned orientations linked by the 9 rotations sharing the same names, { Z, Z2, Zi, Y, Y2, Yi, X, X2, Xi }.
The table below shows how each of the 24 permutations is directly linked to 9 other permutations by the 9 rearrangement operations { Z, Z2, Zi, Y, Y2, Yi, X, X2, Xi }.
Each permutations is indicated by the corresponding rearrangement operation and the corresponding cycle notation.
The table entries show the rearrangement (1..24) that results from applying the rearrangement operation associated with a column of the table to the rearrangement associated with a row of the table.
---------------------------------------------------------------------------
  # : Rearrangement  :    Cycles    :   X  X2  Xi    Y  Y2  Yi    Z  Z2  Zi
---------------------------------------------------------------------------
  1 : [ 1, 2, 3, 4 ] : (1)(2)(3)(4) :   5   2   6   14   3  16   24   4  21
  2 : [ 4, 3, 2, 1 ] : (1 4)(2 3)   :   6   1   5   13   4  15   23   3  22
  3 : [ 3, 4, 1, 2 ] : (1 3)(2 4)   :   7   4   8   16   1  14   22   2  23
  4 : [ 2, 1, 4, 3 ] : (1 2)(3 4)   :   8   3   7   15   2  13   21   1  24
---------------------------------------------------------------------------
  5 : [ 3, 1, 4, 2 ] : (1 2 4 3)    :   2   6   1    9   8  12   20   7  18
  6 : [ 2, 4, 1, 3 ] : (1 3 4 2)    :   1   5   2   10   7  11   19   8  17
  7 : [ 4, 2, 3, 1 ] : (1 4)(2)(3)  :   4   8   3   11   6  10   18   5  20
  8 : [ 1, 3, 2, 4 ] : (1)(2 3)(4)  :   3   7   4   12   5   9   17   6  19
---------------------------------------------------------------------------
  9 : [ 4, 2, 1, 3 ] : (1 3 4)(2)   :  22  11  24    8  12   5   13  10  14
 10 : [ 3, 1, 2, 4 ] : (1 2 3)(4)   :  21  12  23    7  11   6   14   9  13
 11 : [ 1, 3, 4, 2 ] : (1)(2 4 3)   :  24   9  22    6  10   7   15  12  16
 12 : [ 2, 4, 3, 1 ] : (1 4 2)(3)   :  23  10  21    5   9   8   16  11  15
---------------------------------------------------------------------------
 13 : [ 1, 4, 3, 2 ] : (1)(2 4)(3)  :  17  16  20    4  15   2   10  14   9
 14 : [ 2, 3, 4, 1 ] : (1 4 3 2)    :  18  15  19    3  16   1    9  13  10
 15 : [ 3, 2, 1, 4 ] : (1 3)(2)(4)  :  19  14  18    2  13   4   12  16  11
 16 : [ 4, 1, 2, 3 ] : (1 2 3 4)    :  20  13  17    1  14   3   11  15  12
---------------------------------------------------------------------------
 17 : [ 3, 2, 4, 1 ] : (1 4 3)(2)   :  16  20  13   21  18  22    6  19   8
 18 : [ 1, 4, 2, 3 ] : (1)(2 3 4)   :  15  19  14   22  17  21    5  20   7
 19 : [ 4, 1, 3, 2 ] : (1 2 4)(3)   :  14  18  15   23  20  24    8  17   6
 20 : [ 2, 3, 1, 4 ] : (1 3 2)(4)   :  13  17  16   24  19  23    7  18   5
---------------------------------------------------------------------------
 21 : [ 4, 3, 1, 2 ] : (1 3 2 4)    :  12  23  10   18  22  17    1  24   4
 22 : [ 2, 1, 3, 4 ] : (1 2)(3)(4)  :  11  24   9   17  21  18    2  23   3
 23 : [ 1, 2, 4, 3 ] : (1)(2)(3 4)  :  10  21  12   20  24  19    3  22   2
 24 : [ 3, 4, 2, 1 ] : (1 4 2 3)    :   9  22  11   19  23  20    4  21   1
---------------------------------------------------------------------------
If we permit all 9 rearrangement operations from the set { Z, Z2, Zi, Y, Y2, Yi, X, X2, Xi }, then the resulting histogram of the number of permutations requiring a minimum of a certain number of rearrangement operations to reach is: { 0:1, 1:9, 2:14 };
a minimum of 0 rearrangement operations is required to reach 1 permutation (the given permutation itself), and a minimum of 1 rearrangement operation is required to reach 9 permutations (where each permutation is produced by rearranging the given permutation by one of the 9 permitted rearrangement operations), and a minimum of 2 rearrangement operations is required to reach 14 permutations.
The histogram indicates that permitting the 9 rearrangement operations makes it possible to reach all 1 + 9 + 14 = 24 permutations.
The histogram indicates that the number of rearrangement operations, from the set of permitted rearrangement operations, required to convert any given permutation to any other given permutation, will be two or fewer rearrangement operations.
If the set of permitted rearrangement operations is arbitrarily reduced, then the number of links between permutations will be reduced, and the minimum number of rearrangement operations required to convert a given permutation to another given permutation might be larger than when more rearrangement operations are permitted.
If we permit all 9 rearrangement operations from the set { Z, Z2, Zi, Y, Y2, Yi, X, X2, Xi }, then the resulting histogram of the number of permutations requiring a minimum of a certain number of rearrangement operations to reach is: { 0:1, 1:9, 2:14 }.
If we only permit the 3 rearrangement operations from the set { Z, Y, X }, then, for any given permutation, the histogram becomes: { 0:1, 1:6, 2:11, 3:6 }, which indicates that all 1 + 6 + 11 + 6 = 24 permutations are reachable from the given permutation, and that three or fewer rearrangement operations are required to convert any given permutation to any other given permutation.
If we only permit the 2 rearrangement operations from the set { Z, Y }, then, for any given permutation, the histogram becomes: { 0:1, 1:4, 2:10, 3:8, 4:1 }, which indicates that all 1 + 4 + 10 + 8 + 1 = 24 permutation are reachable from the given permutation, and that four or fewer rearrangement operations are required to convert any given permutation to any other given permutation.
( X = (Z * Y * Zi) = (Z * Y * Z*Z*Z).
Therefore, { Z, Y } is sufficient to reach all rearrangements that can be reached with { Z, Y, X } (all 24 rearrangements).)
If we only permit the 1 rearrangement operation from the set { Z }, then, for any given permutation, the histogram becomes: { 0:1, 1:2, 2:1 }, which indicates that only 1 + 2 + 1 = 4 permutations are reachable from the given permutation; and, therefore, the set of 24 permutations is broken in to (24/4) = 6 distinct subsets of permutations that contain mutually-accessible permutations.
Evidently, a minimum of two rearrangement operations (associated with distinct cycles, and satisfying other conditions) are required to make it possible to convert any permutation to all other permutations.
colinfahey.com
contact information