[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

RE: [xsl] Show all permutations of N coins ... without using recursion?

---

---

Jacob Mal} wrote:

>  You just iterate from 1 to 2^N, each step gives
> you one output sequence, you just have to convert
> it to the desired format.

Thank you very much!

I did as you suggested and it works great.

The below stylesheet shows the permutations of N coins, implemented in two
ways: (1) using recursion, and (2) using iteration.

By the way, I recently learned about the xsl:iterate instruction. Wow! Such a
useful instruction. How have I lived without it all these years.

-----------------------------------------------------------------------
           Show all permutations of N coins
-----------------------------------------------------------------------
<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
                xmlns:map="http://www.w3.org/2005/xpath-functions/map"
                xmlns:math="http://www.w3.org/2005/xpath-functions/math"
                xmlns:xs="http://www.w3.org/2001/XMLSchema"
                xmlns:f="function"
                version="3.0">

    <xsl:output method="text"/>

    <xsl:template match="/">
        <xsl:value-of select="f:show-coins-using-recursion(3, '')" />
        <xsl:value-of select="f:show-coins-using-iteration(3)" />
    </xsl:template>

    <xsl:function name="f:show-coins-using-iteration">
        <xsl:param name="N" as="xs:integer" />

        <xsl:for-each select="(0 to xs:integer(math:pow(2, $N) - 1))">
            <xsl:variable name="number" select="." />
            <xsl:iterate select="1 to $N">
                <xsl:param name="num" select="$number" />
                <xsl:param name="coins" select="''" />

                <xsl:variable name="coin" select="if (($num mod 2) eq 0) then
'H' else 'T'" />
                <xsl:next-iteration>
                    <xsl:with-param name="num" select="$num idiv 2" />
                    <xsl:with-param name="coins" select="concat($coins,
$coin)" />
                </xsl:next-iteration>
                <xsl:on-completion>
                    <xsl:value-of select="concat($coins, ' ')" />
                </xsl:on-completion>
            </xsl:iterate>
        </xsl:for-each>
    </xsl:function>

    <xsl:function name="f:show-coins-using-recursion">
        <xsl:param name="N" as="xs:integer" />
        <xsl:param name="coins" as="xs:string*" />

        <xsl:choose>
            <xsl:when test="$N eq 0">
                <xsl:value-of select="concat($coins, ' ')" />
            </xsl:when>
            <xsl:otherwise>
                <xsl:for-each select="('H','T')">
                    <xsl:value-of select="f:show-coins-using-recursion($N - 1,
concat($coins, .))" />
                </xsl:for-each>
            </xsl:otherwise>
        </xsl:choose>
    </xsl:function>

</xsl:stylesheet>

---