## Calling a function on the power set of a sequence

Author: Dave Cassel  |  Category: Software Development

[Update: This post was originally labelled “Calling a function on all permutations of a sequence”. John Boyer was kind enough to point out that the function works for power sets rather than permutations, so I’ve updated this post accordingly. Thanks, John!]

A project I’m working on required me to call a function on the power set of a sequence. I said to myself, “Surely, you can’t be the only person needing to do that in XQuery”. Having heard that from such a reliable source, I figured I should share.

```(: Print an index and the selected members of the sequence. :)
declare function local:print(\$index, \$values, \$selections, \$connector) {
fn:concat(\$index, ": ", fn:string-join(\$values[\$selections], \$connector))
};

(: Apply the specified function to each permutation of \$seq. \$data is
: provided as a pass-through.
:)
declare function local:apply-on-power-set(\$seq as item()*,
\$function as xdmp:function, \$data)
{
let \$len := fn:count(\$seq)
for \$i in (1 to xs:int(math:pow(2, \$len) - 1))
let \$targets :=
for \$bit in (1 to \$len)
let \$shifted :=
if (\$bit > 1) then
xs:int(\$i div (math:pow(2, \$bit - 1)))
else \$i
return
if (math:fmod(\$shifted, 2) eq 1) then
\$bit
else ()
return
xdmp:apply(\$function, \$i, \$seq, \$targets, \$data)
};

let \$seq := ('a', 'b', 'c', 'd')
return local:apply-on-power-set(\$seq, xdmp:function(xs:QName("local:print")), ',')```

Calling this function generates this output:

```1: a
2: b
3: a,b
4: c
5: a,c
6: b,c
7: a,b,c
8: d
9: a,d
10: b,d
11: a,b,d
12: c,d
13: a,c,d
14: b,c,d
15: a,b,c,d```

I’m sure you’ll sleep better tonight knowing that this is available to you.

Tags:

### 4 Responses to “Calling a function on the power set of a sequence”

1. John Boyer Says:

Hi,
These aren’t permutations. You’re generating the power set of a set (less the null set).
There are 4!=24 permutations of {a, b, c, d}. Lexicographically, they are (a b c d), (a b d c), (a c b d), … (d c a b), (d c b a).
The blog entry below  explains how to generate a permutation in XForms, but also contains information on how to generate a permutation in general, which you could perhaps provide the xquery version of. If you do, please leave a comment on my blog so I’ll know to read about it.

2. Dave Cassel Says:

John, thanks for your comment. I stand corrected — this code does generate power sets, as you say. That is the problem I was trying to solve; I mislabeled it. I’ll try to set aside some time to update the post to use the correct terminology.

3. Bob Starbird Says:

Dave,
I struggled with creating a function to generate combinations but not in xquery. Here is what I ended up with to get distinct combinations of length 3 out of 5 in a sequence. I can be modified to generate just the indexes of the sequence if the sequence is large.

declare function local:do_comb(\$l, \$n, \$m, \$el_lst, \$seq) {
if (\$m = 0) then
(
“-“,
for \$i in fn:reverse(\$el_lst)
return (\$seq[\$i])
)
else
for \$i in (\$l to (\$n – \$m))
return
local:do_comb(\$i + 1, \$n, \$m – 1, (\$i+1, \$el_lst), \$seq)
};

declare function local:comb(\$n, \$m, \$seq) {
local:do_comb(0, \$n, \$m, (), \$seq)
};

let \$seq := (‘a’,’b’,’c’,’d’,’e’)
return
local:comb(fn:count(\$seq), 3, \$seq)

4. Vineet George Says:

I have found a convinient method of generating permutation, to see it then log on to the site https://sites.google.com/site/junctionslpresentation/home