This is the mail archive of the
xsl-list@mulberrytech.com
mailing list .
Randomizing a node-list -- long (Was: Re: Extending xsltproc?)
- From: Dimitre Novatchev <dnovatchev at yahoo dot com>
- To: garym at canada dot com, xsl-list at lists dot mulberrytech dot com, exslt at lists dot fourthought dot com
- Date: Fri, 3 May 2002 04:01:17 -0700 (PDT)
- Subject: [xsl] Randomizing a node-list -- long (Was: Re: Extending xsltproc?)
- Reply-to: xsl-list at lists dot mulberrytech dot com
> > Then again, maybe I don't need to extend it. The two transforms I
> > would like to implement seem easy and commonplace, but are proving
> > elusive: I would like to render a node-set into rows of columns
> > without resorting to disable-output-escaping to insert the
> > modulo-column </tr><tr> break, and I'd also like to be able to
> present
> > a node-set in a new random order on each call. If either of these
> > effects can be done directly with xsltproc, I'll be one happy
> camper.
>
> The first one is a FAQ and you can find it in many places, just these
> days there was one at TopXML.com (sure, you don't need DOE at all,
> <tr>
> is a node, not just string). I also remember doing one at the time
> that
> combined creating a multi-column table with adding alternating
> colours
> to the rows -- could find it if this would be useful.
>
> For the second request -- see my article "Casting the Dice with FXSL:
> Random Number Generation Functions in XSLT" at:
>
> http://www.topxml.com/xsl/articles/dice/default.asp
I am pleased to present a complete solution for the problem of
producing and processing randomized node-sets or node-lists (random
indices). This is a XSLT 1.0 solution and can be used immediately
The code bellow is a complete, new module of FXSL, named
randomList.xsl. It should be put in the same folder, where all other
FXSL files reside.
It imports and uses random.xsl.
The main functions/templates are:
1. randomizeList -- given a node-set and an optional seed produces a
new node-set, having nodes with the same values as the given node-set,
but ordered randomly.
2. randomMap -- given a function f, a node-set and an optional seed, it
produces a mapping of the given function f over the nodes of the
node-set, which is applied in a random order, based on the given seed.
It is efficient, because no intermediate randomized list is produced.
3. randListIndex -- given a node-set and an optional seed produces a
random index (a random permutation of the numbers from 1 to
count($node-set). This index can then be used e.g. in a xsl:for-each
loop to index randomly the elements of any node-set with the same
number of nodes.
The basic idea standing behind a list randomisation is to follow the
algorithm of producing a permutation of N elements -- that is to
produce one random number out of N in the first stage, then to produce
one random number out of the remaining N-1, etc...
Actually, a random sequence of N random numbers is produced, and its
elements are then individually scaled, so that its k-th element is in
the interval [1, N-k+1]
Bellow is the complete FXSL module:
randomList.xsl
--------------
<!--
=======================================================================
Stylesheet: random.xsl List Randomization Functions
Version: 1.0 (2002-05-03)
Author: Dimitre Novatchev
Notice: Copyright (c)2002 D.Novatchev ALL RIGHTS RESERVED.
No limitation on use - except this code may not be
published, in whole or in part, without prior written
consent of the copyright owner.
=====================================================================-->
<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:vendor="urn:schemas-microsoft-com:xslt"
xmlns:myIncrement="f:myIncrement"
xmlns:x="f:fxslRandomList.xsl"
exclude-result-prefixes="xsl vendor myIncrement x"
>
<!--
========================================================================
Imported files:
=====================================================================-->
<xsl:import href="random.xsl"/>
<!--
Template: randScale
Purpose : Return an integer, scaled from [0, modulus-1]
to [s, t]
Parameters:
$pStart - [optional] the start of the target interval
$pEnd - [optional] the end of the target interval
$pN - The number N to be scaled
============================================================-->
<!--
> _randScale :: Float -> Float -> Int -> Int
> randScale s t n = floor (rndScl ((t - s + 1)/dintRange ) s n)
> where dintRange = fromInt (modulus - 1)
> rndScl :: Float -> Float -> Int -> Float
> rndScl a b n = a * fromInt n + b
-->
<xsl:template name="_randScale" >
<xsl:param name="arg2" select="0"/> <!--pStart-->
<xsl:param name="arg3" select="1"/> <!--pEnd -->
<xsl:param name="arg1"/> <!--pN -->
<xsl:value-of
select="floor( ($arg3 - $arg2 + 1) div ($modulus - 1)
* $arg1
+ $arg2
)"/>
</xsl:template>
<!--
Template: _dScale
Purpose : Used to prepare a random recursive index
for a list from a random sequence with the
same number of elements
Parameters:
$pRandSeq - a list of (random) numbers
Result: - a random recursive index
=========================================================-->
<xsl:template name="_dScale">
<xsl:param name="pRandSeq" select="/.."/>
<!--
> dScale :: [Int] -> [Int]
> dScale [] = []
> dScale (x:xs) = fstScale : (dScale xs)
> where fstScale = randScale 0 (fromInt (length xs)) x
-->
<xsl:if test="$pRandSeq">
<el>
<xsl:call-template name="_randScale">
<xsl:with-param name="arg2" select="1"/> <!--s-->
<xsl:with-param name="arg3"
select="count($pRandSeq)"/> <!--end-->
<xsl:with-param name="arg1" select="$pRandSeq[1]"/>
</xsl:call-template>
</el>
<xsl:call-template name="_dScale">
<xsl:with-param name="pRandSeq"
select="$pRandSeq[position() > 1]"/>
</xsl:call-template>
</xsl:if>
</xsl:template>
<!--
Template: _randomRecursiveIndex
Purpose : Used to prepare a random recursive index
for a list
Parameters:
$pList - a list to be presented in a random order
$pSeed - [optional] a seed for generation of the
random sequence
Result: - a random recursive index
=========================================================-->
<!--
> randomRecursiveIndex xs sd
= dScale (take (length xs) (randomSequence sd))
-->
<xsl:template name="_randomRecursiveIndex">
<xsl:param name="pList" select="/.."/>
<xsl:param name="pSeed" select="$seed"/>
<xsl:variable name="vRandSequence">
<xsl:call-template name="randomSequence">
<xsl:with-param name="pLength" select="count($pList)"/>
<xsl:with-param name="pSeed" select="$pSeed"/>
</xsl:call-template>
</xsl:variable>
<xsl:call-template name="_dScale">
<xsl:with-param name="pRandSeq"
select="vendor:node-set($vRandSequence)/*"/>
</xsl:call-template>
</xsl:template>
<!--
Template: _permutationFromRecursiveIndex
Purpose : Produce a random permutation of a list
based on a given random recursive index
Parameters:
$pList - a list to be presented in a random order
$pIndex - a list with the same length as $pList
containing the random recursive index
Result: - a randomly permuted list
=========================================================-->
<xsl:template name="_permutationFromRecursiveIndex">
<xsl:param name="pList" select="/.."/>
<xsl:param name="pRecIndex" select="/.."/>
<xsl:if test="not(count($pList) = count($pRecIndex))">
<xsl:message terminate="yes">
Error[permutationFromRecursiveIndex]:
The two lists are not the same length!
</xsl:message>
</xsl:if>
<xsl:call-template name="_permRecIdx">
<xsl:with-param name="pList" select="$pList"/>
<xsl:with-param name="pRecIndex" select="$pRecIndex"/>
</xsl:call-template>
</xsl:template>
<xsl:template name="_permRecIdx">
<xsl:param name="pList" select="/.."/>
<xsl:param name="pRecIndex" select="/.."/>
<xsl:variable name="vIndex"
select="number($pRecIndex[1])"/>
<xsl:if test="$pList">
<el>
<xsl:value-of
select="$pList[position() = $vIndex]"/>
</el>
<xsl:call-template name="_permRecIdx">
<xsl:with-param name="pList"
select="$pList[position() != $vIndex]"/>
<xsl:with-param name="pRecIndex"
select="$pRecIndex[position() > 1]"/>
</xsl:call-template>
</xsl:if>
</xsl:template>
<!--
Template: randomizeList
Purpose : Produce a random permutation of a list
based on a given seed for randomisation
Parameters:
$pList - a list to be reproduced in a random order
$pSeed - [optional] the seed to be used
=========================================================-->
<xsl:template name="randomizeList">
<xsl:param name="pList" select="/.."/>
<xsl:param name="pSeed" select="$seed"/>
<xsl:variable name="vrtfRecIndex">
<xsl:call-template name="_randomRecursiveIndex">
<xsl:with-param name="pList" select="$pList"/>
<xsl:with-param name="pSeed" select="$pSeed"/>
</xsl:call-template>
</xsl:variable>
<xsl:variable name="vRecIndex"
select="vendor:node-set($vrtfRecIndex)/*"/>
<xsl:call-template name="_permutationFromRecursiveIndex">
<xsl:with-param name="pList" select="$pList"/>
<xsl:with-param name="pRecIndex" select="$vRecIndex"/>
</xsl:call-template>
</xsl:template>
<!--
Template: _mapFromRandIndex
Purpose : Produce a mapping of a given function
over a list, which will be applied randomly
based on a given random recursive index
Parameters:
$pFun - a template reference to a function
$pList - a list to be processed in a random order
$pIndex - a list with the same length as $pList
containing the random recursive index
Result: - a mapping of pFun applied in random order
(specified by pIndex) on pList
=========================================================-->
<xsl:template name="_mapFromRandIndex">
<xsl:param name="pFun" select="/.."/>
<xsl:param name="pList" select="/.."/>
<xsl:param name="pRecIndex" select="/.."/>
<xsl:if test="not(count($pList) = count($pRecIndex))">
<xsl:message terminate="yes">
Error[mapFromRandIndex]:
The two lists are not the same length!
</xsl:message>
</xsl:if>
<xsl:call-template name="_mapRndIndex">
<xsl:with-param name="pFun" select="$pFun"/>
<xsl:with-param name="pList" select="$pList"/>
<xsl:with-param name="pRecIndex" select="$pRecIndex"/>
</xsl:call-template>
</xsl:template>
<xsl:template name="_mapRndIndex">
<xsl:param name="pFun" select="/.."/>
<xsl:param name="pList" select="/.."/>
<xsl:param name="pRecIndex" select="/.."/>
<xsl:variable name="vIndex"
select="number($pRecIndex[1])"/>
<xsl:if test="$pList">
<el>
<xsl:apply-templates select="$pFun">
<xsl:with-param name="arg1"
select="$pList[position() = $vIndex]"/>
</xsl:apply-templates>
</el>
<xsl:call-template name="_mapRndIndex">
<xsl:with-param name="pFun" select="$pFun"/>
<xsl:with-param name="pList"
select="$pList[position() != $vIndex]"/>
<xsl:with-param name="pRecIndex"
select="$pRecIndex[position() > 1]"/>
</xsl:call-template>
</xsl:if>
</xsl:template>
<!--
Template: randomMap
Purpose : Produce a mapping of a given function
over a list, which will be applied randomly
based on a given seed for randomization
Parameters:
$pFun - a template reference to a function
$pList - a list to be processed in a random order
$pSeed - [optional] the seed to be used
for randomization
=========================================================-->
<xsl:template name="randomMap">
<xsl:param name="pFun" select="/.."/>
<xsl:param name="pList" select="/.."/>
<xsl:param name="pSeed" select="$seed"/>
<xsl:variable name="vrtfRecIndex">
<xsl:call-template name="_randomRecursiveIndex">
<xsl:with-param name="pList" select="$pList"/>
<xsl:with-param name="pSeed" select="$pSeed"/>
</xsl:call-template>
</xsl:variable>
<xsl:variable name="vRecIndex"
select="vendor:node-set($vrtfRecIndex)/*"/>
<xsl:call-template name="_mapFromRandIndex">
<xsl:with-param name="pFun" select="$pFun"/>
<xsl:with-param name="pList" select="$pList"/>
<xsl:with-param name="pRecIndex" select="$vRecIndex"/>
</xsl:call-template>
</xsl:template>
<!--
Template: randListIndex
Purpose : Produce a random (non-recursive)
index for a list
Parameters:
$pList - the list for which to
produce a random index
$pSeed - [optional] the seed to be used
for randomization
=========================================================-->
<xsl:template name="randListIndex">
<xsl:param name="pList" select="/.."/>
<xsl:param name="pSeed" select="$seed"/>
<xsl:variable name="vFunIncr"
select="$x:st/myIncrement:*[1]"/>
<xsl:variable name="vrtfNums">
<xsl:call-template name="scanIter">
<xsl:with-param name="arg1" select="count($pList) - 1"/>
<xsl:with-param name="arg2" select="$vFunIncr"/>
<xsl:with-param name="arg3" select="'1'"/>
</xsl:call-template>
</xsl:variable>
<xsl:call-template name="randomizeList">
<xsl:with-param name="pList"
select="vendor:node-set($vrtfNums)/*"/>
<xsl:with-param name="pSeed" select="$pSeed"/>
</xsl:call-template>
</xsl:template>
<xsl:template match="myIncrement:*">
<xsl:param name="arg1"/>
<xsl:value-of select="$arg1 + 1"/>
</xsl:template>
<!-- *************************************************************
-->
<!-- ********************* INTERNAL USE ONLY *********************
-->
<!-- *************************************************************
-->
<!-- defined constants -->
<xsl:variable name="x:st" select="document('')/*"/>
<!--
a template reference to an incrementing function
================================================================== -->
<myIncrement:myIncrement/>
</xsl:stylesheet>
And here's a test of the functions of this module:
testListRandomizer.xslt:
-----------------------
<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:vendor="urn:schemas-microsoft-com:xslt"
xmlns:mySquare="f:mySquare"
xmlns:myDouble="f:myDouble"
exclude-result-prefixes="xsl vendor mySquare myDouble"
>
<xsl:import href="randomList.xsl"/>
<xsl:output omit-xml-declaration="yes" indent="yes"/>
<!-- This transformation must be applied to:
numList.xml
-->
<mySquare:mySquare/>
<myDouble:myDouble/>
<xsl:template match="/">
<xsl:variable name="vrtfRands">
<xsl:call-template name="randomSequence">
<xsl:with-param name="pLength" select="100"/>
</xsl:call-template>
</xsl:variable>
Random Recursive Index (dScale (randomSequence 100)):
<xsl:call-template name="_dScale">
<xsl:with-param name="pRandSeq"
select="vendor:node-set($vrtfRands)/*"/>
</xsl:call-template>
Random Recursive Index 10:
<xsl:variable name="vrtfRecIndex">
<xsl:call-template name="_randomRecursiveIndex">
<xsl:with-param name="pList"
select="/*/*"/>
</xsl:call-template>
</xsl:variable>
<xsl:variable name="vRecIndex"
select="vendor:node-set($vrtfRecIndex)/*"/>
<xsl:for-each select="$vRecIndex">
<xsl:copy-of select="."/>
</xsl:for-each>
Randomized 10-elements list:
<xsl:call-template name="_permutationFromRecursiveIndex">
<xsl:with-param name="pList" select="/*/*"/>
<xsl:with-param name="pRecIndex" select="$vRecIndex"/>
</xsl:call-template>
RandomizeList:
<xsl:call-template name="randomizeList">
<xsl:with-param name="pList" select="/*/*"/>
</xsl:call-template>
<xsl:variable name="vFunSquare"
select="document('')/*/mySquare:*[1]"/>
_mapFromRandIndex (^2) [1..10] seed:
<xsl:call-template name="_mapFromRandIndex">
<xsl:with-param name="pFun" select="$vFunSquare"/>
<xsl:with-param name="pList" select="/*/*"/>
<xsl:with-param name="pRecIndex" select="$vRecIndex"/>
</xsl:call-template>
<xsl:variable name="vFunDouble"
select="document('')/*/myDouble:*[1]"/>
randomMap (*2) [1..10] seed:
<xsl:call-template name="randomMap">
<xsl:with-param name="pFun" select="$vFunDouble"/>
<xsl:with-param name="pList" select="/*/*"/>
</xsl:call-template>
randListIndex [1..10] seed:
<xsl:call-template name="randListIndex">
<xsl:with-param name="pList" select="/*/*"/>
</xsl:call-template>
</xsl:template>
<xsl:template match="mySquare:*">
<xsl:param name="arg1"/>
<xsl:value-of select="$arg1 * $arg1"/>
</xsl:template>
<xsl:template match="myDouble:*">
<xsl:param name="arg1"/>
<xsl:value-of select="$arg1 + $arg1"/>
</xsl:template>
</xsl:stylesheet>
When applied to the following source xml document:
numList.xml
-----------
<nums>
<num>01</num>
<num>02</num>
<num>03</num>
<num>04</num>
<num>05</num>
<num>06</num>
<num>07</num>
<num>08</num>
<num>09</num>
<num>10</num>
</nums>
the result is:
Random Recursive Index (dScale (randomSequence 100)):
<el>27</el>
<el>90</el>
<el>14</el>
<el>78</el>
<el>65</el>
<el>13</el>
<el>27</el>
<el>85</el>
<el>75</el>
<el>33</el>
<el>31</el>
<el>26</el>
<el>9</el>
<el>40</el>
<el>31</el>
<el>80</el>
<el>19</el>
<el>44</el>
<el>52</el>
<el>7</el>
<el>8</el>
<el>73</el>
<el>55</el>
<el>16</el>
<el>68</el>
<el>20</el>
<el>29</el>
<el>4</el>
<el>3</el>
<el>30</el>
<el>51</el>
<el>41</el>
<el>14</el>
<el>32</el>
<el>66</el>
<el>4</el>
<el>19</el>
<el>51</el>
<el>48</el>
<el>59</el>
<el>30</el>
<el>1</el>
<el>49</el>
<el>57</el>
<el>14</el>
<el>53</el>
<el>13</el>
<el>10</el>
<el>10</el>
<el>38</el>
<el>13</el>
<el>37</el>
<el>13</el>
<el>36</el>
<el>22</el>
<el>7</el>
<el>28</el>
<el>25</el>
<el>28</el>
<el>7</el>
<el>29</el>
<el>3</el>
<el>34</el>
<el>28</el>
<el>7</el>
<el>13</el>
<el>14</el>
<el>5</el>
<el>32</el>
<el>25</el>
<el>25</el>
<el>24</el>
<el>8</el>
<el>26</el>
<el>23</el>
<el>14</el>
<el>11</el>
<el>18</el>
<el>15</el>
<el>6</el>
<el>5</el>
<el>6</el>
<el>9</el>
<el>4</el>
<el>8</el>
<el>14</el>
<el>12</el>
<el>12</el>
<el>5</el>
<el>2</el>
<el>5</el>
<el>1</el>
<el>4</el>
<el>1</el>
<el>4</el>
<el>4</el>
<el>1</el>
<el>2</el>
<el>1</el>
<el>1</el>
Random Recursive Index 10:
<el>3</el>
<el>9</el>
<el>2</el>
<el>6</el>
<el>5</el>
<el>1</el>
<el>2</el>
<el>3</el>
<el>2</el>
<el>1</el>
Randomized 10-elements list:
<el>03</el>
<el>10</el>
<el>02</el>
<el>08</el>
<el>07</el>
<el>01</el>
<el>05</el>
<el>09</el>
<el>06</el>
<el>04</el>
RandomizeList:
<el>03</el>
<el>10</el>
<el>02</el>
<el>08</el>
<el>07</el>
<el>01</el>
<el>05</el>
<el>09</el>
<el>06</el>
<el>04</el>
_mapFromRandIndex (^2) [1..10] seed:
<el>9</el>
<el>100</el>
<el>4</el>
<el>64</el>
<el>49</el>
<el>1</el>
<el>25</el>
<el>81</el>
<el>36</el>
<el>16</el>
randomMap (*2) [1..10] seed:
<el>6</el>
<el>20</el>
<el>4</el>
<el>16</el>
<el>14</el>
<el>2</el>
<el>10</el>
<el>18</el>
<el>12</el>
<el>8</el>
randListIndex [1..10] seed:
<el>3</el>
<el>10</el>
<el>2</el>
<el>8</el>
<el>7</el>
<el>1</el>
<el>5</el>
<el>9</el>
<el>6</el>
<el>4</el>
Cheers,
Dimitre Novatchev.
__________________________________________________
Do You Yahoo!?
Yahoo! Health - your guide to health and wellness
http://health.yahoo.com
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list