Power set: Difference between revisions

1,406 bytes added ,  9 years ago
→‎{{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...
 
<ul>
=== Module: [https://metacpan.org/pod/Algorithm::Combinatorics Algorithm::Combinatorics] ===
<li><p>'''''Use a third-party module'''''</p>
 
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 simpleSimple custom hash-based set type'''''</p> ===
</li>
<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 ===
</li>
<li><p>'''''Use arrays'''''</p>
 
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>
 
<li><p>'''''Use=== lazyLazy evaluation'''''</p> ===
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.
 
</li>
</ul>
 
=={{header|Perl 6}}==
Anonymous user