[xsl] n-tuple sequences, the constraints they must satisfy, and their XP

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
--~----------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
EasyUnsubscribe: http://lists.mulberrytech.com/unsub/xsl-list/1167547
or by email: xsl-list-unsub(_at_)lists(_dot_)mulberrytech(_dot_)com
--~--