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!!!
(tye)Re: nCr arrays of size r
by tye (Sage) on Apr 18, 2001 at 17:12 UTC
|
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") | [reply] [Watch: Dir/Any] [d/l] |
Re: nCr arrays of size r
by larsen (Parson) on Apr 18, 2001 at 14:41 UTC
|
| [reply] [Watch: Dir/Any] |
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... :-) | [reply] [Watch: Dir/Any] [d/l] |
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) | [reply] [Watch: Dir/Any] |
|
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!!!
| [reply] [Watch: Dir/Any] [d/l] |
|
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)
| [reply] [Watch: Dir/Any] |
|
|