Fastest way to do permutations with replacement

[wdef2]

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?

[grinder]

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.

[wdef2]

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.

[wdef2]

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.

[ikegami]

Algorithm::Loops is pure Perl (no XS) and thread-safe.

[dragonchild]

When you tried it, did it work? I suspect that'll be your answer.