Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Fastest way to do permutations with replacement

by wdef2 (Acolyte)
on Apr 16, 2008 at 14:04 UTC ( #680802=perlquestion: print w/ replies, xml ) Need Help??
wdef2 has asked for the wisdom of the Perl Monks concerning the following question:

I've been assiting a co-forum member on the Damnsmalllinux forum with his project to test the hardness of his wifi key.

He was originally trying to brute force it in bash :=) and running out of memory, so some lines of Perl using the Algorithm::Permute module was a definite improvement, leaving aside for the time being that anything like this probably ought to be done in C or Assembly anyway. (In any case, the main bottleneck is the time it takes to try each perm on openssl.)

However - Algorithm::Permute does not seem to be able to properly do perms _with replacement_ - to get more than one occurence of a char in a set you have to feed it the set twice etc and you get some redundant perms output. Also, less importantly, it does not appear to be thread safe since if I write a threads implementation it segfaults (though that could be my skill level at fault!).

Algorithm::Loop looks like it can handle perms with replacement and seems to be Praised and Glorified on high by some monks:

http://search.cpan.org/~tyemq/Algorithm-Loops-1.031/lib/Algorithm/Loops.pm#Introduction

I don't think I saw any reference to thread safety and I don't know if this one is XScode.

Is Algorthm::Loops the way to go?

Comment on Fastest way to do permutations with replacement
Re: Fastest way to do permutations with replacement
by dragonchild (Archbishop) on Apr 16, 2008 at 14:49 UTC
    When you tried it, did it work? I suspect that'll be your answer.

    My criteria for good software:
    1. Does it work?
    2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?
Re: Fastest way to do permutations with replacement
by ikegami (Pope) on Apr 16, 2008 at 15:02 UTC
Re: Fastest way to do permutations with replacement
by grinder (Bishop) on Apr 16, 2008 at 15:51 UTC

    Does Algorithm::Combinatorics do what want you want? It's written in XS and thus probably one of the fastest ways of doing anything with combinations and permutations. The author has also taken care to use implementations that minimise the amount of memory required to keep track of where it is in the permutation space.

    I've used it in the past and am very happy with it. The few conversations I had with the developer led to new releases being made in a short space of time.

    • another intruder with the mooring in the heart of the Perl

      Thanks Monks for the replies. Algorithm::Combinatorics appears to do this with:

      variations_with_repetition(\@data, $k)

      which is probably the correct name for it.

      As far as a brute force cracker goes, the question then might be: is it more efficient to use Alorithm::Combinatronics in XScode and no threading, or divide the namespace into slabs for each thread of an Algorithm::Loop threaded implementation.

        Those who wish to peruse or berate my humble code as fumbling heresy may find it here:

        http://damnsmalllinux.org/cgi-bin/forums/ikonboard.cgi?act=ST&f=23&t=19676&st=60&&#entry101014

        But please send me for flagellation back here and not there, since I am the only candidate for entry to the Perlmonks novitiate in that spartan flock, almost none of whom seem to speak any of the Prophet Larry's programming language.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://680802]
Approved by kyle
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (5)
As of 2014-08-23 07:11 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (172 votes), past polls