Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

Re: Combinatorics

by bart (Canon)
on Aug 22, 2002 at 09:12 UTC ( [id://191960]=note: print w/replies, xml ) Need Help??


in reply to Combinatorics

Ah, a twist. The common question is about permutations.

Nevertheless, I'd still use recursion. Say you need $n elements. Is the first element included? If yes, combine it with all combinations of $n-1 elements from the list of all of the following elements. If no, get all combinations of $n elements of the same sublist. Of course, you need to include every possible solution, which means walking every possible path.

Code!

sub combinations { my $n = shift; return [@_] if $n == @_; return () if $n > @_ or $n < 0; my $first = shift; my @r = ((map [ $first, @$_ ], combinations($n-1, @_)), combinations($n, @_)); return @r; } use Data::Dumper; print Dumper [ combinations(2, (0, 1, 2, 3)) ];

It appears to be working well.

Update: I'm pretty sure inserting

return [] if $n == 0;
at the appropriate place, i.e. among the other return statements near the top, will improve efficiency quite a bit. It avoids doing a lot of useless recursion if all you want is the empty list as a singleton.

Replies are listed 'Best First'.
Re^2: Combinatorics
by Aristotle (Chancellor) on Aug 22, 2002 at 10:38 UTC
    Yes, it will. In fact you can cut down on the amount of useless processing further by replacing all those returns with return map [$_], @_ if $n == 1; and then you have the equivalent to the code I wrote, except passing around full lists rather than just an arrayref.

    Makeshifts last the longest.

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others goofing around in the Monastery: (3)
As of 2024-03-29 15:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found