Anonymous user
Power set: Difference between revisions
→{{header|Perl}}: actually provide what the task description asks for
(Updated second D entry) |
(→{{header|Perl}}: actually provide what the task description asks for) |
||
Line 1,510:
=={{header|Perl}}==
Perl does not have a built-in set data-type. However, you can...
<ul>
<li><p>'''''Use a third-party module'''''</p>
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:
<lang perl>use Set::Object qw(set);
sub powerset {
my $p = Set::Object->new( set() );
foreach my $i (shift->elements) {
$p->insert( map { set($_->elements, $i) } $p->elements );
}
return $p;
}
my $set = set(1, 2, 3);
my $powerset = powerset($set);
print $powerset->as_string, "\n";</lang>
Output:
<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>
<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, using a hash as the underlying representation (like the task description suggests):
<lang perl>package Set {
sub new { bless { map {$_ => undef} @_[1..$#_] }, shift; }
sub elements { sort keys %{shift()} }
sub as_string { 'Set(' . join(' ', sort keys %{shift()}) . ')' }
# ...more set methods could be defined here...
}</lang>
''(Note: For a ready-to-use module that uses this approach, and comes with all the standard set methods that you would expect, see the CPAN module [https://metacpan.org/pod/Set::Tiny Set::Tiny])''
The limitation of this approach is that only primitive strings/numbers are allowed as hash keys in Perl, so a Set of Set's cannot be represented, and the return value of our powerset function will thus have to be a ''list'' of sets rather than being a Set object itself.
We could implement the function as an imperative foreach loop similar to the <code>Set::Object</code> based solution above, but using list folding (with the help of Perl's <code>List::Util</code> core module) seems a little more elegant in this case:
<lang perl>use List::Util qw(reduce);
sub powerset {
@{( reduce { [@$a, map { Set->new($_->elements, $b) } @$a ] }
[Set->new()], shift->elements )};
}
my $set = Set->new(1, 2, 3);
my @subsets = powerset($set);
print $_->as_string, "\n" for @subsets;</lang>
Output:
<pre>
Set()
Set(1)
Set(2)
Set(1 2)
Set(3)
Set(1 3)
Set(2 3)
Set(1 2 3)
</pre>
</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.
Recursive solution:
<lang perl>sub powerset {
@_ ? map { $_, [$_[0], @$_] } powerset(@_[1..$#_]) : [];
Line 1,521 ⟶ 1,591:
sub powerset {
@{
}</lang>
Usage
<lang perl>my @set = (1, 2, 3);
my @powerset = powerset(@set);
sub set_to_string {
"{" . join(", ", map { ref $_ ? set_to_string(@$_) : $_ } @_) . "}"
}
print set_to_string(@powerset), "\n";</lang>
<pre>
{{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}}
</pre>
</li>
</ul>
=={{header|Perl 6}}==
| |||