import java.util.*;
public class CombinationStuff
{
public static void main(String args[])
{
int nRows = 3;
int nCols = 3;
int a[][] = new int[nRows][nCols];
Integer input[] = new Integer[] { 0, 1, 2 };
CombinationIterable<Integer> ci =
new CombinationIterable<Integer>(nRows*nCols, input);
for (Integer s[] : ci)
{
fill(s,a);
control(a);
}
}
private static void fill(Integer s[], int a[][])
{
int index = 0;
for (int i=0; i<a.length; i++)
{
for (int j=0; j<a[i].length; j++)
{
a[i][j] = s[index];
index++;
}
}
}
private static boolean control(int a[][])
{
System.out.println("Control");
for (int i=0; i<a.length; i++)
{
System.out.println(Arrays.toString(a[i]));
}
return false;
}
}
/**
* A class providing an iterator over all combinations of a certain number
* of elements of a given set. For a set S with n = |S|, there are are n^k
* combinations of k elements of the set. This is the number of possible
* samples when doing sampling with replacement. Example:<br />
* <pre>
* S = { A,B,C }, n = |S| = 3
* k = 2
* m = n^k = 9
*
* Combinations:
* [A, A]
* [A, B]
* [A, C]
* [B, A]
* [B, B]
* [B, C]
* [C, A]
* [C, B]
* [C, C]
* </pre>
*
* @author [url]http://www.java-forum.org/members/Marco13.html[/url]
*/
class CombinationIterable<T> implements Iterable<T[]>
{
private T input[];
private int sampleSize;
private int numElements;
/**
* Creates an iterable over all multisets of
* 'sampleSize' elements of the given array.
*
* @param sampleSize
* @param input
*/
public CombinationIterable(int sampleSize, T... input)
{
this.sampleSize = sampleSize;
this.input = input.clone();
numElements = (int) Math.pow(input.length, sampleSize);
}
public Iterator<T[]> iterator()
{
return new Iterator<T[]>()
{
private int current = 0;
private int chosen[] = new int[sampleSize];
public boolean hasNext()
{
return current < numElements;
}
public T[] next()
{
@SuppressWarnings("unchecked")
T result[] = (T[]) java.lang.reflect.Array.newInstance(
input.getClass().getComponentType(), sampleSize);
for (int i = 0; i < sampleSize; i++)
{
result[i] = input[chosen[i]];
}
increase();
current++;
return result;
}
private void increase()
{
// The array of 'chosen' elements for a set of size n
// effectively is a number represented in k-ary form,
// and thus, this method does nothing else than count.
// For example, when choosing 2 elements of a set with
// n=10, the contents of 'chosen' would represent all
// values
// 00, 01, 02,... 09,
// 10, 11, 12,... 19,
// ...
// 90, 91, 92, ...99
// with each digit indicating the index of the element
// of the input array that should be placed at the
// respective position of the output array.
int index = chosen.length - 1;
while (index >= 0)
{
if (chosen[index] < input.length - 1)
{
chosen[index]++;
return;
}
else
{
chosen[index] = 0;
index--;
}
}
}
public void remove()
{
throw new UnsupportedOperationException(
"May not remove elements from a combination");
}
};
}
}
/**
* A class providing an iterator over all combinations of a certain number
* of elements from a given set, ignoring the order of the elements. For
* a set S with n = |S|, there are are (n+k-1)/(k!*(n-1)!) ways of
* choosing k elements from the set when the order of the elements in the
* resulting set should be ignored. This is, for example, the number of
* distinct results when throwing k dices with n sides. Example:<br />
* <pre>
* S = { A,B,C,D }, n = |S| = 4
* k = 2
* m = (n+k-1)/(k!*(n-1)!) = 10
*
* Unordered combinations of length 2:
* [A, A]
* [A, B]
* [A, C]
* [A, D]
* [B, B]
* [B, C]
* [B, D]
* [C, C]
* [C, D]
* [D, D]
* </pre>
*
* @author [url]http://www.java-forum.org/members/Marco13.html[/url]
*/
class UnorderedCombinationIterable<T> implements Iterable<T[]>
{
private T input[];
private int length;
private int numElements;
private Integer positions[];
public static int factorial(int n)
{
int f = 1;
for (int i = 2; i <= n; i++)
{
f *= i;
}
return f;
}
public UnorderedCombinationIterable(int length, T... input)
{
this.length = length;
this.input = input.clone();
numElements = factorial(input.length + length - 1) /
(factorial(length) *
factorial(input.length - 1));
int numPositions = length + input.length - 1;
positions = new Integer[numPositions];
for (int i = 0; i < numPositions; i++)
{
positions[i] = i;
}
}
public Iterator<T[]> iterator()
{
return new Iterator<T[]>()
{
private int current = 0;
private Iterator<Integer[]> positionChoiceIterator;
// Initialization of the positionChoiceIterator
{
ChoiceIterable<Integer> positionChoiceIterable =
new ChoiceIterable<Integer>(length, positions);
positionChoiceIterator = positionChoiceIterable.iterator();
}
public boolean hasNext()
{
return current < numElements;
}
public T[] next()
{
current++;
return toSelection(positionChoiceIterator.next());
}
private T[] toSelection(Integer positionChoice[])
{
// Selecting k elements from n elements, ignoring the
// order of the selected elements, may be formulated
// as selecting k elements from (n+k-1) elements
// obeying the order.
// The positionChoiceIterator provides choices of k
// elements from (n+k-1) elements, and they are converted
// to the corresponding selection of elements here.
//
// For example:
// 4 elements should be selected from a set of 6 elements,
// and the order of the selected elements is not relevant
// (like when rolling 4 six-sided dices).
// The positionChoiceIterator will be used for choosing
// 4 elements from (6+4-1)=9 elements. If it provides the
// choice 0,3,4,7 then this will be translated into a
// selection in the following way:
//
// Positions array : 012345678
// Choice done by positionChoiceIterator : 0 34 7
// For interpreting this choice, place
// asterisks at the respective positions
// filling the remaining positions with
// consecutive numbers : *12**34*5
// This pattern can then be interpreted as...
// - take 0 once
// - take 2 twice
// - take 4 once
// resulting the the selection 0,2,2,4
@SuppressWarnings("unchecked")
T result[] = (T[]) java.lang.reflect.Array.newInstance(
input.getClass().getComponentType(), length);
int currentValue = 0;
int currentIndex = 0;
for (int x = 0; x < positions.length; x++)
{
if (x == positionChoice[currentIndex])
{
result[currentIndex] = input[currentValue];
currentIndex++;
}
else
{
currentValue++;
}
if (currentIndex >= positionChoice.length)
{
break;
}
}
return result;
}
public void remove()
{
throw new UnsupportedOperationException(
"May not remove elements from a combination");
}
};
}
}
class ChoiceIterable<T> implements Iterable<T[]>
{
private T input[];
private int sampleSize;
private int numElements;
public static int factorial(int n)
{
int f = 1;
for (int i = 2; i <= n; i++)
{
f *= i;
}
return f;
}
/**
* Creates an iterable over all choices of 'sampleSize'
* elements taken from the given array.
*
* @param sampleSize
* @param input
*/
public ChoiceIterable(int sampleSize, T... input)
{
this.sampleSize = sampleSize;
this.input = input.clone();
numElements = factorial(input.length) /
(factorial(sampleSize) *
factorial(input.length - sampleSize));
}
public Iterator<T[]> iterator()
{
return new Iterator<T[]>()
{
private int current = 0;
private int chosen[] = new int[sampleSize];
// Initialization of first choice
{
for (int i = 0; i < sampleSize; i++)
{
chosen[i] = i;
}
}
public boolean hasNext()
{
return current < numElements;
}
public T[] next()
{
@SuppressWarnings("unchecked")
T result[] = (T[]) java.lang.reflect.Array.newInstance(
input.getClass().getComponentType(), sampleSize);
for (int i = 0; i < sampleSize; i++)
{
result[i] = input[chosen[i]];
}
current++;
if (current < numElements)
{
increase(sampleSize - 1, input.length - 1);
}
return result;
}
private void increase(int n, int max)
{
// The fist choice when choosing 3 of 5 elements consists
// of 0,1,2. Subsequent choices are created by increasing
// the last element of this sequence:
// 0,1,3
// 0,1,4
// until the last element of the choice has reached the
// maximum value. Then, the earlier elements of the
// sequence are increased recursively, while obeying the
// maximum value each element may have so that there may
// still be values assigned to the subsequent elements.
// For the example:
// - The element with index 2 may have maximum value 4.
// - The element with index 1 may have maximum value 3.
// - The element with index 0 may have maximum value 2.
// Each time that the value of one of these elements is
// increased, the subsequent elements will simply receive
// the subsequent values.
if (chosen[n] < max)
{
chosen[n]++;
for (int i = n + 1; i < sampleSize; i++)
{
chosen[i] = chosen[i - 1] + 1;
}
}
else
{
increase(n - 1, max - 1);
}
}
public void remove()
{
throw new UnsupportedOperationException(
"May not remove elements from a choice");
}
};
}
}
