Recipe 3.9. Computing Combinatorial Functions

Problem

You need to compute the number of permutations or combinations of size r of a given set.

Solution

XSLT 1.0

If you know the formula for permutations of size r is N! / r! and you know that the formula for combinations is N! / r! * (N-r)!, then you might disregard this example; this book already gave an example for factorial. However, since factorials get very big quickly, you need to be a little crafty to get the best bang for your calculating buck:

<xsl:template name="ckbk:P">
     <xsl:param name="n" select="1"/>
     <xsl:param name="r" select="1"/>
      <xsl:choose>
        <xsl:when test="$n &lt; 0 or $r &lt; 0">NaN</xsl:when>
        <xsl:when test="$n = 0">0</xsl:when>
        <xsl:otherwise>
               <xsl:call-template name="prod-range">
               <xsl:with-param name="start" select="$r + 1"/>
               <xsl:with-param name="end" select="$n"/>
          </xsl:call-template>
        </xsl:otherwise>
      </xsl:choose>
</xsl:template>
   
<xsl:template name="ckbk:C">
     <xsl:param name="n" select="1"/>
     <xsl:param name="r" select="1"/>
      <xsl:choose>
        <xsl:when test="$n &lt; 0 or $r &lt; 0">NaN</xsl:when>
        <xsl:when test="$n = 0">0</xsl:when>
        <xsl:otherwise>
          <xsl:variable name="min" 
               select="($r &lt;= $n - $r) * $r +  ($r > $n - $r) * $n - $r"/>
          <xsl:variable name="max" 
               select="($r >= $n - $r) * $r +  ($r &lt; $n - $r) * $n - $r"/>
          <xsl:variable name="numerator">
            <xsl:call-template name="prod-range">
                 <xsl:with-param name="start" select="$max + 1"/>
                 <xsl:with-param name="end" select="$n"/>
            </xsl:call-template>
          </xsl:variable>
          <xsl:variable name="denominator">
            <xsl:call-template name="ckbk:fact">
              <xsl:with-param name="number" select="$min"/>
            </xsl:call-template>
          </xsl:variable>
          <xsl:value-of select="$numerator div $denominator"/>
        </xsl:otherwise>
      </xsl:choose>
</xsl:template>

XSLT 2.0

<xsl:function name="ckbk:P" as="xs:decimal">
  <xsl:param name="r" as="xs:integer"/>
  <xsl:param name="n" as="xs:integer"/>
  <xsl:sequence select="if ($n eq 0) then 0 else ckbk:prod-range($r + 1, $n)"/>
</xsl:function>
   
<xsl:function name="ckbk:C" as="xs:decimal">
  <xsl:param name="r" as="xs:integer"/>
  <xsl:param name="n" as="xs:integer"/>
  <xsl:variable name="min" select="min( ($r, $n - $r) )" as="xs:integer"/>
  <xsl:variable name="max" select="max( ($r, $n - $r) )" as="xs:integer"/>
  <xsl:sequence select="if ($n eq 0) then 0 
                        else ckbk:prod-range($max + 1, $n) div 
                             ckbk:factorial($min)"/>
</xsl:function>

Discussion

The solutions are designed to reduce the number of multiplications; if you divide one factorial by a smaller factorial, then the smaller factorial effectively cancels out that many multiplications from the larger. Hence, it is better to implement such functions using prod-range (Recipe 3.5) rather than factorial. The combinatorial is slightly more complex because you want to cancel out the large of r and (n - r).