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:

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

  1. John Boyer Says:
    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

  2. Dave Cassel Says:
    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.

  3. Bob Starbird Says:
    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)

  4. Vineet George Says:
    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

Leave a Reply