http://www.perlmonks.org?node_id=580625


in reply to Re: Powerset short-circuit optimization
in thread Powerset short-circuit optimization

jimt,
I admittedly did a poor job of explaining the nuances of this problem that make it difficult. I am going to attempt to clarify since you went through all the trouble of working on it though you may have already nailed it.

You have N files that have to be processed in a specific order. Each line in each file is a set which needs to have the powerset (minus the empty set) generated for it. Any set that has been previously seen anywhere in any file can be skipped. While the sets inside a given file can be pre-ordered in any way that would assist in optimizations, the files themselves have to be processed in a specific order.

File 1 is a list of our base sets. File 2 is a list of some base sets combined "two at a time". File 3 is a list of some base sets combined "three at a time". This process is repeated for N files. Ultimately, the powerset of the longest string in the last file will encompass every single set previously seen and should only produce a single set (itself).

File1 Output ABC A, B, C, AB, AC, BC, ABC ABD D, AD, BD, ABD AB BC E E File2 ABCE AE, BE, CE, ABE, ACE, BCE, ABCE File3 ABCDE CD, DE, ACD, ADE, BCD, BDE, CDE, ABCD, ABDE, ACDE, BCDE, +ABCDE

I hope this complete example makes it clear what I am trying to accomplish. If your code can do what I describe above, please adapt your example accordingly.

Cheers - L~R