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)); }