Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- ****************************************************************************************************************
- * Copyright 2015 Fred Pang fred@pnode.com
- ****************************************************************************************************************
- * A complete list of Permutation base on an index.
- * Algorithm is invented and implemented by Fred Pang fred@pnode.com
- * Created by Fred Pang on 18/11/2015.
- ****************************************************************************************************************
- * LOL this is my first Java project. Therefore, my code is very much like C/C++. The coding itself is not
- * very professional. but...
- *
- * This Permutation Class can be use to generate a complete list of all different permutation of a set of symbols.
- * nPr will be n!/(n-r)!
- * the user can input n = the number of items,
- * r = the number of slots for the items,
- * provided n >= r
- * and a string of single character symbols
- *
- * the program will generate all possible permutation for the condition.
- *
- * Say if n = 5, r = 3, and the string is "12345", it will generate sll 60 different permutation of the set
- * of 3 character strings.
- *
- * The algorithm I used is base on a bin slot.
- * Just like a human or simply myself to generate a permutation.
- *
- * if there are 5 symbols to chose from, I'll have 5 bin slot to indicate which symbol is taken.
- *
- * Note that, once the Permutation object is initialized, or after the constructor is called, the permutation
- * table and all entries are defined, including an index.
- *
- * eg. if pass in value is 5 chose 3, and say the symbol string is "12345"
- * then all permutation table is logically defined (not physically to save memory).
- * It will be a table as follows
- * index output
- * 0 123
- * 1 124
- * 2 125
- * 3 132
- * 4 134
- * 5 135
- * 6 143
- * 7 145
- * : :
- * 58 542
- * 59 543
- *
- * all you need to do is call the "String PermGetString(int iIndex)" or the "int[] PermGetIntArray(int iIndex)"
- * function or method with an increasing iIndex, starting from 0 to getiMaxIndex() - 1. It will return the string
- * or the integer array corresponding to the index.
- *
- * Also notice that in the input string is "12345" of position 01234, and the output is always in accenting order
- * this is how the permutation is generated.
- *
- * ***************************************************************************************************************
- * ==== W a r n i n g ====
- * ***************************************************************************************************************
- *
- * There is very limited error checking in this class
- *
- * Especially the int PermGetIndex(int[] iInputArray) method
- * if the input integer array contains invalid index, it WILL crash the system
- *
- * the other is the string of symbol pass in when the object is created, not sure what will happen if the
- * string is invalid.
- * ***************************************************************************************************************
- *
- */
- public class Permutation
- {
- private boolean bGoodToGo = false; // object status
- private boolean bNoSymbol = true;
- private BinSlot slot; // a bin slot of size n (input)
- private int nTotal; // n number for permutation
- private int rChose; // r position to chose
- private String sSymbol; // character string for symbol of each choice
- private String sOutStr;
- private int iMaxIndex; // maximum index allowed in the Get index function
- private int[] iOutPosition; // output array
- private int[] iDivisorArray; // array to do calculation
- public Permutation(int inCount, int irCount, String symbol)
- {
- if (inCount >= irCount)
- {
- // save all input values passed in
- this.nTotal = inCount;
- this.rChose = irCount;
- this.sSymbol = symbol;
- // some error checking
- if (inCount < irCount || irCount <= 0)
- return; // do nothing will not set the bGoodToGo flag
- if (this.sSymbol.length() >= inCount)
- {
- bNoSymbol = false;
- }
- // allocate output storage
- this.iOutPosition = new int[this.rChose];
- // initialize the bin slot with the right size
- this.slot = new BinSlot(this.nTotal);
- // allocate and initialize divid array
- this.iDivisorArray = new int[this.rChose];
- // calculate default values base on n & r
- this.iMaxIndex = CalPremFormula(this.nTotal, this.rChose);
- int i;
- int j = this.nTotal - 1;
- int k = this.rChose - 1;
- for (i = 0; i < this.rChose; i++)
- {
- this.iDivisorArray[i] = CalPremFormula(j--, k--);
- }
- bGoodToGo = true; // we are ready to go
- }
- }
- public String PermGetString(int iIndex)
- {
- if (!this.bGoodToGo) return "Error: Object not initialized Correctly";
- if (this.bNoSymbol) return "Error: Invalid symbol string";
- if (!this.PermEvaluate(iIndex)) return "Invalid Index";
- sOutStr = "";
- // convert string back to String output
- for (int i = 0; i < this.rChose; i++)
- {
- String sTempStr = this.sSymbol.substring(this.iOutPosition[i], iOutPosition[i] + 1);
- this.sOutStr = this.sOutStr.concat(sTempStr);
- }
- return this.sOutStr;
- }
- public int[] PermGetIntArray(int iIndex)
- {
- if (!this.bGoodToGo) return null;
- if (!this.PermEvaluate(iIndex)) return null ;
- return this.iOutPosition;
- }
- // given an int array, and get the index back.
- //
- // ====== W A R N I N G ======
- //
- // there is no error check in the array that pass in
- // if any invalid value in the input array, it can cause system crash or other unexpected result
- //
- // function pass in an int array generated by the PermGetIntArray() method
- // then return the index value.
- //
- // this is the reverse of the PermGetIntArray()
- //
- public int PermGetIndex(int[] iInputArray)
- {
- if (!this.bGoodToGo) return -1;
- return PermDoReverse(iInputArray);
- }
- public int getiMaxIndex() {
- return iMaxIndex;
- }
- // function to evaluate nPr = n!/(n-r)!
- public int CalPremFormula(int n, int r)
- {
- int j = n;
- int k = 1;
- for (int i = 0; i < r; i++, j--)
- {
- k *= j;
- }
- return k;
- }
- // PermEvaluate function (method) base on an index input, evaluate the correspond permuted symbol location
- // then output it to the iOutPosition array.
- //
- // In the iOutPosition[], each array element corresponding to the symbol location in the input string symbol.
- // from location 0 to length of string - 1.
- private boolean PermEvaluate(int iIndex)
- {
- int iCurrentIndex;
- int iCurrentRemainder;
- int iCurrentValue = iIndex;
- int iCurrentOutSlot;
- int iLoopCount;
- if (iIndex >= iMaxIndex)
- return false;
- this.slot.binReset(); // clear bin content
- iLoopCount = 0;
- do {
- // evaluate the table position
- iCurrentIndex = iCurrentValue / this.iDivisorArray[iLoopCount];
- iCurrentRemainder = iCurrentValue % this.iDivisorArray[iLoopCount];
- iCurrentOutSlot = this.slot.FindFreeBin(iCurrentIndex); // find an available slot
- if (iCurrentOutSlot >= 0)
- this.iOutPosition[iLoopCount] = iCurrentOutSlot;
- else return false; // fail to find a slot, quit now
- this.slot.setStatus(iCurrentOutSlot); // set the slot to be taken
- iCurrentValue = iCurrentRemainder; // set new value for current value.
- iLoopCount++; // increase counter
- } while (iLoopCount < this.rChose);
- // the output is ready in iOutPosition[]
- return true;
- }
- //
- // this function is doing the reverse of the permutation
- // the input is a permutation and will find the correspond index value for that entry
- // which is doing the opposit of the PermEvaluate() method
- //
- private int PermDoReverse(int[] iInputArray)
- {
- int iReturnValue = 0;
- int iLoopIndex;
- int iCurrentValue;
- int iBinLocation;
- this.slot.binReset(); // clear bin content
- for (iLoopIndex = 0; iLoopIndex < this.rChose; iLoopIndex++)
- {
- iCurrentValue = iInputArray[iLoopIndex];
- iBinLocation = this.slot.BinCountFree(iCurrentValue);
- this.slot.setStatus(iCurrentValue); // set the slot to be taken
- iReturnValue = iReturnValue + iBinLocation * this.iDivisorArray[iLoopIndex];
- }
- return iReturnValue;
- }
- /*******************************************************************************************************************
- *******************************************************************************************************************
- * Created by Fred on 18/11/2015. fred@pnode.com
- *
- * *****************************************************************************************************************
- */
- private static class BinSlot
- {
- private int iBinSize; // size of array
- private short[] eStatus; // the status array must have length iBinSize
- private BinSlot(int iBinSize)
- {
- this.iBinSize = iBinSize; // save bin size
- this.eStatus = new short[iBinSize]; // llocate status array
- }
- // reset the bin content. no symbol is in use
- private void binReset()
- {
- // reset the bin's content
- for (int i = 0; i < this.iBinSize; i++) this.eStatus[i] = 0;
- }
- // set the bin position as taken or the number is already used, cannot be use again.
- private void setStatus(int iIndex) { this.eStatus[iIndex]= 1; }
- //
- // to search for the iIndex th unused symbol
- // this is important to search through the iindex th symbol
- // because this is how the table is setup. (or the remainder means)
- // note: iIndex is the remainder of the calculation
- //
- // for example:
- // in a 5 choose 3 permutation symbols "12345",
- // the index 7 item (count starting from 0) element is "1 4 3"
- // then comes the index 8, 8/12 result 0 -> 0th symbol in symbol string = '1'
- // remainder 8. then 8/3 = 2, now we need to scan the Bin and skip 2 unused bins
- // current the bin looks 0 1 2 3 4
- // x o o o o x -> in use; o -> free only 0 is being used
- // s s ^ skipped 2 bins (bin 1 and 2), we get to bin 3
- // and bin 3 is the bin needed. Thus symbol "4" is pick
- // in 8/3, there is a remainder 2 comes in this function as 2/1 = 2, now we have to pick the empty slot
- // for the new 2.
- // the bin now looks 0 1 2 3 4
- // x 0 0 x 0 as bin 3 was used by the last value
- // s s ^ we skip 2 free bins and the next free bin is bin 4
- // therefor the symbol "5" at the symbol array is pick.
- //
- // Thus, for index 8 "1 4 5" is the symbols.
- //
- //
- private int FindFreeBin(int iIndex)
- {
- int j = iIndex;
- if (j < 0 || j > this.iBinSize) return -1; // invalid index
- for (int i = 0; i < this.iBinSize; i++)
- {
- if (this.eStatus[i] == 0) // is it used
- {
- // found an empty slot
- if (j == 0) // this is a free one we want?
- return i; // yes, found and return it.
- else // we have to skip this one
- j--; // else, keep looking and count the skipped one
- }
- }
- assert(true); // something is wrong
- return -1; // fail to find the bin we wanted
- }
- //
- // this function is to help the PermDoReverse() to find out what is the corresponding
- // value during should be added to the index value.
- //
- // it is doing the opposite of int FindFreeBin(int iIndex) method. You need to know how this
- // FindFreeBin() works before looking into this function.
- //
- private int BinCountFree(int iIndex)
- {
- int iRetVal = 0;
- for (int i = iIndex; i > 0; i--)
- {
- if (this.eStatus[i-1] == 0) // it is free
- {
- iRetVal++;
- }
- }
- return iRetVal;
- }
- }
- }
- // End of file - Permutation.java
- /*
- * copyright 2015 Fred Pang
- *
- * This is the main test program for testing the Permutation Class I created.
- * It can be use to demonstrate how to use the Permutation Class and its methods to generate a complete
- * list of a permutation. It also support function to get back the index value as pass in a permutation.
- *
- * As you can see my Java is not very good. :)
- * This is my 1st Java project I created. As I am a C/C++ programmer for years.
- *
- * I still have problem with the Scanner class and the System class.
- * Note that there is only very limited error checking
- *
- *
- */
- import java.util.Scanner;
- public class Main
- {
- private static Scanner scanner = new Scanner(System.in);
- public static void main(String[] args)
- {
- Permutation perm; // declear the object
- String sOutString = "";
- int nCount;
- int rCount;
- int iMaxIndex;
- // Get user input
- System.out.println("Enter n: ");
- nCount = scanner.nextInt();
- System.out.println("Enter r: ");
- rCount = scanner.nextInt();
- System.out.println("Enter Symbol: ");
- sOutString = scanner.next();
- if (sOutString.length() < rCount)
- {
- System.out.println("String too short, default to numbers");
- sOutString = "";
- }
- // create object with user requirement
- perm = new Permutation(nCount, rCount, sOutString);
- // and print the maximum count
- iMaxIndex = perm.getiMaxIndex();
- System.out.println("Max count is:" + iMaxIndex);
- if (!sOutString.isEmpty())
- {
- for (int i = 0; i < iMaxIndex; i++)
- { // print out the return permutation symbol string
- System.out.println(i + " " + perm.PermGetString(i));
- }
- }
- else
- {
- for (int i = 0; i < iMaxIndex; i++)
- {
- System.out.print(i + " ->");
- // Get the permutation array
- int[] iTemp = perm.PermGetIntArray(i);
- // print out the permutation
- for (int j = 0; j < rCount; j++)
- {
- System.out.print(' ');
- System.out.print(iTemp[j]);
- }
- // to verify my PermGetIndex() works. :)
- if (perm.PermGetIndex(iTemp)== i)
- {
- System.out.println(" .");
- }
- else
- { // oops something is wrong :(
- System.out.println(" ***************** F A I L E D *************************");
- assert(true);
- break;
- }
- }
- }
- }
- }
- //
- // End of file - Main.java
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement