/*
    * LetterOrder - Experimenting with the order of letters in words
    * Copyright (C) 2011-2015 Christian Schenk
    *
    * This program is free software: you can redistribute it and/or modify
    * it under the terms of the GNU Lesser General Public License as published by
    * the Free Software Foundation, either version 3 of the License, or
    * (at your option) any later version.
    *
   * This program is distributed in the hope that it will be useful,
   * but WITHOUT ANY WARRANTY; without even the implied warranty of
   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   * GNU Lesser General Public License for more details.
   *
   * You should have received a copy of the GNU Lesser General Public License
   * along with this program.  If not, see <http://www.gnu.org/licenses/>.
   */
  package org.christianschenk.letterorder.utils;
  
  import java.util.ArrayList;
  import java.util.Collections;
  import java.util.List;
  
  /**
   * Helps working with permutations.
   *
   * TODO: Implement caching of permutations.
   *
   * @author Christian Schenk
   */
  public class PermutationUtils {
  
  	/**
  	 * Returns a permutation of n elements in random order.
  	 *
  	 * @param n
  	 *            number of elements
  	 * @return random permutation
  	 */
  	@SuppressWarnings("boxing")
  	public int[] getRandomPermutation(final int n) {
  		final List<Integer> ints = new ArrayList<Integer>(n);
  		for (int i = 0; i < n; i++)
  			ints.add(i);
  		Collections.shuffle(ints, RandomUtils.RANDOM);
  
  		// XXX: All that may be implemented in a better way...
  		final int[] realInts = new int[n];
  		for (int i = 0; i < n; i++)
  			realInts[i] = ints.get(i);
  
  		return realInts;
  	}
  
  	/**
  	 * Implements the
  	 * <a href="https://en.wikipedia.org/w/index.php?oldid=662333702">
  	 * Steinhaus–Johnson–Trotter</a> algorithm.
  	 *
  	 * Uses primitive types due to performance considerations. The internal
  	 * methods used here silently agree that e.g. the <code>work</code> and
  	 * <code>dir</code> arrays are the same size thus minimizing any sanity
  	 * checks in the code.
  	 *
  	 * Since the factorial of n yields large numbers even for small values
  	 * of n one should make sure not to pass arbitrarily large numbers for n
  	 * to this method: at best it simply causes an {@link OutOfMemoryError}
  	 * or may run for a long time.
  	 *
  	 * @param n
  	 *            number of elements
  	 * @return permutations
  	 */
  	public int[][] getPermutations(final int n) {
  		return this.getPermutations(n, 0);
  	}
  
  	/**
  	 * See {@link #getPermutations(int)}.
  	 *
  	 * @param n
  	 *            number of elements
  	 * @param offset
  	 *            elements are initilized with this offset
  	 * @return permutations
  	 */
  	public int[][] getPermutations(final int n, final int offset) {
  		// Holds the results: n! * n elements
  		final int[][] results = new int[(int) this.factorial(n)][];
  		// 1, 2, ..., n
  		final int[] work = new int[n];
  		// 0 = left, 1 = right
  		final int[] dir = new int[n];
  
  		// Initialize
  		for (int i = 0; i < n; i++) {
  			work[i] = i + offset;
  			dir[i] = 0;
  		}
 
 		int step = 1;
 		results[0] = this.copy(work);
 		// print(work, dir);
 
 		while (this.hasMobile(work, dir)) {
 			final int curMobile = this.findLargestMobile(work, dir);
 
 			// swap, b = (a += b -= a) - b;
 			final int movePos = curMobile + (dir[curMobile] == 0 ? -1 : 1);
 			work[movePos] = (work[curMobile] += work[movePos] -= work[curMobile]) - work[movePos];
 			dir[movePos] = (dir[curMobile] += dir[movePos] -= dir[curMobile]) - dir[movePos];
 
 			// reverse direction
 			for (int i = 0; i < n; i++)
 				if (work[i] > work[movePos]) dir[i] = dir[i] == 0 ? 1 : 0;
 
 			// store
 			results[step] = this.copy(work);
 			step++;
 
 			// print(work, dir);
 		}
 
 		return results;
 	}
 
 	/**
 	 * Returns true if a mobile integer exists otherwise false.
 	 *
 	 * @param work
 	 *            array of the integer values
 	 * @param dir
 	 *            direction of the integer values
 	 * @return true if mobile integer exists otherwise false
 	 */
 	private boolean hasMobile(final int[] work, final int[] dir) {
 		for (int i = 0, n = work.length; i < n; i++) {
 			if (this.isMobile(work, dir, i)) return true;
 		}
 		return false;
 	}
 
 	/**
 	 * Returns true if the given integer is mobile otherwise false. An
 	 * integer is said to be mobile if, in the direction of its mobility,
 	 * the nearest integer is less than the current integer. Note that if an
 	 * integer is to the far left and its mobility is to the left, it is not
 	 * mobile. Similarly, if an integer is to the far right and its mobility
 	 * is to the right, it is also not mobile.
 	 *
 	 * @param work
 	 *            array of the integer values
 	 * @param dir
 	 *            direction of the integer values
 	 * @param i
 	 *            selected integer
 	 * @return true if selected integer is mobile otherwise false
 	 */
 	private boolean isMobile(final int[] work, final int[] dir, final int i) {
 		// leftmost integer pointing to the left is not mobile
 		// rightmost integer pointing to the right is not mobile
 		if ((i == 0 && dir[i] == 0) || (i == work.length - 1 && dir[i] == 1)) {
 			return false;
 		}
 		// An integer is mobile if, in the direction of its mobility, the
 		// nearest integer is less than the current integer.
 		if (i > 0 && dir[i] == 0 && work[i] > work[i - 1]) {
 			return true;
 		}
 		if (i < work.length - 1 && dir[i] == 1 && work[i] > work[i + 1]) {
 			return true;
 		}
 		if (i > 0 && i < work.length) {
 			if ((dir[i] == 0 && work[i] > work[i - 1]) || (dir[i] == 1 && work[i] > work[i + 1])) {
 				return true;
 			}
 		}
 
 		return false;
 	}
 
 	/**
 	 * Returns the index of the largest mobile integer.
 	 *
 	 * @param work
 	 *            array of the integer values
 	 * @param dir
 	 *            direction of the integer values
 	 * @return index of largest mobile integer
 	 */
 	private int findLargestMobile(final int[] work, final int[] dir) {
 		int largest = -1;
 		int pos = -1;
 		for (int i = 0, n = work.length; i < n; i++) {
 			if (this.isMobile(work, dir, i) && largest < work[i]) {
 				largest = work[i];
 				pos = i;
 			}
 		}
 		return pos;
 	}
 
 	/**
 	 * Evaluates n!
 	 *
 	 * @param n
 	 *            number
 	 * @return n!
 	 */
 	private long factorial(final int n) {
 		if (n <= 1) return 1;
 		return n * this.factorial(n - 1);
 	}
 
 	/**
 	 * Copies the given array and returns the copy.
 	 *
 	 * @param src
 	 *            source array
 	 * @return array with copied data from source array
 	 */
 	private int[] copy(final int[] src) {
 		final int[] dest = new int[src.length];
 		System.arraycopy(src, 0, dest, 0, src.length);
 		return dest;
 	}
 
 	/**
 	 * Displays the integers of the work array and the direction of the
 	 * individual items.
 	 *
 	 * @param work
 	 *            array of the integer values
 	 * @param dir
 	 *            direction of the integer values
 	 */
 	@SuppressWarnings("unused")
 	private void print(final int[] work, final int[] dir) {
 		for (int i = 0, n = work.length; i < n; i++)
 			System.out.print((dir[i] == 0 ? " <" : "  ") + work[i] + (dir[i] == 1 ? ">" : " "));
 		System.out.println("");
 	}
 }