Kombinatorische Funktionen berechnen

(Auszug aus "XSLT Kochbuch" von Sal Mangano)

Problem

Sie müssen die Anzahl der Permutationen oder Kombinationen der Größe r einer gegebenen Menge berechnen.

Lösung

XSLT 1.0

Falls Sie wissen, dass die Formel für Permutationen der Größe r gleich N! / r! ist und die Formel für Kombinationen N! / r! * (N-r)! lautet, werden Sie dieses Beispiel möglicherweise weglassen, da es in diesem Buch bereits ein Beispiel für die Fakultät gab. Da Fakultäten allerdings schnell sehr groß werden können, brauchen Sie wahrscheinlich ein paar Tricks, um das Beste aus Ihren Berechnungen herauszuholen:

<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 &gt; $n - $r) * $n - $r"/>
      <xsl:variable name="max" select="($r &gt;= $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>

Diskussion

Die Lösungen sind so gestaltet, dass die Anzahl der Multiplikationen verringert wird; falls Sie eine Fakultät durch eine kleinere Fakultät teilen, dann streicht die kleinere Fakultät praktisch entsprechend viele Multiplikationen aus der größeren. Daher ist es besser, solche Funktionen mit Hilfe von prod-range (siehe das Rezept Gebräuchliche mathematische Funktionen implementieren) zu implementieren anstatt mit Fakultäten. Die kombinatorische Funktion ist etwas komplexer, da Sie einen Großteil von r und (n – r) aufheben wollen.

  

<< zurück vor >>

 

 

 

Tipp der data2type-Redaktion:
Zum Thema XSLT bieten wir auch folgende Schulungen zur Vertiefung und professionellen Fortbildung an:

Copyright © 2006 O'Reilly Verlag GmbH & Co. KG
Für Ihren privaten Gebrauch dürfen Sie die Online-Version ausdrucken.
Ansonsten unterliegt dieses Kapitel aus dem Buch "XSLT Kochbuch" denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.

O'Reilly Verlag GmbH & Co. KG, Balthasarstraße 81, 50670 Köln, kommentar(at)oreilly.de