001package com.hfg.math;
002
003
004import java.lang.reflect.Array;
005import java.util.ArrayList;
006import java.util.List;
007
008import com.hfg.util.collection.CollectionUtil;
009
010//------------------------------------------------------------------------------
011/**
012 Utility functions for creating permutations.
013 Permutations are for lists (order matters) and combinations are for groups (order doesn’t matter).
014 <div>
015 @author J. Alex Taylor, hairyfatguy.com
016 </div>
017 */
018//------------------------------------------------------------------------------
019// com.hfg Library
020//
021// This library is free software; you can redistribute it and/or
022// modify it under the terms of the GNU Lesser General Public
023// License as published by the Free Software Foundation; either
024// version 2.1 of the License, or (at your option) any later version.
025//
026// This library is distributed in the hope that it will be useful,
027// but WITHOUT ANY WARRANTY; without even the implied warranty of
028// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
029// Lesser General Public License for more details.
030//
031// You should have received a copy of the GNU Lesser General Public
032// License along with this library; if not, write to the Free Software
033// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
034//
035// J. Alex Taylor, President, Founder, CEO, COO, CFO, OOPS hairyfatguy.com
036// jataylor@hairyfatguy.com
037//------------------------------------------------------------------------------
038
039
040public class Permutations
041{
042   //---------------------------------------------------------------------------
043   public static<T> List<T[]> permutationsWithRepetition(List<T> inObjects, int inPermutationSize)
044   {
045      List<T[]> combinations = null;
046
047      if (CollectionUtil.hasValues(inObjects))
048      {
049         if (inPermutationSize == 1)
050         {
051            // Special case if permutation size is 1
052            combinations = new ArrayList<>(inObjects.size());
053            for (T obj : inObjects)
054            {
055               T[] combination = (T[]) Array.newInstance(inObjects.get(0).getClass(), inPermutationSize);
056               combination[0] = obj;
057               combinations.add(combination);
058            }
059         }
060         else
061         {
062            int numCombinations = (int) Math.pow(inObjects.size(), inPermutationSize);
063            combinations = new ArrayList<>(numCombinations);
064
065            innerPermutationsWithRepetition(inObjects, (T[]) Array.newInstance(inObjects.get(0).getClass(), inPermutationSize), 0, combinations);
066         }
067      }
068      return combinations;
069   }
070
071   //---------------------------------------------------------------------------
072   private static <T> void innerPermutationsWithRepetition(List<T> inObjects, T[] inArray, int inCurrentIndex, List<T[]> inPermutations)
073   {
074      if (inCurrentIndex < inArray.length)
075      {
076         for (int i = 0; i < inObjects.size(); i++)
077         {
078            T[] oldArray = inArray.clone();
079            inArray[inCurrentIndex] = inObjects.get(i);
080            innerPermutationsWithRepetition(inObjects, inArray, inCurrentIndex + 1, inPermutations);
081            inArray = oldArray;
082         }
083      }
084      else
085      {
086         inPermutations.add(inArray);
087      }
088   }
089}