Combinations with repetitions
Combinations with repetitions is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Write a program which generates the all k-combination with repetitions of n different objects. (Practically numerals!)
Java
Using the code of Michael Pryor. You can use this code not only for standard k-combination with repetitions, but for a object list too. E.g. list=(1, 2, 2, 3) or for other needed lists.
MultiCombinationData.java <lang java> public class MultiCombinationData {
private int n = 0; private int k = 0;
public MultiCombinationData(int n, int k) { this.n = Math.max(n, 0); this.k = Math.max(k, 0); }
public int getN() { return n; }
public int getK() { return k; }
} // class </lang>
MultiCombinationGenerator.java <lang java> import java.util.*;
public class MultiCombinationGenerator {
private MultiCombinationData data = null; private Vector<Integer> list = new Vector<Integer>(); private HashSet<Vector<Integer>> result = new HashSet<Vector<Integer>>();
public MultiCombinationGenerator(MultiCombinationData data) { if (data != null) { this.data = data; if (data.getN() > 0 && data.getK() > 0) { for (int i = 1; i <= data.getN(); i++) { for (int j = 0; j < data.getK(); j++) { list.add(i); } } } } }
public MultiCombinationGenerator(int... integers) { for (int i = 0; i < integers.length; i++) { list.add(integers[i]); } }
public void generate(int k) throws Exception { result.clear(); if (k > list.size() || k < 0) { throw new Exception("Error: wrong value of k. (k = " + k + ")"); } else { generate(new Vector<Integer>(), k, 0); } }
public void generate() throws Exception { if (data != null) { generate(data.getK()); } }
private void generate(Vector<Integer> aList, int k, int currPos) { if (k == 0) { result.add(new Vector<Integer>(aList)); } else if ((list.size() - currPos) >= k) { generate(aList, k, currPos + 1); aList.add(list.get(currPos)); generate(aList, k - 1, currPos + 1); aList.removeElementAt(aList.size() - 1); } }
void print() throws Exception { result = getResult(); for (Vector<Integer> anIntegerVector : result) { System.out.println(anIntegerVector.toString()); } }
public HashSet<Vector<Integer>> getResult() throws Exception { if (result.size() == 0) { generate(); } return result; }
public static void main(String[] args) { int n = 3; int k = 2;
System.out.println("Combination with repetitions. n=3 k=2"); MultiCombinationGenerator rcg1 = new MultiCombinationGenerator(new MultiCombinationData(n, k)); try { rcg1.print(); } catch (Exception ex) { System.out.println(ex.getMessage()); }
System.out.println();
System.out.println("Combination of a repetitions list. list=(1, 2, 2, 3) k=2"); MultiCombinationGenerator rcg2 = new MultiCombinationGenerator(1, 2, 2, 3); try { rcg2.generate(k); rcg2.print(); } catch (Exception ex) { System.out.println(ex.getMessage()); } } // main()
} // class </lang>
I got this output:
Combination with repetitions. n=3 k=2 [1, 1] [2, 2] [1, 3] [2, 3] [1, 2] [3, 3] Combination of a repetitions list. list=(1, 2, 2, 3) k=2 [2, 2] [1, 3] [2, 3] [1, 2]