Brute force least adjacent swap anagram transform in Java
0
$begingroup$
In this post, we are given two anagrams, and we wish to compute a shortest sequence of adjacent character swaps. For example, DBAC -> BDAC -> BADC -> ABDC -> ABCD, four adjacent swaps. I tried to split the algorithm into logical parts in order to facilitate better readability and would like to hear comments regarding it. Here is my code:
LeastAdjacentSwapAnagramTransformAlgorithm.java
package net.coderodde.fun;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* This interface defines the API and basic infrastructure for algorithms
* returning a shortest list of adjacent swaps required to transform one anagram
* into another.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Jan 5, 2019)
*/
public interface LeastAdjacentSwapAnagramTransformAlgorithm {
/**
* Encodes an adjacent pair of elements in an array.
*/
public static final class AdjacentSwapDescriptor {
/**
* The index of the left list element. We imply here, that the index of
* the right list element is {@code startingIndex + 1}.
*/
public final int startingIndex;
/**
* Constructs a new, immutable descriptor.
*
* @param startingIndex the index of the left list element.
*/
public AdjacentSwapDescriptor(int startingIndex) {
this.startingIndex = startingIndex;
}
@Override
public boolean equals(Object o) {
if (o == null) {
return false;
}
if (!o.getClass().equals(this.getClass())) {
return false;
}
AdjacentSwapDescriptor other = (AdjacentSwapDescriptor) o;
return startingIndex == other.startingIndex;
}
@Override
public String toString() {
return "(" + startingIndex + ", " + (startingIndex + 1) + ")";
}
}
/**
* Finds a shortest sequence of adjacent swaps, that transforms
* {@code string1} into {@code string2}.
*
* @param string1 the source string.
* @param string2 the target string.
* @return the list of adjacent swaps transforming the source array into the
* target array.
*/
public List<AdjacentSwapDescriptor> compute(String string1, String string2);
/**
* Checks that the two input strings are anagrams.
*
* @param string1 the first string.
* @param string2 the second string.
* @return {@code true} if the two input strings are anagrams. {@code false}
* otherwise.
*/
static boolean areAnagrams(String string1, String string2) {
Map<Character, Integer> characterCountMap1 = new HashMap<>();
Map<Character, Integer> characterCountMap2 = new HashMap<>();
for (char c : string1.toCharArray()) {
characterCountMap1.
put(c, characterCountMap1.getOrDefault(c, 0) + 1);
}
for (char c : string2.toCharArray()) {
characterCountMap2.
put(c, characterCountMap2.getOrDefault(c, 0) + 1);
}
return characterCountMap1.equals(characterCountMap2);
}
}
BruteForceLeastAdjacentSwapAnagramTransformAlgorithm.java
package net.coderodde.fun.support;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;
import static net.coderodde.fun.LeastAdjacentSwapAnagramTransformAlgorithm.areAnagrams;
import net.coderodde.util.ListTupleIndexIterator;
import net.coderodde.util.PermutationIterable;
import net.coderodde.fun.LeastAdjacentSwapAnagramTransformAlgorithm;
/**
* This class implements a brute-force algorithm for computing shortest
* inversions list transforming one input string into another.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Jan 5, 2019)
*/
public final class BruteForceLeastAdjacentSwapAnagramTransformAlgorithm
implements LeastAdjacentSwapAnagramTransformAlgorithm {
/**
* Computes and returns a shortest sequence of inversion required to
* transform one string into another.
*
* @param string1 the first string.
* @param string2 the second string.
* @return a sequence (list) of inversions.
*/
@Override
public List<AdjacentSwapDescriptor> compute(String string1, String string2) {
checkInputStrings(string1, string2);
if (string1.equals(string2)) {
return new ArrayList<>();
}
SolutionDescriptor solutionDescriptor = computeImpl(string1,
string2);
return toAdjacentSwapDescriptorList(solutionDescriptor);
}
/**
* Converts internal representation of a solution to the one according to
* API.
*
* @param solutionDescriptor the solution descriptor.
* @return solution.
*/
private static final List<AdjacentSwapDescriptor>
toAdjacentSwapDescriptorList(SolutionDescriptor solutionDescriptor) {
List<AdjacentSwapDescriptor> list =
new ArrayList<>(solutionDescriptor.permutationIndices.length);
for (int index : solutionDescriptor.permutationIndices) {
list.add(
new AdjacentSwapDescriptor(
solutionDescriptor.tupleIndices[index]));
}
return list;
}
/**
* Runs preliminary checks on the two input strings.
*
* @param string1 the first string.
* @param string2 the second string.
*/
private static void checkInputStrings(String string1, String string2) {
Objects.requireNonNull(string1, "The first input string is null.");
Objects.requireNonNull(string2, "The second input string is null.");
checkStringsHaveSameLength(string1, string2);
checkStringsAreAnagrams(string1, string2);
}
/**
* Checks that the two input strings are of the same length.
*
* @param string1 the first string.
* @param string2 the second string.
*/
private static void checkStringsHaveSameLength(String string1,
String string2) {
if (string1.length() != string2.length()) {
throw new IllegalArgumentException(
"The two input streams have different lengths: " +
string1.length() + " vs. " + string2.length());
}
}
/**
* Checks that the two input strings are of anagrams. In other worlds,
* checks that one string can be transformed into the second string only by
* rearranging the letters in one of them.
*
* @param string1 the first string.
* @param string2 the second string.
*/
private static void checkStringsAreAnagrams(String string1,
String string2) {
if (!areAnagrams(string1, string2)) {
throw new IllegalArgumentException(
"The two input strings are not anagrams.");
}
}
/**
* Runs the topmost search of the algorithm.
*
* @param string1 the source string.
* @param string2 the target string.
* @return the smallest list of inversion descriptors required to transform
* one string into another.
*/
private static SolutionDescriptor computeImpl(String string1, // DBAC -> DABC -> ADBC -> ABDC -> ABCD
String string2) { // (1, 2) -> (0, 1) -> (1, 2) -> (2, 3)
char sourceStringChars = string1.toCharArray();
char targetStringChars = string2.toCharArray();
char bufferStringChars = new char[sourceStringChars.length];
for (int inversions = 1; true; inversions++) {
SolutionDescriptor solutionDescriptor =
computeImpl(sourceStringChars,
targetStringChars,
bufferStringChars,
inversions);
if (solutionDescriptor != null) {
return solutionDescriptor;
}
}
}
/**
* Holds internal representation of a solution. tupleIndices[i] holds the
* index of the i'th adjacent swap to apply to the source array in order to
* convert the source string to the target string. permutationIndices[i]
* specifies the order the indices from tupleIndices should be applies.
*/
private static final class SolutionDescriptor {
final int tupleIndices;
final int permutationIndices;
SolutionDescriptor(int tupleIndices,
int permutationIndices) {
this.tupleIndices = tupleIndices;
this.permutationIndices = permutationIndices;
}
}
/**
* Attempts to find an inversion descriptor list of length
* {@code inversions}. If no such exist, returns {@code null}.
*
* @param sourceStringChars the source string.
* @param targetStringChars the target string.
* @param inversions the requested number of inversions in the result.
* @return if not such list exist.
*/
private static SolutionDescriptor computeImpl(char sourceStringChars,
char targetStringChars,
char bufferStringChars,
int inversions) {
// string1.length() - 1, i.e., there are at most n - 1 distinct
// inversion pairs, with largest value n - 1:
ListTupleIndexIterator iterator =
new ListTupleIndexIterator(inversions,
sourceStringChars.length - 2);
int indices = iterator.getIndexArray();
do {
SolutionDescriptor solutionDescriptor =
applyIndicesToWorkArray(sourceStringChars,
targetStringChars,
bufferStringChars,
indices);
if (solutionDescriptor != null) {
return solutionDescriptor;
}
iterator.generateNextTupleIndices();
} while (iterator.hasNext());
return null;
}
/**
* Permutes all the entries in the {@code indices} and for each index
* permutation applies the sequence and checks to see if they are sufficient
* for transforming the source array to the target array.
*
* @param sourceCharArray the source character array.
* @param targetCharArray the target character array.
* @param bufferCharArray the buffer character array.
* @param indices the adjacent swap indices.
* @return a solution descriptor.
*/
private static SolutionDescriptor
applyIndicesToWorkArray(char sourceCharArray,
char targetCharArray,
char bufferCharArray,
int indices) {
copy(sourceCharArray, bufferCharArray);
PermutationIterable permutationIterable =
new PermutationIterable(indices.length);
int permutationIndices = permutationIterable.getIndexArray();
while (permutationIterable.hasNext()) {
copy(sourceCharArray,
bufferCharArray);
// For each inversion pair permutation, apply it and see whether we
// got to the source character array:
for (int i : permutationIndices) {
int inversionIndex = indices[i];
swap(bufferCharArray,
inversionIndex,
inversionIndex + 1);
}
if (Arrays.equals(bufferCharArray, targetCharArray)) {
return new SolutionDescriptor(indices, permutationIndices);
}
permutationIterable.generateNextPermutation();
}
return null;
}
private static void swap(char array,
int index1,
int index2) {
char tmp = array[index1];
array[index1] = array[index2];
array[index2] = tmp;
}
/**
* Throws entire {@code sourceArray} to [@code targetArray}.
* @param sourceArray the source array.
* @param targetArray the target array.
*/
private static void copy(char sourceArray, char targetArray) {
System.arraycopy(sourceArray,
0,
targetArray,
0,
sourceArray.length);
}
}
ListTupleIndexIterator.java
package net.coderodde.util;
/**
* This class implements list tuples iterators. Given
* {@code requestedMaximumIndexValue} and {@code numberOfIndices}, set all
* {@code numberOfIndices} to zero. Than increments the first index until it has
* value [@code requestedMaximumIndex}, after which, resets the index and sets
* the second index to 1. This is continued until the second index becomes
* {@code requestedMaximumIndex}, after which the two indices are set to all
* and the third index is incremented. This continues until all indices are set
* to {@code requestedMaximumIndexValue}. I
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Jan 5, 2019)
*/
public final class ListTupleIndexIterator {
private final int requestedMaximumIndexValue;
private final int indices;
private boolean iterationExhausted = false;
public ListTupleIndexIterator(int numberOfIndices,
int requestedMaximumIndex) {
this.indices = new int[numberOfIndices];
this.requestedMaximumIndexValue = requestedMaximumIndex;
}
public int getIndexArray() {
return indices;
}
public boolean hasNext() {
return !iterationExhausted;
}
public void generateNextTupleIndices() {
int n = indices.length;
int i = n - 1;
while (i >= 0 && indices[i] == requestedMaximumIndexValue) {
i--;
}
if (i < 0) {
iterationExhausted = true;
return;
}
indices[i]++;
for (int j = i + 1; j < n; j++) {
indices[j] = 0;
}
}
}
PermutationIterator.java
package net.coderodde.util;
import java.util.Arrays;
import java.util.stream.IntStream;
/**
* This class permutes an integer index array.
*
* @author Rodde "rodde" Efremov
* @version 1.6 (Jan 4, 2019)
*/
public final class PermutationIterator {
private final int indices;
private boolean iterationExhausted;
public PermutationIterator(int numberoOfObjectsToPermute) {
this.indices = IntStream.range(0, numberoOfObjectsToPermute).toArray();
this.iterationExhausted = false;
}
public boolean hasNext() {
return !iterationExhausted;
}
public int getIndexArray() {
return indices;
}
public void generateNextPermutation() {
int inversionStartIndex = findAscendingPairStartIndex();
if (inversionStartIndex == -1) {
iterationExhausted = true;
return;
}
int largestElementIndex =
findSmallestElementIndexLargerThanInputIndex(
inversionStartIndex + 1,
indices[inversionStartIndex]);
swap(indices,
inversionStartIndex,
largestElementIndex);
reverse(indices,
inversionStartIndex + 1,
indices.length);
}
/**
* Seeks for the starting index of the rightmost ascending pair in the
* index array.
*
* @return the starting index of the rightmost ascending pair.
*/
private final int findAscendingPairStartIndex() {
for (int i = indices.length - 2; i >= 0; i--) {
if (indices[i] < indices[i + 1]) {
return i;
}
}
return -1;
}
/**
* Returns the index of the smallest integer no smaller or equal to
* {@code lowerBound}.
*
* @param lowerBoundIndex the smallest relevant index into the array
* prefix.
* @param lowerBound
* @return
*/
private int findSmallestElementIndexLargerThanInputIndex(
int lowerBoundIndex,
int lowerBound) {
int smallestFitElement = Integer.MAX_VALUE;
int smallestFitElementIndex = -1;
for (int i = lowerBoundIndex;
i < indices.length;
i++) {
int currentElement = indices[i];
if (currentElement > lowerBound
&& currentElement < smallestFitElement) {
smallestFitElement = currentElement;
smallestFitElementIndex = i;
}
}
return smallestFitElementIndex;
}
private static final void swap(int array,
int index1,
int index2) {
int tmp = array[index1];
array[index1] = array[index2];
array[index2] = tmp;
}
private static final void reverse(int array,
int fromIndex,
int toIndex) {
for (int i = fromIndex, j = toIndex - 1; i < j; i++, j--) {
swap(array, i, j);
}
}
}
(The entire Maven project is here.)
java algorithm strings
asked 9 mins ago
coderoddecoderodde
15.7k538127
$endgroup$
add a comment |
0
$begingroup$
In this post, we are given two anagrams, and we wish to compute a shortest sequence of adjacent character swaps. For example, DBAC -> BDAC -> BADC -> ABDC -> ABCD, four adjacent swaps. I tried to split the algorithm into logical parts in order to facilitate better readability and would like to hear comments regarding it. Here is my code:
LeastAdjacentSwapAnagramTransformAlgorithm.java
package net.coderodde.fun;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* This interface defines the API and basic infrastructure for algorithms
* returning a shortest list of adjacent swaps required to transform one anagram
* into another.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Jan 5, 2019)
*/
public interface LeastAdjacentSwapAnagramTransformAlgorithm {
/**
* Encodes an adjacent pair of elements in an array.
*/
public static final class AdjacentSwapDescriptor {
/**
* The index of the left list element. We imply here, that the index of
* the right list element is {@code startingIndex + 1}.
*/
public final int startingIndex;
/**
* Constructs a new, immutable descriptor.
*
* @param startingIndex the index of the left list element.
*/
public AdjacentSwapDescriptor(int startingIndex) {
this.startingIndex = startingIndex;
}
@Override
public boolean equals(Object o) {
if (o == null) {
return false;
}
if (!o.getClass().equals(this.getClass())) {
return false;
}
AdjacentSwapDescriptor other = (AdjacentSwapDescriptor) o;
return startingIndex == other.startingIndex;
}
@Override
public String toString() {
return "(" + startingIndex + ", " + (startingIndex + 1) + ")";
}
}
/**
* Finds a shortest sequence of adjacent swaps, that transforms
* {@code string1} into {@code string2}.
*
* @param string1 the source string.
* @param string2 the target string.
* @return the list of adjacent swaps transforming the source array into the
* target array.
*/
public List<AdjacentSwapDescriptor> compute(String string1, String string2);
/**
* Checks that the two input strings are anagrams.
*
* @param string1 the first string.
* @param string2 the second string.
* @return {@code true} if the two input strings are anagrams. {@code false}
* otherwise.
*/
static boolean areAnagrams(String string1, String string2) {
Map<Character, Integer> characterCountMap1 = new HashMap<>();
Map<Character, Integer> characterCountMap2 = new HashMap<>();
for (char c : string1.toCharArray()) {
characterCountMap1.
put(c, characterCountMap1.getOrDefault(c, 0) + 1);
}
for (char c : string2.toCharArray()) {
characterCountMap2.
put(c, characterCountMap2.getOrDefault(c, 0) + 1);
}
return characterCountMap1.equals(characterCountMap2);
}
}
BruteForceLeastAdjacentSwapAnagramTransformAlgorithm.java
package net.coderodde.fun.support;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;
import static net.coderodde.fun.LeastAdjacentSwapAnagramTransformAlgorithm.areAnagrams;
import net.coderodde.util.ListTupleIndexIterator;
import net.coderodde.util.PermutationIterable;
import net.coderodde.fun.LeastAdjacentSwapAnagramTransformAlgorithm;
/**
* This class implements a brute-force algorithm for computing shortest
* inversions list transforming one input string into another.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Jan 5, 2019)
*/
public final class BruteForceLeastAdjacentSwapAnagramTransformAlgorithm
implements LeastAdjacentSwapAnagramTransformAlgorithm {
/**
* Computes and returns a shortest sequence of inversion required to
* transform one string into another.
*
* @param string1 the first string.
* @param string2 the second string.
* @return a sequence (list) of inversions.
*/
@Override
public List<AdjacentSwapDescriptor> compute(String string1, String string2) {
checkInputStrings(string1, string2);
if (string1.equals(string2)) {
return new ArrayList<>();
}
SolutionDescriptor solutionDescriptor = computeImpl(string1,
string2);
return toAdjacentSwapDescriptorList(solutionDescriptor);
}
/**
* Converts internal representation of a solution to the one according to
* API.
*
* @param solutionDescriptor the solution descriptor.
* @return solution.
*/
private static final List<AdjacentSwapDescriptor>
toAdjacentSwapDescriptorList(SolutionDescriptor solutionDescriptor) {
List<AdjacentSwapDescriptor> list =
new ArrayList<>(solutionDescriptor.permutationIndices.length);
for (int index : solutionDescriptor.permutationIndices) {
list.add(
new AdjacentSwapDescriptor(
solutionDescriptor.tupleIndices[index]));
}
return list;
}
/**
* Runs preliminary checks on the two input strings.
*
* @param string1 the first string.
* @param string2 the second string.
*/
private static void checkInputStrings(String string1, String string2) {
Objects.requireNonNull(string1, "The first input string is null.");
Objects.requireNonNull(string2, "The second input string is null.");
checkStringsHaveSameLength(string1, string2);
checkStringsAreAnagrams(string1, string2);
}
/**
* Checks that the two input strings are of the same length.
*
* @param string1 the first string.
* @param string2 the second string.
*/
private static void checkStringsHaveSameLength(String string1,
String string2) {
if (string1.length() != string2.length()) {
throw new IllegalArgumentException(
"The two input streams have different lengths: " +
string1.length() + " vs. " + string2.length());
}
}
/**
* Checks that the two input strings are of anagrams. In other worlds,
* checks that one string can be transformed into the second string only by
* rearranging the letters in one of them.
*
* @param string1 the first string.
* @param string2 the second string.
*/
private static void checkStringsAreAnagrams(String string1,
String string2) {
if (!areAnagrams(string1, string2)) {
throw new IllegalArgumentException(
"The two input strings are not anagrams.");
}
}
/**
* Runs the topmost search of the algorithm.
*
* @param string1 the source string.
* @param string2 the target string.
* @return the smallest list of inversion descriptors required to transform
* one string into another.
*/
private static SolutionDescriptor computeImpl(String string1, // DBAC -> DABC -> ADBC -> ABDC -> ABCD
String string2) { // (1, 2) -> (0, 1) -> (1, 2) -> (2, 3)
char sourceStringChars = string1.toCharArray();
char targetStringChars = string2.toCharArray();
char bufferStringChars = new char[sourceStringChars.length];
for (int inversions = 1; true; inversions++) {
SolutionDescriptor solutionDescriptor =
computeImpl(sourceStringChars,
targetStringChars,
bufferStringChars,
inversions);
if (solutionDescriptor != null) {
return solutionDescriptor;
}
}
}
/**
* Holds internal representation of a solution. tupleIndices[i] holds the
* index of the i'th adjacent swap to apply to the source array in order to
* convert the source string to the target string. permutationIndices[i]
* specifies the order the indices from tupleIndices should be applies.
*/
private static final class SolutionDescriptor {
final int tupleIndices;
final int permutationIndices;
SolutionDescriptor(int tupleIndices,
int permutationIndices) {
this.tupleIndices = tupleIndices;
this.permutationIndices = permutationIndices;
}
}
/**
* Attempts to find an inversion descriptor list of length
* {@code inversions}. If no such exist, returns {@code null}.
*
* @param sourceStringChars the source string.
* @param targetStringChars the target string.
* @param inversions the requested number of inversions in the result.
* @return if not such list exist.
*/
private static SolutionDescriptor computeImpl(char sourceStringChars,
char targetStringChars,
char bufferStringChars,
int inversions) {
// string1.length() - 1, i.e., there are at most n - 1 distinct
// inversion pairs, with largest value n - 1:
ListTupleIndexIterator iterator =
new ListTupleIndexIterator(inversions,
sourceStringChars.length - 2);
int indices = iterator.getIndexArray();
do {
SolutionDescriptor solutionDescriptor =
applyIndicesToWorkArray(sourceStringChars,
targetStringChars,
bufferStringChars,
indices);
if (solutionDescriptor != null) {
return solutionDescriptor;
}
iterator.generateNextTupleIndices();
} while (iterator.hasNext());
return null;
}
/**
* Permutes all the entries in the {@code indices} and for each index
* permutation applies the sequence and checks to see if they are sufficient
* for transforming the source array to the target array.
*
* @param sourceCharArray the source character array.
* @param targetCharArray the target character array.
* @param bufferCharArray the buffer character array.
* @param indices the adjacent swap indices.
* @return a solution descriptor.
*/
private static SolutionDescriptor
applyIndicesToWorkArray(char sourceCharArray,
char targetCharArray,
char bufferCharArray,
int indices) {
copy(sourceCharArray, bufferCharArray);
PermutationIterable permutationIterable =
new PermutationIterable(indices.length);
int permutationIndices = permutationIterable.getIndexArray();
while (permutationIterable.hasNext()) {
copy(sourceCharArray,
bufferCharArray);
// For each inversion pair permutation, apply it and see whether we
// got to the source character array:
for (int i : permutationIndices) {
int inversionIndex = indices[i];
swap(bufferCharArray,
inversionIndex,
inversionIndex + 1);
}
if (Arrays.equals(bufferCharArray, targetCharArray)) {
return new SolutionDescriptor(indices, permutationIndices);
}
permutationIterable.generateNextPermutation();
}
return null;
}
private static void swap(char array,
int index1,
int index2) {
char tmp = array[index1];
array[index1] = array[index2];
array[index2] = tmp;
}
/**
* Throws entire {@code sourceArray} to [@code targetArray}.
* @param sourceArray the source array.
* @param targetArray the target array.
*/
private static void copy(char sourceArray, char targetArray) {
System.arraycopy(sourceArray,
0,
targetArray,
0,
sourceArray.length);
}
}
ListTupleIndexIterator.java
package net.coderodde.util;
/**
* This class implements list tuples iterators. Given
* {@code requestedMaximumIndexValue} and {@code numberOfIndices}, set all
* {@code numberOfIndices} to zero. Than increments the first index until it has
* value [@code requestedMaximumIndex}, after which, resets the index and sets
* the second index to 1. This is continued until the second index becomes
* {@code requestedMaximumIndex}, after which the two indices are set to all
* and the third index is incremented. This continues until all indices are set
* to {@code requestedMaximumIndexValue}. I
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Jan 5, 2019)
*/
public final class ListTupleIndexIterator {
private final int requestedMaximumIndexValue;
private final int indices;
private boolean iterationExhausted = false;
public ListTupleIndexIterator(int numberOfIndices,
int requestedMaximumIndex) {
this.indices = new int[numberOfIndices];
this.requestedMaximumIndexValue = requestedMaximumIndex;
}
public int getIndexArray() {
return indices;
}
public boolean hasNext() {
return !iterationExhausted;
}
public void generateNextTupleIndices() {
int n = indices.length;
int i = n - 1;
while (i >= 0 && indices[i] == requestedMaximumIndexValue) {
i--;
}
if (i < 0) {
iterationExhausted = true;
return;
}
indices[i]++;
for (int j = i + 1; j < n; j++) {
indices[j] = 0;
}
}
}
PermutationIterator.java
package net.coderodde.util;
import java.util.Arrays;
import java.util.stream.IntStream;
/**
* This class permutes an integer index array.
*
* @author Rodde "rodde" Efremov
* @version 1.6 (Jan 4, 2019)
*/
public final class PermutationIterator {
private final int indices;
private boolean iterationExhausted;
public PermutationIterator(int numberoOfObjectsToPermute) {
this.indices = IntStream.range(0, numberoOfObjectsToPermute).toArray();
this.iterationExhausted = false;
}
public boolean hasNext() {
return !iterationExhausted;
}
public int getIndexArray() {
return indices;
}
public void generateNextPermutation() {
int inversionStartIndex = findAscendingPairStartIndex();
if (inversionStartIndex == -1) {
iterationExhausted = true;
return;
}
int largestElementIndex =
findSmallestElementIndexLargerThanInputIndex(
inversionStartIndex + 1,
indices[inversionStartIndex]);
swap(indices,
inversionStartIndex,
largestElementIndex);
reverse(indices,
inversionStartIndex + 1,
indices.length);
}
/**
* Seeks for the starting index of the rightmost ascending pair in the
* index array.
*
* @return the starting index of the rightmost ascending pair.
*/
private final int findAscendingPairStartIndex() {
for (int i = indices.length - 2; i >= 0; i--) {
if (indices[i] < indices[i + 1]) {
return i;
}
}
return -1;
}
/**
* Returns the index of the smallest integer no smaller or equal to
* {@code lowerBound}.
*
* @param lowerBoundIndex the smallest relevant index into the array
* prefix.
* @param lowerBound
* @return
*/
private int findSmallestElementIndexLargerThanInputIndex(
int lowerBoundIndex,
int lowerBound) {
int smallestFitElement = Integer.MAX_VALUE;
int smallestFitElementIndex = -1;
for (int i = lowerBoundIndex;
i < indices.length;
i++) {
int currentElement = indices[i];
if (currentElement > lowerBound
&& currentElement < smallestFitElement) {
smallestFitElement = currentElement;
smallestFitElementIndex = i;
}
}
return smallestFitElementIndex;
}
private static final void swap(int array,
int index1,
int index2) {
int tmp = array[index1];
array[index1] = array[index2];
array[index2] = tmp;
}
private static final void reverse(int array,
int fromIndex,
int toIndex) {
for (int i = fromIndex, j = toIndex - 1; i < j; i++, j--) {
swap(array, i, j);
}
}
}
(The entire Maven project is here.)
java algorithm strings
asked 9 mins ago
coderoddecoderodde
15.7k538127
$endgroup$
add a comment |
0
0
0
$begingroup$
In this post, we are given two anagrams, and we wish to compute a shortest sequence of adjacent character swaps. For example, DBAC -> BDAC -> BADC -> ABDC -> ABCD, four adjacent swaps. I tried to split the algorithm into logical parts in order to facilitate better readability and would like to hear comments regarding it. Here is my code:
LeastAdjacentSwapAnagramTransformAlgorithm.java
package net.coderodde.fun;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* This interface defines the API and basic infrastructure for algorithms
* returning a shortest list of adjacent swaps required to transform one anagram
* into another.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Jan 5, 2019)
*/
public interface LeastAdjacentSwapAnagramTransformAlgorithm {
/**
* Encodes an adjacent pair of elements in an array.
*/
public static final class AdjacentSwapDescriptor {
/**
* The index of the left list element. We imply here, that the index of
* the right list element is {@code startingIndex + 1}.
*/
public final int startingIndex;
/**
* Constructs a new, immutable descriptor.
*
* @param startingIndex the index of the left list element.
*/
public AdjacentSwapDescriptor(int startingIndex) {
this.startingIndex = startingIndex;
}
@Override
public boolean equals(Object o) {
if (o == null) {
return false;
}
if (!o.getClass().equals(this.getClass())) {
return false;
}
AdjacentSwapDescriptor other = (AdjacentSwapDescriptor) o;
return startingIndex == other.startingIndex;
}
@Override
public String toString() {
return "(" + startingIndex + ", " + (startingIndex + 1) + ")";
}
}
/**
* Finds a shortest sequence of adjacent swaps, that transforms
* {@code string1} into {@code string2}.
*
* @param string1 the source string.
* @param string2 the target string.
* @return the list of adjacent swaps transforming the source array into the
* target array.
*/
public List<AdjacentSwapDescriptor> compute(String string1, String string2);
/**
* Checks that the two input strings are anagrams.
*
* @param string1 the first string.
* @param string2 the second string.
* @return {@code true} if the two input strings are anagrams. {@code false}
* otherwise.
*/
static boolean areAnagrams(String string1, String string2) {
Map<Character, Integer> characterCountMap1 = new HashMap<>();
Map<Character, Integer> characterCountMap2 = new HashMap<>();
for (char c : string1.toCharArray()) {
characterCountMap1.
put(c, characterCountMap1.getOrDefault(c, 0) + 1);
}
for (char c : string2.toCharArray()) {
characterCountMap2.
put(c, characterCountMap2.getOrDefault(c, 0) + 1);
}
return characterCountMap1.equals(characterCountMap2);
}
}
BruteForceLeastAdjacentSwapAnagramTransformAlgorithm.java
package net.coderodde.fun.support;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;
import static net.coderodde.fun.LeastAdjacentSwapAnagramTransformAlgorithm.areAnagrams;
import net.coderodde.util.ListTupleIndexIterator;
import net.coderodde.util.PermutationIterable;
import net.coderodde.fun.LeastAdjacentSwapAnagramTransformAlgorithm;
/**
* This class implements a brute-force algorithm for computing shortest
* inversions list transforming one input string into another.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Jan 5, 2019)
*/
public final class BruteForceLeastAdjacentSwapAnagramTransformAlgorithm
implements LeastAdjacentSwapAnagramTransformAlgorithm {
/**
* Computes and returns a shortest sequence of inversion required to
* transform one string into another.
*
* @param string1 the first string.
* @param string2 the second string.
* @return a sequence (list) of inversions.
*/
@Override
public List<AdjacentSwapDescriptor> compute(String string1, String string2) {
checkInputStrings(string1, string2);
if (string1.equals(string2)) {
return new ArrayList<>();
}
SolutionDescriptor solutionDescriptor = computeImpl(string1,
string2);
return toAdjacentSwapDescriptorList(solutionDescriptor);
}
/**
* Converts internal representation of a solution to the one according to
* API.
*
* @param solutionDescriptor the solution descriptor.
* @return solution.
*/
private static final List<AdjacentSwapDescriptor>
toAdjacentSwapDescriptorList(SolutionDescriptor solutionDescriptor) {
List<AdjacentSwapDescriptor> list =
new ArrayList<>(solutionDescriptor.permutationIndices.length);
for (int index : solutionDescriptor.permutationIndices) {
list.add(
new AdjacentSwapDescriptor(
solutionDescriptor.tupleIndices[index]));
}
return list;
}
/**
* Runs preliminary checks on the two input strings.
*
* @param string1 the first string.
* @param string2 the second string.
*/
private static void checkInputStrings(String string1, String string2) {
Objects.requireNonNull(string1, "The first input string is null.");
Objects.requireNonNull(string2, "The second input string is null.");
checkStringsHaveSameLength(string1, string2);
checkStringsAreAnagrams(string1, string2);
}
/**
* Checks that the two input strings are of the same length.
*
* @param string1 the first string.
* @param string2 the second string.
*/
private static void checkStringsHaveSameLength(String string1,
String string2) {
if (string1.length() != string2.length()) {
throw new IllegalArgumentException(
"The two input streams have different lengths: " +
string1.length() + " vs. " + string2.length());
}
}
/**
* Checks that the two input strings are of anagrams. In other worlds,
* checks that one string can be transformed into the second string only by
* rearranging the letters in one of them.
*
* @param string1 the first string.
* @param string2 the second string.
*/
private static void checkStringsAreAnagrams(String string1,
String string2) {
if (!areAnagrams(string1, string2)) {
throw new IllegalArgumentException(
"The two input strings are not anagrams.");
}
}
/**
* Runs the topmost search of the algorithm.
*
* @param string1 the source string.
* @param string2 the target string.
* @return the smallest list of inversion descriptors required to transform
* one string into another.
*/
private static SolutionDescriptor computeImpl(String string1, // DBAC -> DABC -> ADBC -> ABDC -> ABCD
String string2) { // (1, 2) -> (0, 1) -> (1, 2) -> (2, 3)
char sourceStringChars = string1.toCharArray();
char targetStringChars = string2.toCharArray();
char bufferStringChars = new char[sourceStringChars.length];
for (int inversions = 1; true; inversions++) {
SolutionDescriptor solutionDescriptor =
computeImpl(sourceStringChars,
targetStringChars,
bufferStringChars,
inversions);
if (solutionDescriptor != null) {
return solutionDescriptor;
}
}
}
/**
* Holds internal representation of a solution. tupleIndices[i] holds the
* index of the i'th adjacent swap to apply to the source array in order to
* convert the source string to the target string. permutationIndices[i]
* specifies the order the indices from tupleIndices should be applies.
*/
private static final class SolutionDescriptor {
final int tupleIndices;
final int permutationIndices;
SolutionDescriptor(int tupleIndices,
int permutationIndices) {
this.tupleIndices = tupleIndices;
this.permutationIndices = permutationIndices;
}
}
/**
* Attempts to find an inversion descriptor list of length
* {@code inversions}. If no such exist, returns {@code null}.
*
* @param sourceStringChars the source string.
* @param targetStringChars the target string.
* @param inversions the requested number of inversions in the result.
* @return if not such list exist.
*/
private static SolutionDescriptor computeImpl(char sourceStringChars,
char targetStringChars,
char bufferStringChars,
int inversions) {
// string1.length() - 1, i.e., there are at most n - 1 distinct
// inversion pairs, with largest value n - 1:
ListTupleIndexIterator iterator =
new ListTupleIndexIterator(inversions,
sourceStringChars.length - 2);
int indices = iterator.getIndexArray();
do {
SolutionDescriptor solutionDescriptor =
applyIndicesToWorkArray(sourceStringChars,
targetStringChars,
bufferStringChars,
indices);
if (solutionDescriptor != null) {
return solutionDescriptor;
}
iterator.generateNextTupleIndices();
} while (iterator.hasNext());
return null;
}
/**
* Permutes all the entries in the {@code indices} and for each index
* permutation applies the sequence and checks to see if they are sufficient
* for transforming the source array to the target array.
*
* @param sourceCharArray the source character array.
* @param targetCharArray the target character array.
* @param bufferCharArray the buffer character array.
* @param indices the adjacent swap indices.
* @return a solution descriptor.
*/
private static SolutionDescriptor
applyIndicesToWorkArray(char sourceCharArray,
char targetCharArray,
char bufferCharArray,
int indices) {
copy(sourceCharArray, bufferCharArray);
PermutationIterable permutationIterable =
new PermutationIterable(indices.length);
int permutationIndices = permutationIterable.getIndexArray();
while (permutationIterable.hasNext()) {
copy(sourceCharArray,
bufferCharArray);
// For each inversion pair permutation, apply it and see whether we
// got to the source character array:
for (int i : permutationIndices) {
int inversionIndex = indices[i];
swap(bufferCharArray,
inversionIndex,
inversionIndex + 1);
}
if (Arrays.equals(bufferCharArray, targetCharArray)) {
return new SolutionDescriptor(indices, permutationIndices);
}
permutationIterable.generateNextPermutation();
}
return null;
}
private static void swap(char array,
int index1,
int index2) {
char tmp = array[index1];
array[index1] = array[index2];
array[index2] = tmp;
}
/**
* Throws entire {@code sourceArray} to [@code targetArray}.
* @param sourceArray the source array.
* @param targetArray the target array.
*/
private static void copy(char sourceArray, char targetArray) {
System.arraycopy(sourceArray,
0,
targetArray,
0,
sourceArray.length);
}
}
ListTupleIndexIterator.java
package net.coderodde.util;
/**
* This class implements list tuples iterators. Given
* {@code requestedMaximumIndexValue} and {@code numberOfIndices}, set all
* {@code numberOfIndices} to zero. Than increments the first index until it has
* value [@code requestedMaximumIndex}, after which, resets the index and sets
* the second index to 1. This is continued until the second index becomes
* {@code requestedMaximumIndex}, after which the two indices are set to all
* and the third index is incremented. This continues until all indices are set
* to {@code requestedMaximumIndexValue}. I
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Jan 5, 2019)
*/
public final class ListTupleIndexIterator {
private final int requestedMaximumIndexValue;
private final int indices;
private boolean iterationExhausted = false;
public ListTupleIndexIterator(int numberOfIndices,
int requestedMaximumIndex) {
this.indices = new int[numberOfIndices];
this.requestedMaximumIndexValue = requestedMaximumIndex;
}
public int getIndexArray() {
return indices;
}
public boolean hasNext() {
return !iterationExhausted;
}
public void generateNextTupleIndices() {
int n = indices.length;
int i = n - 1;
while (i >= 0 && indices[i] == requestedMaximumIndexValue) {
i--;
}
if (i < 0) {
iterationExhausted = true;
return;
}
indices[i]++;
for (int j = i + 1; j < n; j++) {
indices[j] = 0;
}
}
}
PermutationIterator.java
package net.coderodde.util;
import java.util.Arrays;
import java.util.stream.IntStream;
/**
* This class permutes an integer index array.
*
* @author Rodde "rodde" Efremov
* @version 1.6 (Jan 4, 2019)
*/
public final class PermutationIterator {
private final int indices;
private boolean iterationExhausted;
public PermutationIterator(int numberoOfObjectsToPermute) {
this.indices = IntStream.range(0, numberoOfObjectsToPermute).toArray();
this.iterationExhausted = false;
}
public boolean hasNext() {
return !iterationExhausted;
}
public int getIndexArray() {
return indices;
}
public void generateNextPermutation() {
int inversionStartIndex = findAscendingPairStartIndex();
if (inversionStartIndex == -1) {
iterationExhausted = true;
return;
}
int largestElementIndex =
findSmallestElementIndexLargerThanInputIndex(
inversionStartIndex + 1,
indices[inversionStartIndex]);
swap(indices,
inversionStartIndex,
largestElementIndex);
reverse(indices,
inversionStartIndex + 1,
indices.length);
}
/**
* Seeks for the starting index of the rightmost ascending pair in the
* index array.
*
* @return the starting index of the rightmost ascending pair.
*/
private final int findAscendingPairStartIndex() {
for (int i = indices.length - 2; i >= 0; i--) {
if (indices[i] < indices[i + 1]) {
return i;
}
}
return -1;
}
/**
* Returns the index of the smallest integer no smaller or equal to
* {@code lowerBound}.
*
* @param lowerBoundIndex the smallest relevant index into the array
* prefix.
* @param lowerBound
* @return
*/
private int findSmallestElementIndexLargerThanInputIndex(
int lowerBoundIndex,
int lowerBound) {
int smallestFitElement = Integer.MAX_VALUE;
int smallestFitElementIndex = -1;
for (int i = lowerBoundIndex;
i < indices.length;
i++) {
int currentElement = indices[i];
if (currentElement > lowerBound
&& currentElement < smallestFitElement) {
smallestFitElement = currentElement;
smallestFitElementIndex = i;
}
}
return smallestFitElementIndex;
}
private static final void swap(int array,
int index1,
int index2) {
int tmp = array[index1];
array[index1] = array[index2];
array[index2] = tmp;
}
private static final void reverse(int array,
int fromIndex,
int toIndex) {
for (int i = fromIndex, j = toIndex - 1; i < j; i++, j--) {
swap(array, i, j);
}
}
}
(The entire Maven project is here.)
java algorithm strings
asked 9 mins ago
coderoddecoderodde
15.7k538127
$endgroup$
In this post, we are given two anagrams, and we wish to compute a shortest sequence of adjacent character swaps. For example, DBAC -> BDAC -> BADC -> ABDC -> ABCD, four adjacent swaps. I tried to split the algorithm into logical parts in order to facilitate better readability and would like to hear comments regarding it. Here is my code:
LeastAdjacentSwapAnagramTransformAlgorithm.java
package net.coderodde.fun;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* This interface defines the API and basic infrastructure for algorithms
* returning a shortest list of adjacent swaps required to transform one anagram
* into another.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Jan 5, 2019)
*/
public interface LeastAdjacentSwapAnagramTransformAlgorithm {
/**
* Encodes an adjacent pair of elements in an array.
*/
public static final class AdjacentSwapDescriptor {
/**
* The index of the left list element. We imply here, that the index of
* the right list element is {@code startingIndex + 1}.
*/
public final int startingIndex;
/**
* Constructs a new, immutable descriptor.
*
* @param startingIndex the index of the left list element.
*/
public AdjacentSwapDescriptor(int startingIndex) {
this.startingIndex = startingIndex;
}
@Override
public boolean equals(Object o) {
if (o == null) {
return false;
}
if (!o.getClass().equals(this.getClass())) {
return false;
}
AdjacentSwapDescriptor other = (AdjacentSwapDescriptor) o;
return startingIndex == other.startingIndex;
}
@Override
public String toString() {
return "(" + startingIndex + ", " + (startingIndex + 1) + ")";
}
}
/**
* Finds a shortest sequence of adjacent swaps, that transforms
* {@code string1} into {@code string2}.
*
* @param string1 the source string.
* @param string2 the target string.
* @return the list of adjacent swaps transforming the source array into the
* target array.
*/
public List<AdjacentSwapDescriptor> compute(String string1, String string2);
/**
* Checks that the two input strings are anagrams.
*
* @param string1 the first string.
* @param string2 the second string.
* @return {@code true} if the two input strings are anagrams. {@code false}
* otherwise.
*/
static boolean areAnagrams(String string1, String string2) {
Map<Character, Integer> characterCountMap1 = new HashMap<>();
Map<Character, Integer> characterCountMap2 = new HashMap<>();
for (char c : string1.toCharArray()) {
characterCountMap1.
put(c, characterCountMap1.getOrDefault(c, 0) + 1);
}
for (char c : string2.toCharArray()) {
characterCountMap2.
put(c, characterCountMap2.getOrDefault(c, 0) + 1);
}
return characterCountMap1.equals(characterCountMap2);
}
}
BruteForceLeastAdjacentSwapAnagramTransformAlgorithm.java
package net.coderodde.fun.support;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;
import static net.coderodde.fun.LeastAdjacentSwapAnagramTransformAlgorithm.areAnagrams;
import net.coderodde.util.ListTupleIndexIterator;
import net.coderodde.util.PermutationIterable;
import net.coderodde.fun.LeastAdjacentSwapAnagramTransformAlgorithm;
/**
* This class implements a brute-force algorithm for computing shortest
* inversions list transforming one input string into another.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Jan 5, 2019)
*/
public final class BruteForceLeastAdjacentSwapAnagramTransformAlgorithm
implements LeastAdjacentSwapAnagramTransformAlgorithm {
/**
* Computes and returns a shortest sequence of inversion required to
* transform one string into another.
*
* @param string1 the first string.
* @param string2 the second string.
* @return a sequence (list) of inversions.
*/
@Override
public List<AdjacentSwapDescriptor> compute(String string1, String string2) {
checkInputStrings(string1, string2);
if (string1.equals(string2)) {
return new ArrayList<>();
}
SolutionDescriptor solutionDescriptor = computeImpl(string1,
string2);
return toAdjacentSwapDescriptorList(solutionDescriptor);
}
/**
* Converts internal representation of a solution to the one according to
* API.
*
* @param solutionDescriptor the solution descriptor.
* @return solution.
*/
private static final List<AdjacentSwapDescriptor>
toAdjacentSwapDescriptorList(SolutionDescriptor solutionDescriptor) {
List<AdjacentSwapDescriptor> list =
new ArrayList<>(solutionDescriptor.permutationIndices.length);
for (int index : solutionDescriptor.permutationIndices) {
list.add(
new AdjacentSwapDescriptor(
solutionDescriptor.tupleIndices[index]));
}
return list;
}
/**
* Runs preliminary checks on the two input strings.
*
* @param string1 the first string.
* @param string2 the second string.
*/
private static void checkInputStrings(String string1, String string2) {
Objects.requireNonNull(string1, "The first input string is null.");
Objects.requireNonNull(string2, "The second input string is null.");
checkStringsHaveSameLength(string1, string2);
checkStringsAreAnagrams(string1, string2);
}
/**
* Checks that the two input strings are of the same length.
*
* @param string1 the first string.
* @param string2 the second string.
*/
private static void checkStringsHaveSameLength(String string1,
String string2) {
if (string1.length() != string2.length()) {
throw new IllegalArgumentException(
"The two input streams have different lengths: " +
string1.length() + " vs. " + string2.length());
}
}
/**
* Checks that the two input strings are of anagrams. In other worlds,
* checks that one string can be transformed into the second string only by
* rearranging the letters in one of them.
*
* @param string1 the first string.
* @param string2 the second string.
*/
private static void checkStringsAreAnagrams(String string1,
String string2) {
if (!areAnagrams(string1, string2)) {
throw new IllegalArgumentException(
"The two input strings are not anagrams.");
}
}
/**
* Runs the topmost search of the algorithm.
*
* @param string1 the source string.
* @param string2 the target string.
* @return the smallest list of inversion descriptors required to transform
* one string into another.
*/
private static SolutionDescriptor computeImpl(String string1, // DBAC -> DABC -> ADBC -> ABDC -> ABCD
String string2) { // (1, 2) -> (0, 1) -> (1, 2) -> (2, 3)
char sourceStringChars = string1.toCharArray();
char targetStringChars = string2.toCharArray();
char bufferStringChars = new char[sourceStringChars.length];
for (int inversions = 1; true; inversions++) {
SolutionDescriptor solutionDescriptor =
computeImpl(sourceStringChars,
targetStringChars,
bufferStringChars,
inversions);
if (solutionDescriptor != null) {
return solutionDescriptor;
}
}
}
/**
* Holds internal representation of a solution. tupleIndices[i] holds the
* index of the i'th adjacent swap to apply to the source array in order to
* convert the source string to the target string. permutationIndices[i]
* specifies the order the indices from tupleIndices should be applies.
*/
private static final class SolutionDescriptor {
final int tupleIndices;
final int permutationIndices;
SolutionDescriptor(int tupleIndices,
int permutationIndices) {
this.tupleIndices = tupleIndices;
this.permutationIndices = permutationIndices;
}
}
/**
* Attempts to find an inversion descriptor list of length
* {@code inversions}. If no such exist, returns {@code null}.
*
* @param sourceStringChars the source string.
* @param targetStringChars the target string.
* @param inversions the requested number of inversions in the result.
* @return if not such list exist.
*/
private static SolutionDescriptor computeImpl(char sourceStringChars,
char targetStringChars,
char bufferStringChars,
int inversions) {
// string1.length() - 1, i.e., there are at most n - 1 distinct
// inversion pairs, with largest value n - 1:
ListTupleIndexIterator iterator =
new ListTupleIndexIterator(inversions,
sourceStringChars.length - 2);
int indices = iterator.getIndexArray();
do {
SolutionDescriptor solutionDescriptor =
applyIndicesToWorkArray(sourceStringChars,
targetStringChars,
bufferStringChars,
indices);
if (solutionDescriptor != null) {
return solutionDescriptor;
}
iterator.generateNextTupleIndices();
} while (iterator.hasNext());
return null;
}
/**
* Permutes all the entries in the {@code indices} and for each index
* permutation applies the sequence and checks to see if they are sufficient
* for transforming the source array to the target array.
*
* @param sourceCharArray the source character array.
* @param targetCharArray the target character array.
* @param bufferCharArray the buffer character array.
* @param indices the adjacent swap indices.
* @return a solution descriptor.
*/
private static SolutionDescriptor
applyIndicesToWorkArray(char sourceCharArray,
char targetCharArray,
char bufferCharArray,
int indices) {
copy(sourceCharArray, bufferCharArray);
PermutationIterable permutationIterable =
new PermutationIterable(indices.length);
int permutationIndices = permutationIterable.getIndexArray();
while (permutationIterable.hasNext()) {
copy(sourceCharArray,
bufferCharArray);
// For each inversion pair permutation, apply it and see whether we
// got to the source character array:
for (int i : permutationIndices) {
int inversionIndex = indices[i];
swap(bufferCharArray,
inversionIndex,
inversionIndex + 1);
}
if (Arrays.equals(bufferCharArray, targetCharArray)) {
return new SolutionDescriptor(indices, permutationIndices);
}
permutationIterable.generateNextPermutation();
}
return null;
}
private static void swap(char array,
int index1,
int index2) {
char tmp = array[index1];
array[index1] = array[index2];
array[index2] = tmp;
}
/**
* Throws entire {@code sourceArray} to [@code targetArray}.
* @param sourceArray the source array.
* @param targetArray the target array.
*/
private static void copy(char sourceArray, char targetArray) {
System.arraycopy(sourceArray,
0,
targetArray,
0,
sourceArray.length);
}
}
ListTupleIndexIterator.java
package net.coderodde.util;
/**
* This class implements list tuples iterators. Given
* {@code requestedMaximumIndexValue} and {@code numberOfIndices}, set all
* {@code numberOfIndices} to zero. Than increments the first index until it has
* value [@code requestedMaximumIndex}, after which, resets the index and sets
* the second index to 1. This is continued until the second index becomes
* {@code requestedMaximumIndex}, after which the two indices are set to all
* and the third index is incremented. This continues until all indices are set
* to {@code requestedMaximumIndexValue}. I
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Jan 5, 2019)
*/
public final class ListTupleIndexIterator {
private final int requestedMaximumIndexValue;
private final int indices;
private boolean iterationExhausted = false;
public ListTupleIndexIterator(int numberOfIndices,
int requestedMaximumIndex) {
this.indices = new int[numberOfIndices];
this.requestedMaximumIndexValue = requestedMaximumIndex;
}
public int getIndexArray() {
return indices;
}
public boolean hasNext() {
return !iterationExhausted;
}
public void generateNextTupleIndices() {
int n = indices.length;
int i = n - 1;
while (i >= 0 && indices[i] == requestedMaximumIndexValue) {
i--;
}
if (i < 0) {
iterationExhausted = true;
return;
}
indices[i]++;
for (int j = i + 1; j < n; j++) {
indices[j] = 0;
}
}
}
PermutationIterator.java
package net.coderodde.util;
import java.util.Arrays;
import java.util.stream.IntStream;
/**
* This class permutes an integer index array.
*
* @author Rodde "rodde" Efremov
* @version 1.6 (Jan 4, 2019)
*/
public final class PermutationIterator {
private final int indices;
private boolean iterationExhausted;
public PermutationIterator(int numberoOfObjectsToPermute) {
this.indices = IntStream.range(0, numberoOfObjectsToPermute).toArray();
this.iterationExhausted = false;
}
public boolean hasNext() {
return !iterationExhausted;
}
public int getIndexArray() {
return indices;
}
public void generateNextPermutation() {
int inversionStartIndex = findAscendingPairStartIndex();
if (inversionStartIndex == -1) {
iterationExhausted = true;
return;
}
int largestElementIndex =
findSmallestElementIndexLargerThanInputIndex(
inversionStartIndex + 1,
indices[inversionStartIndex]);
swap(indices,
inversionStartIndex,
largestElementIndex);
reverse(indices,
inversionStartIndex + 1,
indices.length);
}
/**
* Seeks for the starting index of the rightmost ascending pair in the
* index array.
*
* @return the starting index of the rightmost ascending pair.
*/
private final int findAscendingPairStartIndex() {
for (int i = indices.length - 2; i >= 0; i--) {
if (indices[i] < indices[i + 1]) {
return i;
}
}
return -1;
}
/**
* Returns the index of the smallest integer no smaller or equal to
* {@code lowerBound}.
*
* @param lowerBoundIndex the smallest relevant index into the array
* prefix.
* @param lowerBound
* @return
*/
private int findSmallestElementIndexLargerThanInputIndex(
int lowerBoundIndex,
int lowerBound) {
int smallestFitElement = Integer.MAX_VALUE;
int smallestFitElementIndex = -1;
for (int i = lowerBoundIndex;
i < indices.length;
i++) {
int currentElement = indices[i];
if (currentElement > lowerBound
&& currentElement < smallestFitElement) {
smallestFitElement = currentElement;
smallestFitElementIndex = i;
}
}
return smallestFitElementIndex;
}
private static final void swap(int array,
int index1,
int index2) {
int tmp = array[index1];
array[index1] = array[index2];
array[index2] = tmp;
}
private static final void reverse(int array,
int fromIndex,
int toIndex) {
for (int i = fromIndex, j = toIndex - 1; i < j; i++, j--) {
swap(array, i, j);
}
}
}
(The entire Maven project is here.)
java algorithm strings
java algorithm strings
asked 9 mins ago
coderoddecoderodde
15.7k538127
asked 9 mins ago
coderoddecoderodde
15.7k538127
asked 9 mins ago
coderoddecoderodde
15.7k538127
asked 9 mins ago
coderoddecoderodde
15.7k538127
asked 9 mins ago
coderoddecoderodde
15.7k538127
15.7k538127
add a comment |
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f211749%2fbrute-force-least-adjacent-swap-anagram-transform-in-java%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
draft saved
draft discarded
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f211749%2fbrute-force-least-adjacent-swap-anagram-transform-in-java%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
