Re: Generate sequences of the permutations of a set

Hi David,

> I think you  want all non-empty sequences
> of length n using items from a set of size n?

Wonderful! That is a perfect description of what I want. I was struggling to
find the right words. You nailed it David!  /Roger

-----Original Message-----
From: David Carlisle d.p.carlisle@xxxxxxxxx
[mailto:xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx]
Sent: Saturday, November 18, 2017 2:55 PM
To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
Subject: Re:  Generate sequences of the permutations of a set

can you clarify what you mean by "permutation" here? You don't seem to be
using the normal mathematical or English meaning you would not normally
consider AAA to be a permutation of ABC?
I think you  want all non empty sequences of length n using items from a set
of size n?

On 18 November 2017 at 19:10, Costello, Roger L. costello@xxxxxxxxx
<xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote:
> Hi Folks,
>
> I want an XSLT program that generates sequences of the permutations of a
set.
>
> For example, here is a set containing 2 elements:
>
> <set>
>     <element>A</element>
>     <element>B</element>
> </set>
>
> I want the XSLT to generate these sequences:
>
> <sequences>
>     <sequence/>
>     <sequence>A</sequence>
>     <sequence>B</sequence>
>     <sequence>AA</sequence>
>     <sequence>AB</sequence>
>     <sequence>BA</sequence>
>     <sequence>BB</sequence>
> </sequences>
>
> Let's take another example. Here is a set containing 3 elements:
>
> <set>
>     <element>A</element>
>     <element>B</element>
>     <element>C</element>
> </set>
>
> I want the XSLT to generate these sequences:
>
> <sequences>
>     <sequence/>
>     <sequence>A</sequence>
>     <sequence>B</sequence>
>     <sequence>C</sequence>
>     <sequence>AA</sequence>
>     <sequence>AB</sequence>
>     <sequence>AC</sequence>
>     <sequence>BA</sequence>
>     <sequence>BB</sequence>
>     <sequence>BC</sequence>
>     <sequence>CA</sequence>
>     <sequence>CB</sequence>
>     <sequence>CC</sequence>
>     <sequence>AAA</sequence>
>     <sequence>AAB</sequence>
>     <sequence>AAC</sequence>
>     <sequence>ABA</sequence>
>     <sequence>ABB</sequence>
>     <sequence>ABC</sequence>
>     <sequence>ACA</sequence>
>     <sequence>ACB</sequence>
>     <sequence>ACC</sequence>
>     <sequence>BAA</sequence>
>     <sequence>BAB</sequence>
>     <sequence>BAC</sequence>
>     <sequence>BBA</sequence>
>     <sequence>BBB</sequence>
>     <sequence>BBC</sequence>
>     <sequence>BCA</sequence>
>     <sequence>BCB</sequence>
>     <sequence>BCC</sequence>
>     <sequence>CAA</sequence>
>     <sequence>CAB</sequence>
>     <sequence>CAC</sequence>
>     <sequence>CBA</sequence>
>     <sequence>CBB</sequence>
>     <sequence>CBC</sequence>
>     <sequence>CCA</sequence>
>     <sequence>CCB</sequence>
>     <sequence>CCC</sequence>
> </sequences>
>
> I desire all the sequences -- including the empty sequence -- of all the
permutations, up to the length of the set.
>
> I have written (below) an XSLT program to do this. But, I have two
questions:
>
> 1. Is it correct? Do you see any errors in my XSLT implementation?
>
> 2. I seek plainness and transparency over efficiency and cleverness. I
> want the XSLT to be super-super-easy to understand. It must use
> meaningful names. Can you suggest ways to make the XSLT more plain,
> more transparent, more easily understandable?  /Roger
>
> <xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
>     xmlns:xs="http://www.w3.org/2001/XMLSchema"
>     exclude-result-prefixes="xs generate"
>     xmlns:generate="function"
>     version="2.0">
>
>     <xsl:output method="xml" />
>
>     <xsl:variable name="empty" select="''" as="xs:string"/>
>     <xsl:variable name="one" select="1" as="xs:integer"/>
>     <xsl:variable name="set_elements" select="/set/element"
> as="xs:string+"/>
>
>     <xsl:template match="/">
>         <sequences>
>             <sequence/>
>             <xsl:sequence select="generate:sequences_of_length_n($empty,
$one)" />
>         </sequences>
>     </xsl:template>
>
>     <xsl:function name="generate:sequences_of_length_n"
as="element(sequence)*">
>         <xsl:param name="sequences_of_length_n_minus_1" as="xs:string*" />
>         <xsl:param name="n" as="xs:integer" />
>
>         <xsl:if test="$n le count($set_elements)">
>             <xsl:variable name="sequences_of_length_n" as="xs:string+">
>                 <xsl:for-each select="$sequences_of_length_n_minus_1">
>                     <xsl:variable name="a_sequence_of_length_n_minus_1"
select="." as="xs:string"/>
>                     <xsl:for-each select="$set_elements">
>                         <xsl:variable name="a_set_element" select="."
as="xs:string"/>
>                         <xsl:sequence
select="concat($a_sequence_of_length_n_minus_1, $a_set_element)" />
>                     </xsl:for-each>
>                 </xsl:for-each>
>             </xsl:variable>
>             <xsl:for-each select="$sequences_of_length_n">
>                 <sequence><xsl:value-of select="."/></sequence>
>             </xsl:for-each>
>             <xsl:sequence
select="generate:sequences_of_length_n($sequences_of_length_n, $n+1)" />
>         </xsl:if>
>     </xsl:function>
> </xsl:stylesheet>