Permutation in XSLT

Question

I'm sure the answer is going to be some sort of 'recursion' I'm struggling to get quite there though -- for a set of nodes, I want to return all their permutations:

Input:

<animals>       
            <animal>Rabbit</animal>
            <animal>Turtle</animal>
            <animal>Moose</animal>
    </animals>

Desired output:

MooseRabbitTurtle
MooseTurtleRabbit
RabbitMooseTurtle
RabbitTurtleMoose
TurtleMooseRabbit
TurtleRabbitMoose

Note the alphabetical sorting, but if that's not possible, I can live without it. Also, there won't always be 3 input nodes, so ideally it'd work with any number of nodes

Thanks for any pointing in the right directions!

Answer 1

Here is an example XSLT 2.0 stylesheet

<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:xs="http://www.w3.org/2001/XMLSchema"
    xmlns:mf="http://example.com/mf"
    exclude-result-prefixes="xs mf"
    version="2.0">

    <xsl:output indent="yes"/>

    <xsl:function name="mf:permute" as="item()*">
        <xsl:param name="head" as="item()*"/>
        <xsl:param name="tail" as="item()*"/>
        <xsl:choose>
            <xsl:when test="count($tail) eq 1">
                <permutation>
                    <xsl:for-each select="$head, $tail">
                        <item>
                            <xsl:value-of select="."/>
                        </item>
                    </xsl:for-each>
                </permutation>
            </xsl:when>
            <xsl:otherwise>
                <xsl:sequence select="for $pos in (1 to count($tail)) return mf:permute(($head, $tail[$pos]), $tail[position() ne $pos])"/>
            </xsl:otherwise>
        </xsl:choose>
    </xsl:function>

    <xsl:function name="mf:permutations" as="element(permutations)">
        <xsl:param name="input" as="item()*"/>
        <permutations>
            <xsl:sequence select="for $pos in (1 to count($input)) return mf:permute($input[$pos], $input[position() ne $pos])"/>
        </permutations>
    </xsl:function>

    <xsl:template match="animals">
        <xsl:variable name="sorted-animals" as="element(animal)*">
            <xsl:perform-sort select="animal">
                <xsl:sort select="."/>
            </xsl:perform-sort>
        </xsl:variable>
        <xsl:copy-of select="mf:permutations($sorted-animals)"/>
    </xsl:template>

</xsl:stylesheet>

that transforms the input

<animals>       
    <animal>Rabbit</animal>
    <animal>Turtle</animal>
    <animal>Moose</animal>
</animals>

into the output

<permutations>
   <permutation>
      <item>Moose</item>
      <item>Rabbit</item>
      <item>Turtle</item>
   </permutation>
   <permutation>
      <item>Moose</item>
      <item>Turtle</item>
      <item>Rabbit</item>
   </permutation>
   <permutation>
      <item>Rabbit</item>
      <item>Moose</item>
      <item>Turtle</item>
   </permutation>
   <permutation>
      <item>Rabbit</item>
      <item>Turtle</item>
      <item>Moose</item>
   </permutation>
   <permutation>
      <item>Turtle</item>
      <item>Moose</item>
      <item>Rabbit</item>
   </permutation>
   <permutation>
      <item>Turtle</item>
      <item>Rabbit</item>
      <item>Moose</item>
   </permutation>
</permutations>

The function mf:permutations takes the input sequence (which can be sorted as shown before passing it to the function) and then computes the for each item in the sequence the possible permutations of the sequence formed by the item and a recursive call passing the sequence except the item.

With XSLT 3.0 as supported by Saxon 9.7 we could shorten the code and return a sequence of arrays instead of an XML structure with the permutations:

<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:xs="http://www.w3.org/2001/XMLSchema"
    xmlns:math="http://www.w3.org/2005/xpath-functions/math"
    xmlns:array="http://www.w3.org/2005/xpath-functions/array"
    xmlns:mf="http://example.com/mf"
    exclude-result-prefixes="xs math array mf"
    version="3.0">

    <xsl:output method="adaptive"/>

    <xsl:function name="mf:permute" as="array(*)*">
        <xsl:param name="head" as="array(*)"/>
        <xsl:param name="tail" as="item()*"/>
        <xsl:sequence select="if (count($tail) eq 1)
                              then array:append($head, $tail)
                              else for $pos in (1 to count($tail)) return mf:permute(array:append($head, $tail[$pos]), $tail[position() ne $pos])"/>
    </xsl:function>

    <xsl:function name="mf:permutations" as="array(*)*">
        <xsl:param name="input" as="xs:untypedAtomic*"/>
        <xsl:sequence select="mf:permute([], $input)"/>     
    </xsl:function>

    <xsl:template match="animals">
        <xsl:sequence select="mf:permutations(sort(animal))"/>
    </xsl:template>

</xsl:stylesheet>

That way the result is

["Moose","Rabbit","Turtle"]
["Moose","Turtle","Rabbit"]
["Rabbit","Moose","Turtle"]
["Rabbit","Turtle","Moose"]
["Turtle","Moose","Rabbit"]
["Turtle","Rabbit","Moose"]