Trying all permutations

Given any set of scripts that are aware, convergent, and homogeneous, one can try them in all possible permutations in a very straightforward way. One exploits the following mathematical fact:

Proposition 5: Given a sequence $S = A_1 \ldots A_n$ of n objects, the sequence containing n-1 copies of S followed by the first object A₁ in S contains all permutations of the members of A as subsequences. This sequence contains n(n-1)+1 elements.

Counter to intuition, enumerating all permutations as subsequences of a given sequence does not require O(n!) steps, but only O(n²) steps.

As an aside, this fact is easy to see by inductive proof. The inductive basis case is that for two objects A₁ and A₂, the appropriate sequence is A₁A₂A₁. If we presume that the proposition is true for $A_1 \ldots A_{n-1}$, then a sequence S_n-1 consisting of n-2 copies of $A_1 \ldots A_{n-1}$, followed by A₁, contains all permutations of $A_1 \ldots A_{n-1}$ as subsequences. For A_n elements, we construct the sequence S_n of n-1 copies of $A_1 \ldots A_n$, followed by A₁. Our claim is that S_n contains all permutations of $A_1 \ldots A_n$ as subsequences.

To show this, we choose one element A_i from the first copy of $A_1 \ldots A_n$, and consider the subsequence of this sequence constructed by starting after A_i and deleting A_i from the rest. The beginning of this subsequence always has the form of the sequence in the inductive hypothesis, and thus contains all permutations of the A's without A_i. Thus the sequence S_n (of which this is a subsequence) contains all permutations starting with A_i. As A_i was arbitrary, S_n contains all permutations of the A's.

For example, consider what happens with four scripts A, B, C, and D. If we start with the sequence ABCDABCDABCDA and select, e.g., C from the first group, the subsequence constructed according to the proof is ABDABDA, which has already been shown to contain all permutations of A, B, and D. By repeating this process we can generate all permutations of A, B, C, and D:

 
subsequence     permutations
 ABCDABCDABCDA   
 ABCD.BCD.B...  (A first)
 .BCD..C......  ABCD, ABDC
 ..C..B.D.B...  ACBD, ACDB
 ...D.BC..B...  ADBC, ADCB
 .BCDA.CDA.C..  (B first)
 ..CDA..D.....  BCDA, BCAD
 ...DA.C.A....  BDAC, BDCA
 ....A.CD..C..  BACD, BADC
 ..CDAB.DAB.D.  (C first)
 ...DABA......  CDAB, CDBA
 ....AB.D.B...  CABD, CADB
 .....B..A..DA  CBAD, CBDA
 ...DABC.ABC.A  (D first)
 ....ABC..B...  DABC, DACB
 .....BC.A.C..  DBCA, DBAC
 ......C.AB..A  DCAB, DCBA

This is not the best known solution to the problem of ``Permutation Embedding''. For n objects there is a sequence of n²-2n+4elements that contains all permutations of the original objects as subsequences[1,5,13,19,22,26,27]. The methods utilized to construct a sequence with this lower bound are less intuitive than ours, while the size of the sequence remains O(n²) in all cases. To our knowledge, finding the optimal solution in the general case remains an open problem in combinatorics.

In our case, the objects being permuted are scripts that manage the values of configurable attributes, while the sequence is the execution order for the scripts. If we know that a correct order for the scripts exists, then if we try to execute them in the order suggested above, that order will be achieved at some time during the process. Because of our homogeneity constraint, each script need work only once and scripts will not undo the work of others, so that one iteration of the scripts in the proper order is all that is required. Thus the precedence constraints for all scripts will be satisfied if there is a way to satisfy them at all, and the algorithm dynamically infers the correct execution order for the scripts as it executes.