Subject: Re: [xsl] All combinations from a sequence From: "David Carlisle d.p.carlisle@xxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> Date: Thu, 30 Sep 2021 20:19:27 -0000 |
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 MC<ller-Hillebrand mmh@xxxxxxxxx <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> 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 MC<ller-Hillebrand > > > > Am 30.09.2021 um 16:37 schrieb Michael Kay mike@xxxxxxxxxxxx <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx>: > > > > 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 MC<ller-Hillebrand mmh@xxxxxxxxx <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> 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
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] All combinations from a s, Michael Müller-Hille | Thread | |
Re: [xsl] All combinations from a s, Michael Müller-Hille | Date | |
Month |