patternjavaMinor
An iterator returning all possible permutations of a list in Java
Viewed 0 times
iteratoralljavapossiblereturninglistpermutations
Problem
I have this class that iterates over all permutations of an input list:
```
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.
*
* @author Rodion "rodde" Efremov
@version 1.6 (Feb 14, 2016) :
*/
public class PermutationIterable implements Iterable> {
final List allElements = new ArrayList<>();
public PermutationIterable(List allElements) {
this.allElements.addAll(allElements);
}
@Override
public Iterator> iterator() {
return new PermutationIterator<>(allElements);
}
private static final class PermutationIterator
implements Iterator> {
private List nextPermutation;
private final List allElements = new ArrayList<>();
private int[] indices;
PermutationIterator(List allElements) {
if (allElements.isEmpty()) {
nextPermutation = null;
return;
}
this.allElements.addAll(allElements);
this.indices = new int[allElements.size()];
for (int i = 0; i (this.allElements);
}
@Override
public boolean hasNext() {
return nextPermutation != null;
}
@Override
public List next() {
if (nextPermutation == null) {
throw new NoSuchElementException("No permutations left.");
}
List 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.
ne
PermutationIterable.java:```
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.
*
* @author Rodion "rodde" Efremov
@version 1.6 (Feb 14, 2016) :
*/
public class PermutationIterable implements Iterable> {
final List allElements = new ArrayList<>();
public PermutationIterable(List allElements) {
this.allElements.addAll(allElements);
}
@Override
public Iterator> iterator() {
return new PermutationIterator<>(allElements);
}
private static final class PermutationIterator
implements Iterator> {
private List nextPermutation;
private final List allElements = new ArrayList<>();
private int[] indices;
PermutationIterator(List allElements) {
if (allElements.isEmpty()) {
nextPermutation = null;
return;
}
this.allElements.addAll(allElements);
this.indices = new int[allElements.size()];
for (int i = 0; i (this.allElements);
}
@Override
public boolean hasNext() {
return nextPermutation != null;
}
@Override
public List next() {
if (nextPermutation == null) {
throw new NoSuchElementException("No permutations left.");
}
List 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.
ne
Solution
Your solution looks good. It's a really challenging task. This is because you have to "flatten" an algorithm with recursive nature. Furthermore you have to break it apart into single steps and to be able to resume at the last step made.
So there are little things that I would change:
You see that our solutions do not differ in structure. Only the algorithm to generate a new permutation is extracted in a class and reformulated.
I unpacked this riddle (I somehow liked this riddle) and I want to provide a solution that can use either your algorithm or mine. But finally they converged against the same interface. I expected that as I know there is only one structure that fits the problem best. We may not have found it but both solutions have a "meeting" where the structure is mostly the same AND the things that may be different can work under the same abstraction. Sure, most structure was provided by the interfaces "Iterable" and "Iterator" but I found it interesting how the algorithms are interchangeable.
So first of all the interface for our algorithms:
Your algorithm:
Mine:
The iterator:
The iterable:
```
public class PermutationIterable implements Iterable> {
private List base;
private PermutationResolver
So there are little things that I would change:
- I like separated classes instead of inner classes they are more handy in testing
- I would have separated the algorithm in "generateNextPermutation()" in an additional class.
- I would follow the recursive nature of the problem and build a recursive structure. This is a slightly different approach.
- I do not exactly know how the algorithm should behave if you provide an empty list. I assume that you will have one permutation as result. So I adapted your algorithm to work with an empty array of indices.
You see that our solutions do not differ in structure. Only the algorithm to generate a new permutation is extracted in a class and reformulated.
I unpacked this riddle (I somehow liked this riddle) and I want to provide a solution that can use either your algorithm or mine. But finally they converged against the same interface. I expected that as I know there is only one structure that fits the problem best. We may not have found it but both solutions have a "meeting" where the structure is mostly the same AND the things that may be different can work under the same abstraction. Sure, most structure was provided by the interfaces "Iterable" and "Iterator" but I found it interesting how the algorithms are interchangeable.
So first of all the interface for our algorithms:
public interface PermutationResolver {
List resolvePermutation(List base);
boolean nextStep();
}Your algorithm:
public class IndicesWalker implements PermutationResolver {
private int[] indices;
public IndicesWalker(int elements) {
indices = new int[elements];
for (int i = 0; i = 0 && indices[i] > indices[i + 1]) {
--i;
}
if (i == -1) {
// No more new permutations.
return false;
}
int j = i + 1;
int min = indices[j];
int minIndex = j;
while (j resolvePermutation(List base) {
List newPermutation = new ArrayList<>(indices.length);
for (int i : indices) {
newPermutation.add(base.get(i));
}
return newPermutation;
}
private void swap(int[] array, int a, int b) {
int tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
}Mine:
public class RecursiveCounter implements PermutationResolver {
private int i;
private int max;
private RecursiveCounter nextState;
public RecursiveCounter(int max) {
this.max = max;
this.i = 0;
if (this.max > 1) {
nextState = new RecursiveCounter(max - 1);
}
}
@Override
public boolean nextStep() {
boolean wasIncremented = true;
if (nextState != null) {
if (!nextState.nextStep()) {
if (this.i == this.max - 1) {
this.i = 0;
wasIncremented = false;
} else {
i++;
}
}
} else {
wasIncremented = false;
}
return wasIncremented;
}
private int getI(int level) {
if (level == 0) {
return this.i;
} else {
return nextState.getI(level - 1);
}
}
@Override
public List resolvePermutation(List base) {
List result = new ArrayList<>();
List work = new ArrayList<>(base);
for(int i = 0; i < base.size(); i++) {
result.add(work.remove(getI(i)));
}
return result;
}
}The iterator:
public class PermutationIterator implements Iterator> {
private List base;
private PermutationResolver permutationResolver;
private List next;
public PermutationIterator(List base, PermutationResolver resolver) {
this.base = base;
this.next = new ArrayList<>(base);
this.permutationResolver = resolver;
}
private List generateNextPermutation(boolean isLast) {
List result = null;
if (!isLast) {
result = getPermutationResolver().resolvePermutation(base);
}
return result;
}
@Override
public boolean hasNext() {
return next != null;
}
@Override
public List next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
List current = next;
this.next = generateNextPermutation(!getPermutationResolver().nextStep());
return current;
}
private PermutationResolver getPermutationResolver() {
return permutationResolver;
}
}The iterable:
```
public class PermutationIterable implements Iterable> {
private List base;
private PermutationResolver
Code Snippets
public interface PermutationResolver<T> {
List<T> resolvePermutation(List<T> base);
boolean nextStep();
}public class IndicesWalker<T> implements PermutationResolver<T> {
private int[] indices;
public IndicesWalker(int elements) {
indices = new int[elements];
for (int i = 0; i < indices.length; ++i) {
indices[i] = i;
}
}
@Override
public boolean nextStep() {
if (indices.length == 0) return false;
int i = indices.length - 2;
while (i >= 0 && indices[i] > indices[i + 1]) {
--i;
}
if (i == -1) {
// No more new permutations.
return false;
}
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--);
}
return true;
}
@Override
public List<T> resolvePermutation(List<T> base) {
List<T> newPermutation = new ArrayList<>(indices.length);
for (int i : indices) {
newPermutation.add(base.get(i));
}
return newPermutation;
}
private void swap(int[] array, int a, int b) {
int tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
}public class RecursiveCounter<T> implements PermutationResolver<T> {
private int i;
private int max;
private RecursiveCounter<T> nextState;
public RecursiveCounter(int max) {
this.max = max;
this.i = 0;
if (this.max > 1) {
nextState = new RecursiveCounter<T>(max - 1);
}
}
@Override
public boolean nextStep() {
boolean wasIncremented = true;
if (nextState != null) {
if (!nextState.nextStep()) {
if (this.i == this.max - 1) {
this.i = 0;
wasIncremented = false;
} else {
i++;
}
}
} else {
wasIncremented = false;
}
return wasIncremented;
}
private int getI(int level) {
if (level == 0) {
return this.i;
} else {
return nextState.getI(level - 1);
}
}
@Override
public List<T> resolvePermutation(List<T> base) {
List<T> result = new ArrayList<>();
List<T> work = new ArrayList<>(base);
for(int i = 0; i < base.size(); i++) {
result.add(work.remove(getI(i)));
}
return result;
}
}public class PermutationIterator<T> implements Iterator<List<T>> {
private List<T> base;
private PermutationResolver<T> permutationResolver;
private List<T> next;
public PermutationIterator(List<T> base, PermutationResolver<T> resolver) {
this.base = base;
this.next = new ArrayList<>(base);
this.permutationResolver = resolver;
}
private List<T> generateNextPermutation(boolean isLast) {
List<T> result = null;
if (!isLast) {
result = getPermutationResolver().resolvePermutation(base);
}
return result;
}
@Override
public boolean hasNext() {
return next != null;
}
@Override
public List<T> next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
List<T> current = next;
this.next = generateNextPermutation(!getPermutationResolver().nextStep());
return current;
}
private PermutationResolver<T> getPermutationResolver() {
return permutationResolver;
}
}public class PermutationIterable<T> implements Iterable<List<T>> {
private List<T> base;
private PermutationResolver<T> resolver;
public PermutationIterable(List<T> base, PermutationResolver<T> resolver) {
super();
this.base = base;
this.resolver = resolver;
}
@Override
public Iterator<List<T>> iterator() {
return new PermutationIterator<T>(base, resolver);
}
}Context
StackExchange Code Review Q#119969, answer score: 3
Revisions (0)
No revisions yet.