Generate the Power Set of any given input Set

Hi everyone,

I have created a nested iterative macro that runs through all the combinations for the set of records.

I'm needing to scale the workflow and the only thing preventing that is I haven't found a way to generate all the subsets of the input set automatically. I'm currently using static data of all the subsets of a set of 9 elements (as I've never run into an instance where there are more than that many records for one iteration) and joining only the subsets that would apply, then looping through those combinations.

So, If I input 4 records, how can I auto-generate the subsets of that set, [1,2,3,4]?

Attached is how I'm currently tackling it.

Thanks!

Power_Set_Problem.yxmd

Datasets

Macros

Iterative Macro

Accepted answers

danilang

Hi @Trevor_Nordberg

Here's a different take on the problem based on the fact that the power set of U items is equivalent to the binary representation of all the integers to 2^U that have n bits set. All the combinations of n=1 item is the same as the set of all the integers with only a single bit=1 in the binary representation, the set 2 items = all number with 2 bits set, etc.

The main workflow generates all the integers, builds a binary representation as a string and then counts the number of 1 bits in the string. It also reverses the representation string, so the combos come out in numerical(as much as possible) order

The first filter in the iterative macro separates the integers where the number of 1 bits equals the iteration number. The others are sent back to the next iteration. The rest of tools in the top branch splits each integer to digits, adds an order, keeps only the 1 bits and concats the combo.

Since there are no joins, crosstabs or other expensive tools, the workflow runs very quickly, taking only 14 seconds to generate all 1048575(the null group isn't returned) unique combinations of a universe of 20 items. With only 4 items, it runs in under 0.1 seconds and looks like this

It's theoretically limited to a maximum universe of 63 items since that's all that will fit into a 64-bit int. The practical limit will be hit before then as the run time increases exponentially

Dan

PowerSet.yxzp

All comments

Qiu

@Trevor_Nordberg
I feel it must have beter solution, since it cost quite a bit amount time to calculate 9 records, almost 1 hour.
for 4 records, just less than one second though.

Power_Set_Problem-r1.yxzp

danilang

Hi @Trevor_Nordberg

It's theoretically limited to a maximum universe of 63 items since that's all that will fit into a 64-bit int. The practical limit will be hit before then as the run time increases exponentially

Dan

PowerSet.yxzp

Trevor_Nordberg

Wow! This is exactly what I needed.

Dan, your solution runs almost immediately. Incredible.

I can't thank you both enough for taking your time on this.

Quick Links

This months top contributors

atcodedog05 19458

Qiu 15866

binu_acs 15708

MarqueeCrew 13708

apathetichell 13703