Combinatorics in Power Query -part1

Super User

11 months ago

Apologies on the necro, but I recently needed to generate combinations and came across this page, which I found very helpful. I came up with yet another technique and sharing below for anyone interested. On some quick testing, this performed a little better among the PQ options above.

Combos

let
    fx = 
    (L as list, optional listCombineFunc as function) as list =>
    [
        Lb = List.Buffer(L),
        Lpos = List.Positions(L),
        Lrpt = List.Reverse( Lpos ),
        pattern = List.Transform( Lpos, each 
            List.Repeat( 
                List.Repeat( {null}, Number.Power(2,_) ) & 
                List.Repeat( {Lb{_}}, Number.Power(2,_) ),
                Number.Power(2,Lrpt{_})
            ) 
        ),
        combine = List.Zip( pattern ),
        applyFunc = 
            if listCombineFunc = null 
            then List.Transform(combine, List.RemoveNulls ) 
            else List.Transform(combine, each listCombineFunc( List.RemoveNulls(_) ) )
    ] [applyFunc]
in
    fx

Invoke examples:

Sample (0-19 series, N=20, 2^20 >1m combos)

let
    Source = List.Generate(()=>0, each _ < 20, each _+1 )
in
    Source

Invoke example 1:

let
    Source = Sample,
    GetCombos = Combos( Source )
in
    GetCombos

Invoke example 2 (using optional function param):

let
    Source = Sample,
    GetAndConcatCombos = Combos( Source, each Text.Combine( List.Transform(_, Text.From), "|" ) )
in
    GetAndConcatCombos

Quick explanation

Rather than iterate through the combinations (akin to going through each "row" of the table of combos and accessing list 0-N times), we build column by column using List.Repeat on a single value, cutting down on iterations and access on original list. Leveraging the same pattern used by the math of the other approaches.

(on = x, off = o)

Item Position	0	1	2	3	...	N - 1
on/off group size	2^0 = 1	2^1 = 2	2^2 = 4	2^3 = 8	...	2^(N - 1)
pattern repeats	2^(N - 1)	2^(N - 2)	2^(N - 3)	2^(N - 4)	...	2^0

1	o	o	o	o		o
2	x	o	o	o		o
3	o	x	o	o		.
4	x	x	o	o		.
5	o	o	x	o		.
6	x	o	x	o		.
7	o	x	x	o		o
8	x	x	x	o		o
9	o	o	o	x		2^N-1th o
10	x	o	o	x		x
11	o	x	o	x		x
12	x	x	o	x		.
13	o	o	x	x		.
14	x	o	x	x		.
15	o	x	x	x		.
16	x	x	x	x		x
...						x
2^N						2^N-1th x

Note that List.Repeat only supports Int32, so the max N that this function can handle is 31. Technically, you can switch out List.Repeat with List.Generate to try to compute N>31, but it's not as performant and you're already over 2b combos at N=31, so not recommended.

Blog Post