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: 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 <>)
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] n-tuple sequences, the co, Christoph Naber pent | Thread | [xsl] [ANN] Reminder: XML Prague 20, Jirka Kosek jirka@xx |
Re: [xsl] n-tuple sequences, the co, Christoph Naber pent | Date | |
Month |