Re: [xsl] n-tuple sequences, the constraints they must satisfy, and their XPath expressions

["David Carlisle d.p.carlisle@xxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx>]

your condition 4 is the most complicated and I don't think you need
it, given conditions 1-3 you just need to say that no two of your
sequences are deep-equal.

David

On 22 November 2017 at 18:53, Costello, Roger L. costello@xxxxxxxxx
<xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote:
> 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