Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Re^3: One Zero variants_without_repetition

by BrowserUk (Patriarch)
on Aug 07, 2007 at 11:22 UTC ( #631016=note: print w/replies, xml ) Need Help??


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

Okay, sorry! Try this iterator then. It will handle upto 32 0s + 1s.

If you uncomment the second example it runs on a bit.

Update: Had to tweak the termination condition. It works now but I'm not happy with it.

Update2: D'oh! No need to count both 1s and 0s.

#! perl -slw use strict; sub combs { my( $ones, $zeros ) = @_; my $n = $ones+$zeros; my $max = 2**$n; my $p = 0; return sub { my $x = ''; $x = unpack "b$n", pack 'V', $p++ until $x =~ tr[1][] == $ones or $p > $max and return; return $x; } } my $iter = combs( 2, 3 ); print while $_ = $iter->(); #my $iter = combs( 14, 6 ); #print while $_ = $iter->(); __END__ C:\test>junk7 11000 10100 01100 10010 01010 00110 10001 01001 00101 00011

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Replies are listed 'Best First'.
Re^4: One Zero variants_without_repetition
by thenetfreaker (Friar) on Aug 07, 2007 at 12:06 UTC
    That's a very nice algorythm, but it's a bit slow, and 2 questions:
    1. how can i work with (much)more that 32 1's+0's ?
    2. why do i need $max to be 2**$n ? when combs(2,3) gives 10 reasults not 32 ???

    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.
      1. how can i work with (much) more that 32 1's+0's ?

      You almost certainly do not need to. It could be extended to handle 53-bits quite easily, but given that it would take the fastest algorithm in this thread ~462 years to deal with the numbers possible from that small number of bits. And as your target of 435 + 343 will take, for all intents and purposes, that number * infinity--so many times longer than the universe has existed as to be totally meaningless--you simply don't.

      One has to wonder what use, other than as another outing for Algorithm::Loops, that you thought you were going to put this to?

      Had you been dealing with reasonable numbers, I've got a specialisation of tye's nextPermute() that handles this particular problem about 3 1/2 times more quickly, but unless your name is Q, it probably won't help :)

      Update: Seems someone didn't bellieve me:

      sub combs2 { my( $z, $o ) = @_; my $str = '0'x$z . '1'x$o; my $l = length $str; return sub { my $p = 1+rindex( $str, '01' ) or return; my $r = 1+rindex( $str, '1'); my $s = 1+rindex( $str, '0', $r-1); substr( $str, $s, 0 ) = substr( $str, $r, $l-$r, '' ); my $q = index( $str, '1', $p ); substr( $str, $p-1, 1 ) = '1'; substr( $str, $q, 1 ) = '0'; $str; }; }

      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (6)
As of 2023-02-03 10:41 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    I prefer not to run the latest version of Perl because:







    Results (24 votes). Check out past polls.

    Notices?