Analysis of Permutation Finder algorithm(pseudo code)

Question

A SO post about generating all the permutations got me thinking about a few alternative approaches. I was thinking about using space/run-time trade offs and was wondering if people could critique this approach and possible hiccups while trying to implement it in C#.

The steps goes as follows:

1. Given a data-structure of homogeneous elements, count the number of elements in the structure.

2. Assuming the permutation consists of all the elements of the structure, calculate the factorial of the value from Step 1.

3. Instantiate a newer structure(Dictionary) of type <key(Somehashofcollection),Collection<data-structure of homogeneous elements>> and initialize a counter.

4. Hash(???) the seed structure from step 1, and insert the key/value pair of hash and collection into the Dictionary. Increment the counter by 1.

5. Randomly shuffle(???) the order of the seed structure, hash it and then try to insert it into the Dictionary from step 3.

6. If there is a conflict in hashes,repeat step 5 again to get a new order and hash and check for conflict. Upon successful insertion increment the counter by 1.

7. Repeat steps 5 & 6 until the counter equals the factorial calculated in step 2.

It seems like doing it this way using some sort of randomizer(which is a black box to me at the moment) might help with getting all the permutations within a decent timeframe for datasets of obscene sizes.

It will be great to get some feedback from the great minds of SO to further analyze this approach whose objective is to deviate from the traditional brute-force approach prevalent in algorithms of such nature and also the repercussions of implementing such an algorithm using C#.

Thanks

Answer 1

It seems like a complicated way to randomise the order of the generated permutations. In terms of time efficiency, you can't do much better than the 'brute force' approach.

Answer 2

This method of generating all permutations does not fare well as compared to the standard known methods.

Say you had n items and M=n! permutations.

This method of generation is expected to generate M*lnM permutations before discovering all M.

(See this answer for a possible explanation: http://stackoverflow.com/questions/3282832/programing-pearls-random-select-algorithm/3282949#3282949)

Also, what would the hash function be? For a reasonable hash function, we might have to start dealing with very large integer issues pretty soon (any n > 50 for sure, don't remember that exact cut-off point).

This method uses up a lot of memory too (the hashtable of all permutations).

Even assuming the hash is perfect, this method would take expected Omega(n*M*logM) operations and guaranteed Omega(nM) space, while standard well-known methods can do it in O(M) time and O(n) space.

As a starting point I suggest one can read: Systematic Generation of All Permutations which is believe is O(nM) time and O(n) space and still much better than this method.

Note that if one has to generate all permutations, any algorithm will necessarily take Omega(M) steps and so the the method I refer to above is optimal!