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

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(_at_)mitre(_dot_)org
<xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com> 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
--~----------------------------------------------------------------
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
--~--