Implement a class that works like an iterator and generates all permutations of
ID: 3714693 • Letter: I
Question
Implement a class that works like an iterator and generates all permutations of a list:
Implement a class that works like an iterator and generates all possible permutations of a list. It
cannot actually
be
an Iterator, because the ocial Java Iterator interface looks like the following:
public interface Iterator<E> {
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<E> {
public Permutations(List<E> list);
public boolean hasNext();
public List<E> next();
}
Notice the di erence? 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 rst element (
c
) from the list.
Create and remember a new Permutations object (
P
) with the leftover list.
Obtain and remember the rst 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.
2
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 nished 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], [1, 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.
Hint:
The list you return should be a newly-created one, either a LinkedList or an ArrayList
(your choice), with elements copied over. Don't try to use the same list that you were given in the
constructor, because you'd be disassembling it and reassembling it at multiple levels of recursion,
and it's almost impossible to keep it straight and do it right.
Extra Credit:
You should really think about doing this one, because it's a great way to test
your Permutations object. Use your Permutations object to implement the exponential NP sort
that we talked about in class. Generate all of the permutations of a list in turn, checking each one
to see if it's sorted. Stop when you nd the sorted list. How long a list can you sort using this
algorithm, before the time it takes becomes intolerable?
Explanation / Answer
PROGRAM:
package net.coderodde.util;
import java.util.List;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.NoSuchElementException;
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[] indces;
PermutationIterator(List<T> allElements) {
if (allElements.isEmpty()) {
nextPermutation = null;
return;
}
this.allElements.addAll(allElements);
this.indces = new int[allElements.size()];
for (int i = 0; i < indces.length; ++i) {
indces[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 = indces.length - 2;
while (i >= 0 && indces[i] > indces[i + 1]) {
--i;
}
if (i == -1) {
nextPermutation = null;
return;
}
int j = i + 1;
int min = indces[j];
int minIndex = j;
while (j < indces.length) {
if (indces[i] < indces[j] && indces[j] < min) {
min = indces[j];
minIndex = j;
}
++j;
}
swap(indces, i, minIndex);
++i;
j = indces.length - 1;
while (i < j) {
swap(indces, i++, j--);
}
loadPermutation();
}
private void loadPermutation() {
List<T> newPermutation = new ArrayList<>(indces.length);
for (int a : indces) {
newPermutation.add(allElements.get(a));
}
this.nextPermutation = newPermutation;
}
}
private static void swap(int[] array, int x, int y) {
int tmp = array[x];
array[x] = array[y];
array[y] = tmp;
}
public static void main(final String... args) {
List<String> alphabet = Arrays.asList("A", "B", "C", "D");
int rownum = 1;
for (List<String> permutation : new Permutations<>(alphabet)) {
System.out.printf("%2d: %s ", rownum++, permutation);
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.