Subject: [xsl] n-tuple sequences, the constraints they must satisfy, and their XPath expressions From: "Costello, Roger L. costello@xxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> Date: Wed, 22 Nov 2017 18:53:46 -0000 |
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
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] How to compare two sequen, Michael Kay mike@xxx | Thread | Re: [xsl] n-tuple sequences, the co, David Carlisle d.p.c |
Re: [xsl] How to compare two sequen, Michael Kay mike@xxx | Date | Re: [xsl] n-tuple sequences, the co, David Carlisle d.p.c |
Month |