Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??

Late to the party and, not only that, but wearing the same outfit as some (see ambrus's link above). I think the best answer for you is toolic's. My answer that follows just fills in a few conceptual details for you about the Power Set, illustrated by two functions that do the job two different ways.

Earlier, I had copied this problem to my notepad and had misremembered your question as being about a string, "ABCD", rather than an array of elements. So both functions take in a string and return a list of strings. This makes my answer slightly different from the others in the recursive case and bulky in the enumeration case.

Power Set

Given a set, A, the set of all subsets of elements of A is called the power set of A, here denoted P(A). A power set, P(A), of finite set A has size 2N. So your example should have 16 results. (Note, one of those subsets is the empty set / empty string). Finding all combinations of elements of a set is an equivalent notion.

Power sets get very big, very fast, so in general you don't see many applications for power sets unless you are writing advertisements for how many ways customers can put condiments on their hamburgers. If this question is motivated by a real-world problem (i.e., one that doesn't get a grade) it would be interesting to some of us if you could post some details about it.

recursion

The first function, rpow, shows the recursive solution and its map block indicates that the results of the recursed function call are doubled, hence you can see how the 2N subsets are built up.

#!/usr/bin/env perl use Modern::Perl; sub rpow { my ($p, $q) = $_[0] =~ /(.)(.*)/; return $_[0] ? map { ($p.$_, $_) } rpow ($q) : ''; } say join ("\n", rpow 'ABCD');

enumeration

The second function, bpow, is a direct enumeration of the power set by using the on/off nature of a bit in the binary representation of a number as a representation for the in/out selection of an element of A for a given element of P(A). That is, it runs a bit-mask of each non-negative integer less than 2N against your string. It produces the same results as rpow (in reverse order).

#!/usr/bin/env perl use Modern::Perl; sub bpow { map { my $m = unpack("b*", pack("i*",$_)); $m =~ s/0/\0/g; $m =~ s/1/~"\0"/ge; $m & $_[0]; } 0..2**length($_[0])-1 } say join ("\n", bpow 'ABCD');

In reply to Re: Combinations of array? by jaredor
in thread Combinations of array? by dagwood00

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others contemplating the Monastery: (7)
    As of 2020-07-14 10:09 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      No recent polls found

      Notices?