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

Re^4: One Zero variants_without_repetition

by thenetfreaker (Friar)
on Aug 07, 2007 at 11:58 UTC ( [id://631022]=note: print w/replies, xml ) Need Help??


in reply to Re^3: One Zero variants_without_repetition
in thread One Zero variants_without_repetition

That's nice, but it goes through the factorial of $ones+$zeroes, 5!=120.. 120 != 10.
i'm working with strings of 435 zeroes and 343 ones (for instance), where i'm in dought i'll live that long to see it finish.

i need this sub{} to play with the strings that contain that number of 1's and 0's, not the numbers that contain them.
  • Comment on Re^4: One Zero variants_without_repetition

Replies are listed 'Best First'.
Re^5: One Zero variants_without_repetition
by ohcamacj (Beadle) on Aug 08, 2007 at 02:59 UTC
    With 435 zeroes and 343 ones, you'll never live long enough to see it finish, regardless of the method used to generate the sequence. A simple way to figure out how many permutations a list will generate is with
    my $num_zeros = 3; my $num_ones = 2; use Math::BigInt; sub fac { my $result = Math::BigInt->new("1"); my $n = Math::BigInt->new(shift()); while($n){ $result *= $n--; } return $result; } my $num_permutations = fac($num_ones + $num_zeros ) / (fac($num_ones) +* fac($num_zeros)); print("Number of permutations of a ($num_zeros, $num_ones) list is $nu +m_permutations\n");'
    A list with 453 zeros and 343 ones will have roughly 1.962e230 different permutations -- are you sure you need all of them?

      I like this way of computing it better, for several mostly unimportant reasons. :)

      #!/usr/bin/perl -w use strict; print countPairPermutations( @ARGV ), $/; sub countPairPermutations { my( $x, $y )= @_; ( $x, $y )= ( $y, $x ) if $y < $x; my $log= 0; for my $i ( 1 .. $x ) { $log += log( $y+$i ) - log( $i ); } my $exp= int( $log / log(10) ); my $mant= exp( $log - log(10)*$exp ); $mant= sprintf "%.*f", 6 < $exp ? 3 : 8, $mant; $mant .= $exp ? "e" . $exp : ""; return $mant if 6 < $exp; return 0 + $mant; }

      My code appears to agree with your code (though I didn't count the number of digits output by your code) but they both disagree with your node, reporting that there are 5.807e234 different permutations (not 1.962e230).

      Update: Or, using my prototype module:

      #!/usr/bin/perl -w use strict; require Math::BigPositiveOkayPrecision; print countPairPermutations( @ARGV ), $/; sub countPairPermutations { my( $x, $y )= @_; ( $x, $y )= ( $y, $x ) if $y < $x; my $p= Math::BigPositiveOkayPrecision->new( 1 ); for my $i ( 1 .. $x ) { $p= $p * ( $y+$i ) / $i; } return $p; }

      - tye        

Re^5: One Zero variants_without_repetition
by GrandFather (Saint) on Aug 07, 2007 at 21:03 UTC

    Perhaps if you told us what you were trying to achieve we might understand what it is that you actually need. Up to now every time someone suggests a new solution you have introduced a new requirement.

    Tell us what you need this for and what the constraints are on the input parameters and what the requirements are for the output.

    A fairly trivial change to the recursive code I gave will change it to work with a string of characters rather than a "string" of bits. You would still run into deep recursion issues with large numbers of ones and other solutions are likely to be faster (memory constraints on recursion are unlikely to be a factor though) however.


    DWIM is Perl's answer to Gödel

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others scrutinizing the Monastery: (6)
As of 2024-04-16 17:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found