StacksQueues/Subsets/Java - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:55:41Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:55, 9 October 2019
Line 29:		Line 29:
	==Code==		==Code==

	See https://charlesreid1.com~~:3000~~/cs/java/src/master/stacks-queues-deques/subset/StringPermutations.java		See https://git.charlesreid1.com/cs/java/src/master/stacks-queues-deques/subset/StringPermutations.java

	===the main method/test===		===the main method/test===

Admin: /* Code */

2017-06-04T18:47:02Z

Code

← Older revision		Revision as of 18:47, 4 June 2017
Line 29:		Line 29:
	==Code==		==Code==

			See https://charlesreid1.com:3000/cs/java/src/master/stacks-queues-deques/subset/StringPermutations.java

			===the main method/test===

			<pre>
			import java.io.*;
			import java.util.*;

			class Oops extends ArrayIndexOutOfBoundsException {}

			public class StringPermutations {

			public static void main(String[] args) {
			// Start with strings, then move to generics
			String theString = "CHARLES";
			LinkedQueue<String> permutations = stringPermutations(thestring);
			System.out.println(permutations.size());
			}

			</pre>

			===utility methods===

			Had to implement two utility methods:

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


			===Core algorithm===

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

			<pre>
			public static LinkedQueue<String> stringPermutations(String s_input) {
			LinkedQueue<String> q = new LinkedQueue<String>();

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

			</pre>

	==Flags==		==Flags==

Admin: /* =Flags */

2017-06-04T18:45:08Z

=Flags

← Older revision		Revision as of 18:45, 4 June 2017
Line 32:		Line 32:


	==Flags=		==Flags==

	[[Category:Stacks]]		[[Category:Stacks]]

Admin: Created page with "==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..."

2017-06-04T18:44:24Z

Created page with "==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..."

New page

==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 <code>input[i] < input[i+1]</code> (if no such index, we are done)

3. Let j be the last index such that <code>input[i] < input[j]</code>

4. Swap <code>input[i]</code> with <code>input[j]</code>

5. Reverse <code>input[i+1]</code> through <code>input[input.length-1]</code>

==Example==

Pass the flag "CHARLES"

First permutation is sorted: ACEHLRS

Second string is ACEHLSR

Third string is ACEHRLS

etc.

==Code==

==Flags=

[[Category:Stacks]]
[[Category:Queues]]
[[Category:Java]]

{{AlgorithmsFlag}}