20
May

## 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: xquery

September 27th, 2011 at 1:19 pm

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 [1] 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.

[1] https://www.ibm.com/developerworks/mydeveloperworks/blogs/JohnBoyer/entry/randomizing_the_responses_to_a_survey_question_in_xforms29

September 28th, 2011 at 5:27 pm

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.

August 3rd, 2012 at 11:05 am

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)

August 7th, 2012 at 2:56 pm

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