Subject: Re: [xsl] All combinations from a sequence From: "Michael Kay mike@xxxxxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> Date: Thu, 30 Sep 2021 14:37:27 -0000 |
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 -> |
---|---|---|
[xsl] All combinations from a seque, Michael Müller-Hille | Thread | Re: [xsl] All combinations from a s, Michael Müller-Hille |
[xsl] All combinations from a seque, Michael Müller-Hille | Date | Re: [xsl] All combinations from a s, Michael Müller-Hille |
Month |