|Just another Perl shrine|
Generating powerset with progressive orderingby Limbic~Region (Chancellor)
|on Feb 25, 2005 at 15:36 UTC||Need Help??|
Limbic~Region has asked for the
wisdom of the Perl Monks concerning the following question:
I am trying to improve my solution to this problem by incorporating the shortcuts I outlined here. This requires ordering the powerset of prime factors in some sort of progressive order:
In this simple example, the number is 210 so any factor larger than 14 need not be considered. This means that after checking 2*3*5, we can skip 2*3*5*7 and after we check 3*5, we can skip 3*5*7.
Additional savings can be found if the primes repeat since it will lead to duplicate subsets. Prior to determining the product of the subset, we can easily determine if we have already seen this subset and skip. If this previously seen subset was also too large, we can skip the entire progression.
Anyone have any ideas about how to implement this?
Cheers - L~R
Update: You can see the result of this exercise here