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" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx>
Date: Thu, 23 Nov 2017 23:00:37 -0000
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 >> > 

Current Thread