Implement a class that works like an Iterator and generates all possible permuta
ID: 3827108 • Letter: I
Question
Implement a class that works like an Iterator and generates all possible permutations of a list. It cannot actually be an Iterator, because the official Java Iterator interface looks like the following: public interface Iterator {public boolean hasNext(); public E next (); public void remove ();} The next () method of a Java iterator returns an element of a collection, but our permutation generator must return a whole list. Nevertheless, we will adopt the mechanics of iterators. Create a Permutations object that implements the following three methods (at least): public class Permutations {public Permutations (List list); public Boolean hasNext(); public List next ();} Notice the difference? We should be able to call the constructor with an arbitrary list. Then, as long as hasNext() returns true, we should be able to call next() and get a new permutation of our list. The easiest way to generate permutations is (not surprisingly) recursively. The algorithm for creating a Permutations object is as follows: (Base case) If I am a Permutations object of list length 0, do nothing, except to note that I should always return false when hasNext() is called. (Recursive case) Remove and remember the first element (c) from the list Create and remember a new Permutations object (P) with the leftover list Obtain and remember the first permutation (L) from this new object, or an empty list if it has none (because it is size 0) Initialize an index counter (i) to 0. Each time the next () method is called on a Permutations object, it should do the following: Return a copy of L with c inserted at position i. Increment i Once i becomes too large set L to P.next() and reset i to 0. If P has no next permutation, then this object is finished as well. hasNext() should return false from here on out. Here's how it works for the list [0, 1, 2] For each permutation of [1, 2] Insert 0 into each position in the list. Thus successive calls to next return [0, 1, 2], [l, 0, 2], [1, 2, 0], [0, 2, 1], [2, 0, 1] and [2, 1, 0]. After this last list is returned, hasNext() should return false.Explanation / Answer
package net.coderodde.util;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
/**
* This class implements an {@code Iterable} returning all possible permutations
* of a list.
*
*/
public class Permutations<T> implements Iterable<List<T>> {
final List<T> allElements = new ArrayList<>();
public Permutations(List<T> allElements) {
this.allElements.addAll(allElements);
}
@Override
public Iterator<List<T>> iterator() {
return new PermutationIterator<>(allElements);
}
private static final class PermutationIterator<T>
implements Iterator<List<T>> {
private List<T> nextPermutation;
private final List<T> allElements = new ArrayList<>();
private int[] indices;
PermutationIterator(List<T> allElements) {
if (allElements.isEmpty()) {
nextPermutation = null;
return;
}
this.allElements.addAll(allElements);
this.indices = new int[allElements.size()];
for (int i = 0; i < indices.length; ++i) {
indices[i] = i;
}
nextPermutation = new ArrayList<>(this.allElements);
}
@Override
public boolean hasNext() {
return nextPermutation != null;
}
@Override
public List<T> next() {
if (nextPermutation == null) {
throw new NoSuchElementException("No permutations left.");
}
List<T> ret = nextPermutation;
generateNextPermutation();
return ret;
}
private void generateNextPermutation() {
int i = indices.length - 2;
while (i >= 0 && indices[i] > indices[i + 1]) {
--i;
}
if (i == -1) {
// No more new permutations.
nextPermutation = null;
return;
}
int j = i + 1;
int min = indices[j];
int minIndex = j;
while (j < indices.length) {
if (indices[i] < indices[j] && indices[j] < min) {
min = indices[j];
minIndex = j;
}
++j;
}
swap(indices, i, minIndex);
++i;
j = indices.length - 1;
while (i < j) {
swap(indices, i++, j--);
}
loadPermutation();
}
private void loadPermutation() {
List<T> newPermutation = new ArrayList<>(indices.length);
for (int i : indices) {
newPermutation.add(allElements.get(i));
}
this.nextPermutation = newPermutation;
}
}
private static void swap(int[] array, int a, int b) {
int tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
public static void main(final String... args) {
List<String> alphabet = Arrays.asList("A", "B", "C", "D");
int row = 1;
for (List<String> permutation : new Permutations<>(alphabet)) {
System.out.printf("%2d: %s ", row++, permutation);
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.