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

 Subject: Re: [xsl] n-tuple sequences, the constraints they must satisfy, and their XPath expressions From: "Christoph Naber pentium120mhz@xxxxxxxxx" Date: Fri, 24 Nov 2017 21:26:16 -0000
```Hello,

I don't want to leave a false statement here. Constraints 3 and 4 are
NOT enough to restrict the value set. The induction base as well as the
definition of value range and definition range is missing for this proof
to be complete. I wrote a working induction proof, if anyone is
interested...

Regards
Christoph

Am 24.11.2017 um 00:01 schrieb Christoph Naber pentium120mhz@xxxxxxxxx:
> Conditions 1-3 wouldn't work on their own.
> i.e. one could introduce items that do not belong to the original set.
> So one additional constraint has to check that.
> every \$s in \$sequences[item] satisfies (
> B B B  every \$item in \$s/item satisfies (
> B B B  B B B  some \$i in \$set satisfies deep-equal(\$i, \$item)))
>
> On top of that the deep-equal uniqueness check for sequences would be
> necessary if you drop constraint 4.
> every \$s in \$sequences, \$t in (\$sequences except \$s) satisfies
> not(deep-equal(\$s, \$t))
>
> Instead I think Rogers' forth condition is _absolutly marvelous_.
> Overall it enforces some kind of induction constraint on the sequences.
> "if you have one sequence that isn't full length, there have to be \$n
> bigger sequences that have been extended with each of the items from
> the set"
>
> I would be surprised if it would be necessary to have more than just
> the constraints 3 and 4 to decide the combinatorical question. I
> played around, but "lengthy" (see below) gave always the same result
> as "compressed"
>
> <xsl:stylesheet version="2.0"
> B B B  xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
> B B B  xmlns:math="http://www.w3.org/2005/xpath-functions/math";
> B B B  exclude-result-prefixes="math">
>
> B B B  <xsl:output method="xml" encoding="UTF-8" indent="yes"/>
>
> B B B  <xsl:template match="/" >
> B B B  B B B  <xsl:variable name="set">
> B B B  B B B  B B B  <item>A</item>
> B B B  B B B  B B B  <item>B</item>
> B B B  B B B  </xsl:variable>
>
> B B B  B B B  <xsl:variable name="sequences">
> B B B  B B B  B B B  <sequence />
> B B B  B B B  B B B  <sequence>
> B B B  B B B  B B B  B B B  <item>A</item>
> B B B  B B B  B B B  </sequence>
> B B B  B B B  B B B  <sequence>
> B B B  B B B  B B B  B B B  <item>B</item>
> B B B  B B B  B B B  </sequence>
> B B B  B B B  B B B  <sequence>
> B B B  B B B  B B B  B B B  <item>A</item>
> B B B  B B B  B B B  B B B  <item>A</item>
> B B B  B B B  B B B  </sequence>
> B B B  B B B  B B B  <sequence>
> B B B  B B B  B B B  B B B  <item>A</item>
> B B B  B B B  B B B  B B B  <item>B</item>
> B B B  B B B  B B B  </sequence>
> B B B  B B B  B B B  <sequence>
> B B B  B B B  B B B  B B B  <item>B</item>
> B B B  B B B  B B B  B B B  <item>A</item>
> B B B  B B B  B B B  </sequence>
> B B B  B B B  B B B  <sequence>
> B B B  B B B  B B B  B B B  <item>B</item>
> B B B  B B B  B B B  B B B  <item>B</item>
> B B B  B B B  B B B  </sequence>
> B B B  B B B  </xsl:variable>
>
> B B B  B B B  <xsl:variable name="n" select="count(\$set/item)" />
>
>
> B B B  B B B  <evaluation n="{\$n}">
> B B B  B B B  B B B  <compressed>
> B B B  B B B  B B B  B B B  <xsl:comment>The total number of sequences is sum(n^k)
> for k = 0 to n</xsl:comment>
> B B B  B B B  B B B  B B B  <constraint no="1">
> B B B  B B B  B B B  B B B  B B B  <xsl:value-of select="count(\$sequences/sequence)
> eq sum(for \$k in 0 to \$n return math:pow(\$n, \$k))" />
> B B B  B B B  B B B  B B B  </constraint>
> B B B  B B B  B B B  B B B  <xsl:comment>Inductional proof</xsl:comment>
> B B B  B B B  B B B  B B B  <constraint no="2">
> B B B  B B B  B B B  B B B  B B B  <xsl:value-of select="
> B B B  B B B  B B B  B B B  every \$s in \$sequences/sequence[count(item) lt \$n]
> satisfies
> B B B  B B B  B B B  B B B  B B B  every \$i in \$set/item satisfies
> B B B  B B B  B B B  B B B  B B B  B B B  some \$sequence-extended in \$sequences/sequence
> satisfies
> B B B B B B B B B B B B B B B B B B B B B B B B B B B B  deep-equal(\$sequence-extended/item,
> (\$s/item, \$i))" />
> B B B  B B B  B B B  B B B  </constraint>
> B B B  B B B  B B B  </compressed>
>
> B B B  B B B  B B B  <lengthy>
> <xsl:comment>sequence[empty(item)]</xsl:comment>
> B B B  B B B  B B B  B B B  <constraint no="1">
> B B B  B B B  B B B  B B B  B B B  <xsl:value-of select="every \$s in
> \$sequences/sequence satisfies count(\$s/item) le \$n" />
> B B B  B B B  B B B  B B B  </constraint>
> B B B  B B B  B B B  B B B  <xsl:comment>All sequences have a length less than or
> equal to count(\$items)</xsl:comment>
> B B B  B B B  B B B  B B B  <constraint no="2">
> B B B  B B B  B B B  B B B  B B B  <xsl:value-of select="every \$s in
> \$sequences/sequence satisfies count(\$s/item) le \$n" />
> B B B  B B B  B B B  B B B  </constraint>
>
> B B B  B B B  B B B  B B B  <xsl:comment>The total number of sequences is sum(n^k)
> for k = 0 to n</xsl:comment>
> B B B  B B B  B B B  B B B  <constraint no="3">
> B B B  B B B  B B B  B B B  B B B  <xsl:value-of select="count(\$sequences/sequence)
> eq sum(for \$k in 0 to \$n return math:pow(\$n, \$k))" />
> B B B  B B B  B B B  B B B  </constraint>
>
> B B B  B B B  B B B  B B B  <xsl:comment>All sequences are unique with respect to
> item-type and -order</xsl:comment>
> B B B  B B B  B B B  B B B  <constraint no="4">
> B B B  B B B  B B B  B B B  B B B  <xsl:value-of select="every \$s in
> \$sequences/sequence, \$t in (\$sequences/sequence except \$s) satisfies
> not(deep-equal(\$s, \$t))" />
> B B B  B B B  B B B  B B B  </constraint>
>
> B B B  B B B  B B B  B B B  <xsl:comment>All non-empty sequences must only contain
> items from the set</xsl:comment>
> B B B  B B B  B B B  B B B  <constraint no="5">
> B B B  B B B  B B B  B B B  B B B  <xsl:value-of select="
> B B B  B B B  B B B  B B B  B B B  B B B  every \$s in \$sequences/sequence[item] satisfies (
> B B B  B B B  B B B  B B B  B B B  B B B  B B B  every \$item in \$s/item satisfies (
> B B B  B B B  B B B  B B B  B B B  B B B  B B B  B B B  some \$i in \$set/item satisfies
> deep-equal(\$i, \$item)
> B B B  B B B  B B B  B B B  B B B  B B B  B B B  )
> B B B  B B B  B B B  B B B  B B B  B B B  )" />
> B B B  B B B  B B B  B B B  </constraint>
> B B B  B B B  B B B  </lengthy>
>
> B B B  B B B  </evaluation>
> B B B  </xsl:template>
> </xsl:stylesheet>
>
>
> Best regards
> Christoph Naber
>
> Am 22.11.2017 um 20:38 schrieb David Carlisle d.p.carlisle@xxxxxxxxx:
> > 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 >> >
>
> XSL-List info and archive <http://www.mulberrytech.com/xsl/xsl-list>
> EasyUnsubscribe <-list/2867173>
> (by email <>)

```