Re: [xsl] All combinations from a sequence

I think the recursive version is easier to read than using idiv and
math:pow something like

<xsl:stylesheet version="3.0"
        xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
        xmlns:xs="http://www.w3.org/2001/XMLSchema";
        xmlns:my="data:,my"
        >

 <xsl:function name="my:powerset" as="xs:string*">
    <xsl:param name="seq" as="xs:string*"/>
     <xsl:sequence select="if(exists($seq)) then
     (let $z:= my:powerset(tail($seq)) return
          ($z,for $i in $z return concat(head($seq),$i)))
     else ''
    "/>

  </xsl:function>

<xsl:template name="main">
<xsl:message select="my:powerset(('A','B','C','D'))"/>
</xsl:template>

</xsl:stylesheet>


$ saxon9 -it:main ps.xsl
 D C CD B BD BC BCD A AD AC ACD AB ABD ABC ABCD


David

On Thu, 30 Sept 2021 at 20:29, Michael Müller-Hillebrand 
mmh(_at_)docufy(_dot_)de
<xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com> wrote:
> Thanks a lot, Michael Kay, just what I needed!
>
> After a bit of thinking and just for handling a sequence of strings I came up 
> with this:
>
>   <xsl:function name="my:powerset" as="xs:string*">
>     <xsl:param name="seq" as="xs:string+"/>
>     <xsl:variable name="N" select="count($seq)" as="xs:integer"/>
>     <xsl:sequence select="
>     for $i in 0 to xs:integer(math:pow(2, $N)) - 1
>     return string-join(
>       for $j in 1 to $N
>       return (
>         if ($i idiv math:pow(2, $j -1) mod 2 eq 1)
>           then $seq[$j]
>           else ()
>           )
>       , '')
>     "/>
>   </xsl:function>
>
> No recursion necessary, and not too difficult to follow.
>
> my:powerset(('A','B','C','D')) creates: '', 'A', 'B', 'AB', 'C', 'AC', 'BC', 
> 'ABC', 'D', 'AD', 'BD', 'ABD', 'CD', 'ACD', 'BCD', 'ABCD'
>
> Best regards,
>
> - Michael Müller-Hillebrand
>
>
> > Am 30.09.2021 um 16:37 schrieb Michael Kay mike(_at_)saxonica(_dot_)com 
> > <xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com>:
> >
> > There's a nice algorithm here
> >
> > https://www.geeksforgeeks.org/power-set/
> >
> > which abstracts to
> >
> > for $i in 1 to math:pow(2, count($input))
> > return combination($i)
> >
> > where combination($i) includes or excludes each $input[$N] depending on 
> > whether bit $N is set in $i, which you can determine using bin:shift() from 
> > the EXPath binary module.
> >
> > Michael Kay
> >
> > > On 30 Sep 2021, at 15:20, Michael Müller-Hillebrand 
> > > mmh(_at_)docufy(_dot_)de 
> > > <xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com> wrote:
> > >
> > > Good afternoon,
> > >
> > > I have a sequence of items and I need all combinations (not permutations) 
> > > in all possible lengths.
> > >
> > > I saw what I want described as "powerset" in the Python docs: 
> > > powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)
> > >
> > > In XPath notation and based on strings:
> > >
> > > my:powerset(('A','B','C','D'))
> > >
> > > This sequence of 4 items should result in a sequence of 16 strings (order 
> > > not important) representing all possible combinations: 'ABCD', 'ABC', 
> > > 'ABD', 'ACD', 'AB', 'AC', 'AD', 'A', 'BCD', 'BC', 'BD', 'B', 'CD', 'C', 
> > > 'D', ''
> > >
> > > Or more general, the result could be an array of sequences.
> > >
> > > To get this as a solution in XSLT/XPath I am currently fiddling around 
> > > with a recursive function including head() and tail() and count() but I 
> > > have the impression I am overcomplicating things.
> > >
> > > I am wondering, if this is a use case for fold-left() or if I should 
> > > rather think of a filter that drops 0, 1, 2 or 3 items from the sequence. 
> > > Or is there a well-known algorithm with a cool name?
> > >
> > > Any hints are, as always, very welcome, thanks a lot,
> > >
> > > - Michael
--~----------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
EasyUnsubscribe: http://lists.mulberrytech.com/unsub/xsl-list/1167547
or by email: xsl-list-unsub(_at_)lists(_dot_)mulberrytech(_dot_)com
--~--