Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical

Golf: Selection from sets (Choose)

by knobunc (Pilgrim)
on May 24, 2001 at 21:30 UTC ( #83013=perlmeditation: print w/replies, xml ) Need Help??

Since there was just a golf for factorials, I figured that doing one for the number of ways to select M objects from a set of N objects without repetition might be appropriate.

Basically, if I have a set of 4 cards, how many ways can I select a hand of 1 card from the set without repeating myself? The answer is obviously 4. Now if I have a hand size of 2 how many ways are there? The answer is 6, but it is less obvious.

The general solution is defined by the function:

Choose(M, N) = M! ---------------- N! * (M - N)!
Where M is the size of the set and N is the number of cards to select. And M! is the factorial of M. See Golf: Factorials for more info.

The following are test cases that you can use:
5252598960Number of 5 card hands in a deck of 52 cards
527133784560Number of 7 card hands in a deck of 52 cards
5213635013559600Number of 7 card hands in a deck of 52 cards
52521Number of ways to select a hand size of 1 from a 52 card deck

The interface for the resulting code should be:

print c($m, $n);

If you want to define a factorial subroutine that should be included in the size of the code.


Replies are listed 'Best First'.
Re: Golf: Selection from sets (Choose)
by no_slogan (Deacon) on May 25, 2001 at 00:42 UTC
    46 characters, passes strict and -w. I wouldn't suggest running it with that sample data without Memoize, unless you have a lot of time to kill.
    sub c{ my($m,$n)=@_;$n?$m?c($m-1,$n)+c($m-1,$n-1):0:1 }

    Update: We can squeeze a couple more characters out of that...

    sub c{ my($m,$n)=@_;$n?$m--?c($m,$n)+c($m,$n-1):0:1 }
Re: Golf: Selection from sets (Choose)
by knobunc (Pilgrim) on May 24, 2001 at 21:56 UTC

    My best is 74 chars (including newlines and sub c{}:
    sub c{f($_[0],$_[0]-$_[1]+1) / f($_[1],1)} sub f{eval join'*',$_[1]..$_[0]}

    Take 2 (66 chars including both subs and newlines, 50 chars for just the sub bodies):
    sub c{f($_[0]-$_[1]+1..$_[0])/f(1..$_[1])} sub f{eval join'*',@_}


Re: Golf: Selection from sets (Choose)
by srawls (Friar) on May 24, 2001 at 22:44 UTC
    55 chars (see update), not counting the sub subName parts.
    sub a{ eval join'*',1..pop } sub f { a($_[0])/(a($_[1])*a($_[0]-$_[1])) }

    Update: changed code a bit, down to 53 characters now

    The 15 year old, freshman programmer,
    Stephen Rawls

      It is usual when counting helper subroutines to count the declaration of the helper in the overall length. So your code is of length 60.

      Incidentally here is another reasonably efficient one to compute of length 53. Mainly interesting because it works on a different principle.

      sub c{ my@c=1;map$c[$_]+=$c[$_-1],1..$_[1]for 1..$_[0];pop@c }
Re: Golf: Selection from sets (Choose)
by jynx (Priest) on May 25, 2001 at 01:11 UTC

    i'm posting this just to show some different code. The methodolgy doesn't use factorials per se, just lists of numbers. There are probably some ways to optimize, but i don't have enough time to really try right now.
    sub c{ my($c,$d)=@_;my%n=map{$_=>1}1..$c;delete$n{$_}for 1..($c-$d); eval join'/',map"($_)",(join'*',keys%n),(join'*',1..$d) }
    It's warnings and strict compliant, and returns all the right answers.

    nuf evah,

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://83013]
Approved by root
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (3)
As of 2017-10-19 05:44 GMT
Find Nodes?
    Voting Booth?
    My fridge is mostly full of:

    Results (251 votes). Check out past polls.