PROBLEM STATEMENT
In combinatory theory, given a set of elements S of size n, you are asked to
produce all k-tuples (k <= n). A k-tuple is some combination of k distinct
elements from S. This is called producing variations of k elements over the
n-element set S.
Let's consider a simple example:
Suppose S = {1, 2, 3, 4}, i.e. n = 4, and assume k = 3
Resulting variations are:
{1, 2, 3} {1, 3, 2} {2, 1, 3} {2, 3, 1} {3, 1, 2} {3, 2, 1}
{1, 2, 4} {1, 4, 2} {2, 1, 4} {2, 4, 1} {4, 1, 2} {4, 2, 1}
{1, 3, 4} {1, 4, 3} {3, 1, 4} {3, 4, 1} {4, 1, 3} {4, 3, 1}
{2, 3, 4} {2, 4, 3} {3, 2, 4} {3, 4, 2} {4, 2, 3} {4, 3, 2}
All variations should be ordered in the following manner:
1. If they have the same elements, ordering should be lexicographical:
e.g. {1, 3, 2} < {2, 1, 3} because 132 < 213
2. If they have different elements, ordering should be lexicographical, but
pre-sort each variation in ascending order:
e.g. {3, 2, 1} < {1, 2, 4}, because {1, 2, 3} < {1, 2, 4}
In the example above variations are ordered left to right, top to bottom.
In this problem you are to write a class Combinatorics that has a method
variate. The method should take as inputs: a set S, represented by an int[],
and an int k. As a result, you should return a String[] representing all
variations of length k, in the sorted order. The format of each String in the
String[] will be "<element1>,<element2>,...,<elementN>". All elements in a
given variation are separated by a comma. For instance, if you were to return
the 20 variations in the example above, it would look like this:
{"1,2,3", "1,3,2", "2,3,1", ..., "1,2,4", "1,4,2", ..., "4,3,2"}
In other words, it is a String[] containing the Strings "1,2,3", "1,3,2", etc.
DEFINITION
Class name: Combinatorics
Method name: variate
Parameters: int[], int
Returns: String[]
The method signature is (make sure your method is public): String[] (variate
int[] S, int k);
* S will contain between 1 and 6 elements, inclusive
* Each element of S will be between 0 and 9, inclusive
* There will be no repeating elements in S
* k will be less or equal to the size of S and greater than 0
EXAMPLES
S = {1}, k = 1 -> {"1"}
S = {1, 2}, k = 1 -> {"1", "2"}
S = {1, 2, 3}, k = 2 -> {"1,2", "2,1", "1,3", "3,1", "2,3", "3,2"}