Re: [xsl] n-tuple sequences, the constraints they must satisfy, and their XPath expressions
2017-11-24 15:26:24
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(_at_)gmail(_dot_)com:
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 (
every $item in $s/item satisfies (
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"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:math="http://www.w3.org/2005/xpath-functions/math"
exclude-result-prefixes="math">
<xsl:output method="xml" encoding="UTF-8" indent="yes"/>
<xsl:template match="/" >
<xsl:variable name="set">
<item>A</item>
<item>B</item>
</xsl:variable>
<xsl:variable name="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>
</xsl:variable>
<xsl:variable name="n" select="count($set/item)" />
<evaluation n="{$n}">
<compressed>
<xsl:comment>The total number of sequences is sum(n^k)
for k = 0 to n</xsl:comment>
<constraint no="1">
<xsl:value-of select="count($sequences/sequence)
eq sum(for $k in 0 to $n return math:pow($n, $k))" />
</constraint>
<xsl:comment>Inductional proof</xsl:comment>
<constraint no="2">
<xsl:value-of select="
every $s in $sequences/sequence[count(item) lt $n]
satisfies
every $i in $set/item satisfies
some $sequence-extended in $sequences/sequence
satisfies
deep-equal($sequence-extended/item,
($s/item, $i))" />
</constraint>
</compressed>
<lengthy>
<xsl:comment>sequence[empty(item)]</xsl:comment>
<constraint no="1">
<xsl:value-of select="every $s in
$sequences/sequence satisfies count($s/item) le $n" />
</constraint>
<xsl:comment>All sequences have a length less than or
equal to count($items)</xsl:comment>
<constraint no="2">
<xsl:value-of select="every $s in
$sequences/sequence satisfies count($s/item) le $n" />
</constraint>
<xsl:comment>The total number of sequences is sum(n^k)
for k = 0 to n</xsl:comment>
<constraint no="3">
<xsl:value-of select="count($sequences/sequence)
eq sum(for $k in 0 to $n return math:pow($n, $k))" />
</constraint>
<xsl:comment>All sequences are unique with respect to
item-type and -order</xsl:comment>
<constraint no="4">
<xsl:value-of select="every $s in
$sequences/sequence, $t in ($sequences/sequence except $s) satisfies
not(deep-equal($s, $t))" />
</constraint>
<xsl:comment>All non-empty sequences must only contain
items from the set</xsl:comment>
<constraint no="5">
<xsl:value-of select="
every $s in $sequences/sequence[item] satisfies (
every $item in $s/item satisfies (
some $i in $set/item satisfies
deep-equal($i, $item)
)
)" />
</constraint>
</lengthy>
</evaluation>
</xsl:template>
</xsl:stylesheet>
Best regards
Christoph Naber
Am 22.11.2017 um 20:38 schrieb David Carlisle
d(_dot_)p(_dot_)carlisle(_at_)gmail(_dot_)com:
> 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 <-list/2867173>
(by email <>)
--~----------------------------------------------------------------
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
--~--
|
|