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
            if (math:fmod($shifted, 2) eq 1) then
            else ()
        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.


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

  1. John Boyer Says:

    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.


  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:

    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])
    for $i in ($l to ($n – $m))
    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’)
    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

Leave a Reply