Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

nCr arrays of size r

by PsychoSpunk (Hermit)
on Apr 18, 2001 at 10:12 UTC ( [id://73440]=perlquestion: print w/replies, xml ) Need Help??

PsychoSpunk has asked for the wisdom of the Perl Monks concerning the following question:

I am working on a problem where I calculate the result of nCr given n,r. n is the length of an array and r is the remaining length of a second array (ex: @t = (4,5,6,x,x,x) where x is an available spot).

What I want to do is take every combination of nCr and place those into separate arrays. So, using the above example @t and @array = (10,11,12,13,14), I want to get the 10 arrays from combining @t and @array with regards to 5C3. I can see this as a recursive solution, but I haven't wrapped my mind around the actual solution. Ideally, the solution will allow for nC1 and nCn cases. Anyway, I'm going to give it a stab after I get some sleep, but I would like to see other ideas as well.

Note: This is for a toy project at home. All would be homework denouncers can make mental note that I have been out of school for over a year now. It occurred to me that this is rather homeworky, so I figured that I'd be better off on getting real answers if I made this statement from the beginning. Thanks.

ALL HAIL BRAK!!!

Replies are listed 'Best First'.
(tye)Re: nCr arrays of size r
by tye (Sage) on Apr 18, 2001 at 17:12 UTC

    Being a mathematician by training, I chose to reduce this to two problems I have already solved (Permuting with duplicates and no memory and mapcar -- map for more than one list):

    use mapcar; sub nCr { my( $r, @n )= @_; die "Usage: nCr($r,@n)" if @n < $r; my @pick= ( (0)x(@n-$r), (1)x$r ); my @c; do { push @c, [mapcar{$_[0]?$_[1]:()}\@pick,\@n]; } while( nextpermute( @pick ) ); return \@c; } for( @{nCr(@ARGV)} ) { print "[ ",join(", ",@$_)," ]\n"; } __END__ > nCr 2 a b c [ b, c ] [ a, c ] [ a, b ]
    And, yes, it works for nC0 and nCn.

            - tye (but my friends call me "Tye")
Re: nCr arrays of size r
by larsen (Parson) on Apr 18, 2001 at 14:41 UTC
Re (tilly) 1: nCr arrays of size r
by tilly (Archbishop) on Apr 18, 2001 at 18:32 UTC
    Allow me to add the (inefficient) recursive solution that you were looking for.

    Writing recursion is 2 tricks together. The first is to take a problem and break it into one or more simpler problems. The other is to figure out the simple problems that you will come to and make them special cases.

    So in this case what do we want? We want a function that takes a number (m) and an array of n things, and returns all of the possible choices of m things from the list. Well we can make this simpler by deciding whether or not to choose the first element. That will reduce n, and possibly m as well, which has to be simpler.

    Now what simple problems can we come down to? Well we could get down to needing no elements. In which case there is one list of no elements. Or we could get down to a situation where our list is shorter than the number we want, in which case we have no answers.

    So we wind up with this:

    # Takes a number and a list of elements. Returns all possible ways to # select that number out of the list. sub choose_m { my $m = shift; # Special cases first if (0 == $m) { return []; } elsif (@_ < $m) { return (); } else { # This is our recursion step my $first = shift; return ( # Things without the first element choose_m($m, @_), # Things with the first element map {[$first, @$_]} choose_m($m - 1, @_) ); } }
    Now a warning on recursion. Recursive problems where you make a *pair* of recursive calls (like this one) open you up to processing an exponential amount of data, or even returning that. (Certainly the case here!) This should be a danger flag, and when you reach for this you should either be willing to pay a very steep price, or you should know why in your situation it won't be a problem.

    Try to write an iterative and a recursive solution to calculating Fibonacci numbers, see which is faster. Likewise Perl's RE engine uses recursion, if you look around you will find some discussions of the possible problems that result. And in this case, well try to list 30 choose 15 things, see what happens to your memory... :-)

Re: nCr arrays of size r
by jeroenes (Priest) on Apr 18, 2001 at 14:47 UTC
    While you claim this to be a non-homework question, I would categorize as homework nevertheless, because you didn't provide any code to start with. You also did not take the trouble to super search on permutations. That would be a good starting point.

    To help you on the road: have a look at this. To whack up a first solution, take only the first r items of the permutations, and filter out the duplicates.

    Hope this help,

    Jeroen
    "We are not alone"(FZ)

      jeroenes as a side thread, if I had said that I was trying to implement a CGI parsing routine, someone would undoubtedly point me to use CGI;. I admit that I didn't search for permutations, because I didn't think of it (however, I did do some searching on similar topics as my little project). I did recall some discussion from the CB on similar subjects and, for lack of a useful search term, I figured this SoPW would get me a good answer (with either a link or code such as tye provided). So, instead of poorly reinventing the wheel, I asked my fellow wheelmakers for an appropriate wheel.

      So while I can fully see your point of view (as I CBed), I think that it would be remiss of me to not request an answer, considering the purpose of SoPW and PerlMonks itself. Or has the purpose of PerlMonks been perverted from this style of question? Not to be snide, but can you point me to that change in the Need Help?? or Perl Monks FAQ?

      My goal isn't to solve all of this toy project myself, but to simply finish it. If that involves requests for code (noting that this is my first such request, and happens to be the last thing I need to finish the current instantiation), then I think such questions are well within the nature of PerlMonks and SoPW.

      Note: This is not an attack on your reply, I found your link to be useful. It is simply a response to the homework statement and my own interpretation of what SoPW is supposed to be for. I just wanted to address an issue that I think I tried to avoid initially.

      ALL HAIL BRAK!!!

        PsychoSpunk I can see your point, and thank you for softening your statement in CB ;-). Of course you are free to request some code in a SoPW, naturellement. And I think we are here to help others, at least, that's my opinion. But too often there are people here who ask and expect others to solve their problems, and they clearly do so trying to minimize the effort from their side. Well, that is not polite.

        I don't think you mean to be rude, (neither do I) but simply a statement like 'this is no homework' doesn't help much (IMHO). You better state something like: I've had some discussion about this in CB, but I wouldn't know where to search for in Supersearch, etc etc...

        If I had such a question, I would simply ask it in CB, and very soon I would have got some links were to look for. But that's me.

        So, feel free to post anything you want here. SoPW is meant for such questions. It's merely the attitude of the posting I responded to, and I think just a little difference in the style/approach could have made your post somewhat politer. But again, that's just me. I know it is fairly easy to be misinterpreted when it comes to the intention of a posting.... I made some errors in that direction myself.

        Cheers,

        Jeroen
        "We are not alone"(FZ)

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://73440]
Approved by root
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others imbibing at the Monastery: (4)
As of 2024-03-29 07:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found