Permutations · 1dir1

First of all, permutations are overrated. You will need to compute permutations a few times in your life, but then the rest will be all about reusing your last solution. On the other hand, iterators in java is a joy. Mostly when it’s about converting recursive solutions and feeding the results one by one non-recursively.

So now you know how I spent one my Friday nights.

Oh, by the way, this one can permutate some quite long sets since it doesn’t rely on recursion or the result of the factorial of the number of elements to fit in the range of long. Please let me know if you ever use it for such a long array before your computer dies a natural death.

import java.util.Iterator;
import java.util.NoSuchElementException;

@SuppressWarnings("javadoc")
public class Perm<T> implements Iterator<T[]> {
  private T[] input;
  private int[] posList;
  private long pos;
  private boolean lastItem;
  private T[] output;
  private int len;
  private boolean willCheckDups;
  private boolean willClone;

  public Perm(T[] inputs) {
    this(inputs, false);
  }

  public Perm(T[] inputs, boolean willClone) {
    this.input = inputs.clone();
    this.output = inputs.clone();
    this.len = this.input.length;
    this.posList = new int[this.len];
    for (int s = 0; s < this.len; s++) {
      this.posList[this.len - s - 1] = s;
    }
    this.willCheckDups = this.len >= 2;
    this.willClone = willClone;
  }

  @Override
  public boolean hasNext() {
    return !this.lastItem;
  }

  @Override
  public T[] next() {
    if (!this.hasNext()) {
      throw new NoSuchElementException();
    }
    for (int s = 0; s < this.len; s++) {
      this.output[s] = this.input[this.posList[s]];
    }
    this.pos++;
    incr();
    return this.willClone ? this.output.clone() : this.output;
  }

  private void incr() {
    do {
      int digit = 0;
      this.posList[digit]++;
      while (this.posList[digit] == this.len) {
        this.posList[digit] = 0;
        digit++;
        if (digit == this.len) {
          this.lastItem = true;
          break;
        }
        this.posList[digit]++;
      }
    } while (!this.willCheckDups || containsDuplicate());
  }

  private boolean containsDuplicate() {
    for (int dig = 0; dig < this.len; dig++) {
      for (int s = dig + 1; s < this.len; s++) {
        if (this.posList[s] == this.posList[dig]) {
          return true;
        }
      }
    }
    return false;
  }
}