001package com.hfg.math;
002
003import java.lang.reflect.Array;
004import java.util.ArrayList;
005import java.util.Collection;
006import java.util.Collections;
007import java.util.List;
008import java.util.Set;
009
010import com.hfg.util.collection.CollectionUtil;
011
012//------------------------------------------------------------------------------
013/**
014 Generate combinations of the specified size using the specified list of objects.
015 A combination is a set of objects in which position (or order) is NOT important.
016 <div>
017  @author J. Alex Taylor, hairyfatguy.com
018 </div>
019 */
020//------------------------------------------------------------------------------
021// com.hfg Library
022//
023// This library is free software; you can redistribute it and/or
024// modify it under the terms of the GNU Lesser General Public
025// License as published by the Free Software Foundation; either
026// version 2.1 of the License, or (at your option) any later version.
027//
028// This library is distributed in the hope that it will be useful,
029// but WITHOUT ANY WARRANTY; without even the implied warranty of
030// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
031// Lesser General Public License for more details.
032//
033// You should have received a copy of the GNU Lesser General Public
034// License along with this library; if not, write to the Free Software
035// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
036//
037// J. Alex Taylor, President, Founder, CEO, COO, CFO, OOPS hairyfatguy.com
038// jataylor@hairyfatguy.com
039//------------------------------------------------------------------------------
040
041public class Combinations
042{
043   //---------------------------------------------------------------------------
044   public static<T extends Comparable<? super T>> List<List<T>> combinations(List<T> inObjects, int inCombinationSize)
045   {
046      List<List<T>> combinations = null;
047      if (CollectionUtil.hasValues(inObjects))
048      {
049         if (inCombinationSize == 1)
050         {
051            combinations = new ArrayList<>(inObjects.size());
052            for (T obj : inObjects)
053            {
054               combinations.add(Collections.singletonList(obj));
055            }
056         }
057         else
058         {
059            combinations = new ArrayList<>();
060            for (int i = 0; i <= inObjects.size() - inCombinationSize; i++)
061            {
062               T firstItem = inObjects.get(i);
063               List<List<T>> additionalItems = combinations(inObjects.subList(i + 1, inObjects.size()), inCombinationSize - 1);
064               for (List<T> additional : additionalItems)
065               {
066                  List<T> combination = new ArrayList<>();
067                  combination.add(firstItem);
068                  combination.addAll(additional);
069                  combinations.add(combination);
070               }
071            }
072         }
073      }
074
075      return combinations;
076   }
077
078   //---------------------------------------------------------------------------
079   public static int countOfCombinationsWithRepetition(List<?> inObjects, int inCombinationSize)
080   {
081      int numCombinations = 0;
082
083      if (CollectionUtil.hasValues(inObjects))
084      {
085         if (inCombinationSize == 1)
086         {
087            // Special case if combination size is 1
088            numCombinations = inObjects.size();
089         }
090         else
091         {
092            int numeratorFactorial = inObjects.size() + inCombinationSize - 1;  // (n + r - 1)!
093            int denominatorFactorial = inObjects.size() - 1;  // (n - 1)!
094
095            long factorialDivisionResult = 1;
096            for (int i = denominatorFactorial + 1; i <= numeratorFactorial; i++)
097            {
098               factorialDivisionResult *= i;
099            }
100
101            numCombinations = (int) (factorialDivisionResult / MathUtil.factorial(inCombinationSize));
102         }
103      }
104
105      return numCombinations;
106   }
107
108   //---------------------------------------------------------------------------
109   public static<T extends Comparable<? super T>> List<T[]> combinationsWithRepetition(List<T> inObjects, int inCombinationSize)
110   {
111      List<T[]> combinations = null;
112
113      if (CollectionUtil.hasValues(inObjects))
114      {
115         if (inCombinationSize == 1)
116         {
117            // Special case if combination size is 1
118            combinations = new ArrayList<>(inObjects.size());
119            for (T obj : inObjects)
120            {
121               T[] combination = (T[]) Array.newInstance(inObjects.get(0).getClass(), inCombinationSize);
122               combination[0] = obj;
123               combinations.add(combination);
124            }
125         }
126         else
127         {
128            int numeratorFactorial = inObjects.size() + inCombinationSize - 1;  // (n + r - 1)!
129            int denominatorFactorial = inObjects.size() - 1;  // (n - 1)!
130
131            long factorialDivisionResult = 1;
132            for (int i = denominatorFactorial + 1; i <= numeratorFactorial; i++)
133            {
134               factorialDivisionResult *= i;
135            }
136
137            int numCombinations = (int) (factorialDivisionResult / MathUtil.factorial(inCombinationSize));
138            combinations = new ArrayList<>(numCombinations);
139
140            innerCombinationWithRepetition(inObjects, (T[]) Array.newInstance(inObjects.get(0).getClass(), inCombinationSize), 0, inCombinationSize, 0, inObjects.size() - 1, combinations);
141         }
142      }
143      return combinations;
144   }
145
146   //---------------------------------------------------------------------------
147   private static <T extends Comparable<? super T>> void innerCombinationWithRepetition(List<T> inObjects, T[] inChosen,
148                                                                                        int inIndex, int inCombinationSize, int inStartIdx, int inEndIdx, List<T[]> inCombinations)
149   {
150      // Since index has become r, current combination is ready to be printed, print
151      if (inIndex == inCombinationSize)
152      {
153         inCombinations.add(inChosen.clone());
154      }
155      else
156      {
157         // One by one choose all elements (without considering
158         // the fact whether element is already chosen or not)
159         // and recur
160         for (int i = inStartIdx; i <= inEndIdx; i++)
161         {
162            inChosen[inIndex] = inObjects.get(i);
163            innerCombinationWithRepetition(inObjects, inChosen, inIndex + 1, inCombinationSize, i, inEndIdx, inCombinations);
164         }
165      }
166   }
167}