geekyOkay, ubergeek time here.
A well-known fact is that I play on TopCoder. I do so with great regularity, and enjoy the challenge- I'm not that great at the game, but it's a lot of fun.
Something I've missed more than once: something where I can give it a pile of objects (a Set or an array) and it will consecutively spit out every possible ordering of those objects. A standardized Object that makes brute force much, much simpler to implement- and makes it possible to do so iteratively, without need for dangerous levels of recursion.
I have built my masterpiece. I have built the Permutor. It is the generalized solution to the "find all permutations" problem. It runs, as it must, in factorial time, but that's because the raw size of the output increases in a factorial manner; it's as streamlined as I could make it.
Now that I've solved it, I never have to solve the problem again! The Permutor has been written- and I will never need to do it again.
Anybody curious about the source code is welcome to it- but TopCoder players, please remember that all library code must be your own. Write your own version- probably a better one. Want it for something else? Y'all are welcome to it.
It's sad. I feel like this is the biggest thing I've accomplished all month, and I am also fully aware that for most purposes, the Permutor is almost completely useless, as any brute force that runs in n! time is rarely the solution called for.
Oh, and not to gloat, but, uh, *cough* next_permutation *cough* STL *cough*
I've often thought about making my own permutor (in fact I have written non-generic ones for practice SRMs, off-line) but never got around to generalizing it. Sigh. I'd probably not know when to use it anyway.
10 seems to be the upper bound that this thing can handle within TopCoder limits. It can run through and create results for all 10! orderings of ten elements in a hair under two seconds; predictably, with factorial-order time, iterating over every result for 11 elements takes over twenty seconds.
That's assuming you do nothing with the data, of course. Each call to the Permutor is really quite speedy- it's just that there are a huge number of calls for even seemingly moderate N, as is traditional for factorial...
I suspect my whack-it-yourself version of the Permutor is nowhere near as good as C++ can come up with. Just discarding the data, how long does it take C++ to create every permutation of ten elements? Considering Java's 1813 ms. for that operation, I'd suspect somewhere around one second?
PUBLIC
Re: PUBLIC
Re: PUBLIC