n-tuple sequences, the constraints they must satisfy,

Hi Folks,

Thank you for your help this past week in answering my question about
sequences. Below is a description of the sequences, the constraints they must
satisfy, and XPath expressions for implementing the constraints.  /Roger

Problem: Sometimes you want all possible sequences of elements of a set with
lengths from 0 to n, where n is the number of elements in the set. Such
sequences are called n-tuples, or, permutations with repetition.
(https://en.wikipedia.org/wiki/Permutation#Permutations_with_repetition)

Let's look at some examples.

Here is a set: {A, B}

Here are the valid sequences: (), (A), (B), (A, A), (A, B), (B, A), (B, B)

Notice it has:
- The empty sequence.
- Two sequences, one for each element in the set.
- Four sequences, each consisting of two elements, in all permutations.

Total number of sequences: 7

Suppose the set contains three elements: {A, B, C}

Then here are the valid sequences:

(), (A), (B), (C), (A, A), (A, B), (A, C), (B, A), (B, B), (B, C), (C, A), (C,
B), (C, C), (A, A, A), (A, A, B), (A, A, C), (A, B, A), (A, B, B), (A, B, C),
(A, C, A), (A, C, B), (A, C, C), (B, A, A), (B, A, B), (B, A, C), (B, B, A),
(B, B, B), (B, B, C), (B, C, A), (B, C, B), (B, C, C), (C, A, A), (C, A, B),
(C, A, C), (C, B, A), (C, B, B), (C, B, C), (C, C, A), (C, C, B), (C, C, C)

Notice it has:
- The empty sequence.
- Three sequences, one for each element in the set.
- Nine sequences, each consisting of two elements, in all permutations.
- Twenty-seven sequences, each consisting of three elements, in all
permutations.

Total number of sequences: 40

If the set has 4 elements, then the total number of sequences is 341.

The number of sequences grows rapidly as the number of elements in the set
increases.

Of all possible sequences in the universe, only certain sequences are valid
(i.e., have the desired properties). What are the constraints that sequences
must satisfy to be valid?

Here are the constraints that sequences must satisfy:

Constraint 1. There must be an empty sequence.
Constraint 2. All sequences have a length less than or equal to n (the length
of the set).
Constraint 3. The total number of sequences is sum(n^k) for k = 0 to n.
Constraint 4. For every sequence s that does not already have the maximum
length, there is, for every item i in the set, an (extended) sequence s' whose
items are the same as s plus item i.

Let's look at an XML representation of the sequences and how to express the
constraints using XPath.

Here is an XML representation of a set containing two elements:

<set>
    <item>A</item>
    <item>B</item>
</set>

Here is an XML representation of the sequences for that set:

<sequences>
    <sequence/>
    <sequence>
        <item>A</item>
    </sequence>
    <sequence>
        <item>B</item>
    </sequence>
    <sequence>
        <item>A</item>
        <item>A</item>
    </sequence>
    <sequence>
        <item>A</item>
        <item>B</item>
    </sequence>
    <sequence>
        <item>B</item>
        <item>A</item>
    </sequence>
    <sequence>
        <item>B</item>
        <item>B</item>
    </sequence>
</sequences>

The empty sequence () is represented by:

    <sequence/>

The sequence (A) is represented by:

    <sequence>
        <item>A</item>
    </sequence>

The sequence (A, B) is represented by:

    <sequence>
        <item>A</item>
        <item>B</item>
    </sequence>

And so forth.

Below are XPath expressions for each of the constraints.

Note: assume the root element <sequences> is the context node, $set is a
variable holding the set XML document, and $n is a variable holding the number
of elements in the set.

Constraint 1. There must be an empty sequence.

sequence[empty(item)]

Constraint 2. All sequences have a length less than or equal to n.

every $sequence in sequence satisfies count($sequence/item) le $n

Constraint 3. The total number of sequences is sum(n^k) for k = 0 to n.

count(sequence) = sum(for $i in 0 to $n return math:pow($n, $i))

Constraint 4. For every sequence s that does not already have the maximum
length, there is, for every item i in the set, an (extended) sequence s' whose
items are the same as s plus item i.

every $sequence in sequence[count(item) lt $n] satisfies
          every $item in $set//item satisfies
                    some $sequence-extended in sequence satisfies
                             deep-equal($sequence-extended/item,
($sequence/item, $item))

Acknowledgement

Thank you to the following people for their fantastic help with creating the
XPath expressions:

    - David Carlisle
    - Michael Kay
    - Christoph Naber