Anonymous user
Power set: Difference between revisions
→{{header|Perl}}: Switch from HTML list to subheaders. Add two simpler module solutions. Modify some text.
(→{{header|D}}: Bonus credit) |
(→{{header|Perl}}: Switch from HTML list to subheaders. Add two simpler module solutions. Modify some text.) |
||
Line 1,725:
Perl does not have a built-in set data-type. However, you can...
=== Module: [https://metacpan.org/pod/Algorithm::Combinatorics Algorithm::Combinatorics] ===
This module has an iterator over the power set. Note that it does not enforce that the input array is a set (no duplication). If each subset is processed immediately, this has an advantage of very low memory use.
<lang perl>use Algorithm::Combinatorics "subsets";
my @S = ("a","b","c");
my @PS;
my $iter = subsets(\@S);
while (my $p = $iter->next) {
push @PS, "[@$p]"
}
say join(" ",@PS);</lang>
{{out}}
<pre>[a b c] [b c] [a c] [c] [a b] [b] [a] []</pre>
=== Module: [https://metacpan.org/pod/ntheory ntheory] ===
Similar to the Pari/GP solution, uses <tt>vecextract</tt> with an integer mask to select elements. Note that it does not enforce that the input array is a set (no duplication). This also has low memory if each subset is processed immediately. Alternately, a solution using <tt>vecreduce</tt> could be done identical to the array reduce solution shown later.
<lang perl>use ntheory "vecextract";
my @S=("a","b","c");
my @PS = map { "[".join(" ",vecextract(\@S,$_))."]" } 0..2**scalar(@S)-1;
say join(" ",@PS);</lang>
{{out}}
<pre>[] [a] [b] [a b] [c] [a c] [b c] [a b c]</pre>
=== Module: [https://metacpan.org/pod/Set::Object Set::Object] ===
The CPAN module [https://metacpan.org/pod/Set::Object Set::Object] provides a set implementation for sets of arbitrary objects, for which a powerset function could be defined and used like so:
Line 1,748 ⟶ 1,772:
<pre>Set::Object(Set::Object() Set::Object(1 2 3) Set::Object(1 2) Set::Object(1 3) Set::Object(1) Set::Object(2 3) Set::Object(2) Set::Object(3))</pre>
▲<li><p>'''''Use a simple custom hash-based set type'''''</p>
It's also easy to define a custom type for sets of strings or numbers,
Line 1,791 ⟶ 1,814:
</pre>
=== Arrays ===
If you don't actually need a proper set data-type that guarantees uniqueness of its elements, the simplest approach is to use arrays to store "sets" of items, in which case the implementation of the powerset function becomes quite short.
Line 1,823 ⟶ 1,845:
</pre>
If the initial set is quite large, constructing it's powerset all at once can consume lots of memory.
If you want to iterate through all of the elements of the powerset of a set, and don't mind each element being generated immediately before you process it, and being thrown away immediately after you're done with it, you can use vastly less memory. This is similar to the earlier solutions using the Algorithm::Combinatorics and ntheory modules.
The following algorithm uses one bit of memory for every element of the original set (technically it uses several bytes per element with current versions of Perl). This is essentially doing a <tt>vecextract</tt> operation by hand.
<lang perl>use strict;
Line 1,876 ⟶ 1,898:
</pre>
The technique shown above will work with arbitrarily large sets, and uses a trivial amount of memory.
=={{header|Perl 6}}==
| |||