123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117 |
- package pathgame.algorithm;
- /** Class for generating all possible permutations of travelling salesman paths
- *
- */
- public class Permutation {
- private int size;
- private int[] vals;
- private int[] minVals;
- private int minCost = Integer.MAX_VALUE;
- private int thingsPerPos;
- /** Creates a new Permutation based on the given parameters
- *
- * @param listSize size of the list the permutation is for
- * @param thingsPerPos number of list items per permutation position - for pairs: 2, for single items: 1
- */
- public Permutation(int listSize, int thingsPerPos) {
- this.thingsPerPos = thingsPerPos;
- this.size = (listSize/thingsPerPos) - 1;
- vals = new int[size];
- }
- /** Returns the offset stored at the given position
- *
- * @param pos position of the permutation from which the value should be returned
- * @return an offset of the Permutation
- */
- public int getValAtPos (int pos) {
- return vals[pos];
- }
- /** Returns true if the offset value at the given position can't be increased further
- *
- * @param pos position of the permutation that should be checked
- * @return whether offset at the given position is at its maximum
- */
- public boolean isPosAtMax (int pos) {
- if(vals[pos] == getMaxOfPos(pos)) {
- return true;
- }
- return false;
- }
- /** Returns the maximum value an offset can have at the given position
- *
- * @param pos position of the permutation that should be checked
- * @return the maximum value an offset can have at the given position
- */
- public int getMaxOfPos (int pos) {
- return thingsPerPos * (size - pos);
- }
- /** Returns the size of the permutation
- *
- * @return the size of the permutation
- */
- public int size() {
- return size;
- }
- /** Increases the offset at the given position by 1 and sets all offsets of higher positions back to 0
- *
- * @param pos position of the permutation that should be increased
- */
- public void increaseAtPos (int pos) {
- vals[pos]++;
- for(int i = pos+1; i < size; i++) {
- vals[i] = 0;
- }
- }
- /** Returns the minimum cost stored in this Permutation
- *
- * @return the minimum cost stored in this Permutation
- */
- public int getMinCost() {
- return minCost;
- }
- /** Sets the minimum cost stored in this Permutation
- *
- * @param minCost the new minimum cost to be set
- */
- public void setMinCost(int minCost) {
- this.minCost = minCost;
- minVals = vals.clone();
- }
- /** Makes the current permutation the new minimum permutation to be stored
- *
- */
- public void makePermutMinimal() {
- vals = minVals.clone();
- }
- /** Prints the current permutation
- *
- */
- public void printPermut() {
- for(int i = 0; i < size; i++) {
- System.out.print(vals[i] + " ");
- }
- System.out.println();
- }
- /** Prints the stored minimum permutation
- *
- */
- public void printMinPermut() {
- for(int i = 0; i < size; i++) {
- System.out.print(minVals[i] + " ");
- }
- System.out.println();
- }
- }
|