[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: n-tuple sequences, the constraints they must satis

Subject: Re: n-tuple sequences, the constraints they must satisfy, and their XPath expressions
From: "Christoph Naber pentium120mhz@xxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx>
Date: Fri, 24 Nov 2017 21:26:16 -0000
Re:  n-tuple sequences
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 <>)

Current Thread

PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.