Algorithm for finding permutations of subsets in lexicographic order, no recursion

Here are the steps:

To find permutations, in lexicographic order:

1. Sort the list of items and print this as the first permutation

2. Let i be the last index such that `input[i] < input[i+1]` (if no such index, we are done)

3. Let j be the last index such that `input[i] < input[j]`

4. Swap `input[i]` with `input[j]`

5. Reverse `input[i+1]` through `input[input.length-1]`

Example

Pass the flag "CHARLES"

First permutation is sorted: ACEHLRS

Second string is ACEHLSR

Third string is ACEHRLS

etc.

Code

the main method/test

```import java.io.*;
import java.util.*;

class Oops extends ArrayIndexOutOfBoundsException {}

public class StringPermutations {

public static void main(String[] args) {
String theString = "CHARLES";
System.out.println(permutations.size());
}

```

utility methods

Had to implement two utility methods:

```	public static void swap(char[] input, int i, int j) {
char t = input[i];
input[i] = input[j];
input[j] = t;
}

public static void reverseFrom(char[] input, int startIndex) {
// prolly shoulda used a stack.

int len = input.length;
int n = len - startIndex - 1;
// if n odd, ignores middle index
// if n even, swaps exactly half
for(int k=0; k<(n/2); k++) {
int ix = startIndex + k;
int jx = len-1-k;
swap(input,ix,jx);
}
}
```

Core algorithm

Finally, the core swapping algorithm, applied to char arrays:

```	public static LinkedQueue<String> stringPermutations(String s_input) {

// Save useful info
int n = s_input.length();

char[] input = s_input.toCharArray();
Arrays.sort(input);

// First is sorted string
q.enqueue(new String(input));

boolean done = false;

try {

// Loop until we reach end
while(!done) {
// Step 1:
// let i be the last index such that input[i] < input[i+1]
// (if no such index, i=0 and we are done)
int i = -1;
for(int k=0; k<(n-1); k++) {
if(input[k] < input[k+1]) {
i = k;
}
}
if(i<0) {
// No such index, we are done
done = true;
break;
}

// Step 2:
// let j be the last index such that input[i] < input[j]
int j = -1;
for(int k=i+1; k<n; k++) {
if(input[i] < input[k]) {
j = k;
}
}

// Step 3:
// swap i and j
swap(input,i,j);

// Step 4:
// reverse i+1 thru length-1
reverseFrom(input, i+1);

q.enqueue(new String(input));
}

} catch(ArrayIndexOutOfBoundsException e) {
System.out.println("OOPSIE");
}
return q;
}
}

```