Iterate over n-sized array’s permutations with O(n) space complexity.Github: https://github.com/exhesham/all_permutation_no_recurs
Github: https://github.com/exhesham/all_permutation_no_recurs
Purpose
yield next permutation in java.
Create an instance of the class AllPermsNoRec
and call the method next()
to get the next permutation.
If all the permutations were generated, a null will be returned. in order to restart the generation, call the method reset()
.
This code is thread safe using a semaphore The next()
function is not declared as synchronized
as I implemented the semaphore. I used a semaphore in order to ban a scenario where reset()
is called during next()
execution. synchronized
will not solve such scenario.
Algorithm
- calculate (n-1)!
- Clone the original string and use that string to do the swaps.
- Fix the first position(character), and swap all the k’th and (k+1)’th characters till (n-1)!.
- At the end of first (n-1)! all the (n-1)th characters will be permuted.
- Now again store the original string to the auxiliary string and swap i’th and (i+1)’th characters and repeat the 3rd and 4th process.
Benefits
Recursion is precious in space allocation. Space Complexity in the given algorithm is O(n).
Usage
AllPermsNoRec iter = new AllPermsNoRec(new Integer[]{1,2,3}); Integer[] arr; while(( arr = iter.next()) != null){ System.out.println(Arrays.toString(arr)); }