Re: [xsl] All combinations from a sequence

["Michael Müller-Hillebrand mmh@xxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx>]

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