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:Counter to intuition, enumerating all permutations asGiven a sequenceofnobjects, the sequence containingn-1copies ofSfollowed by the first objectA_{1}inScontains all permutations of the members ofAas subsequences. This sequence containsn(n-1)+1elements.

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

To show this, we choose one element *A*_{i} from the first copy of
,
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*^{2}-2*n*+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*^{2}) 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.*