Subject: [xsl] Randomizing a node-list -- long (Was: Re: Extending xsltproc?) From: Dimitre Novatchev <dnovatchev@xxxxxxxxx> Date: Fri, 3 May 2002 04:01:17 -0700 (PDT) |
> > 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
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] For Loop in XSLT, Mike Brown | Thread | [xsl] foreign keys in a xml-databas, ChivaBaba |
[xsl] For Loop in XSLT, Bagchi Ratul | Date | Re: [xsl] For Loop in XSLT, Jeni Tennison |
Month |