All possible combinations of n vectors with k elements
Dear all,
I have a method which takes as input N vectors each one containing K strings.
I want all the possible combinations of strings occurring if I select only one string at a time from each vector and from all vectors.
For example:
If I have the vectors:
v1[A, B, C] v2[H, k] and v3[k, O, P]
an acceptable value could be: A,k,k or B,H,P and so on.
I tried to implement my own algorithm but I couldn't get it right.
I would like to ask if there is any similar algorithm which can be applied for my problem or any suggestions of how I should think about it.
Thank you very much.
Shakur.
[658 byte] By [
ShakuR_a] at [2007-11-27 6:44:09]
# 2
Hello prometheuzz ,
Thanks for your answer.
I will try to explain my problem and the incomplete solution I have tried.
First of all I have one Vector named attributes which can include arbitrary number of lets say attribute vectors . Each of these attribute vectors includes arbitrary number of strings. I want to find all the possible string combinations if I can select exactly one string from each attribute vector and I have to select a string from all the attribute vectors.
Example:
Lets say that the given attributes vector contains the attribute vectors:
names:['John', 'Tom', 'Nick']
teams:['A', 'B']
class:['F', 'N']
Then the desired outcome should be:
John, A, F
John, A, N
John, B, F
John, B, N
Tom, A, F
Tom, A, N
Tom, B, N
Tom, B, F
Nick, A, F
Nick, A, N
Nick, B, F
Nick, B, N
My Solution
Please note that my solution is incomplete and maybe totally wrong so you can ignore it and give me some other direction to follow.
What I have tried to do was to create pairs of values with the current attribute's strings and the strings of the next one:
Vector pair = new Vector();
Vector v = new Vector();
pair.add ('John');
pair.add('A');
v.add(pair);
pair.add ('John');
pair.add('B');
v.add(pair);
This continues for all the pairs between the current attribute vector and the next one. Finally I will come up with a vector named values which contains value. vectors. The value vectors contain all the v vectors which contain pair vectors. For example for the 'John' element of the names attribute a v vector will created, for the 'Tom' element another v and for the element 'Nick' a third v Vector. The code below implements what I have tried to describe.
public void produceValues (Vector attributes)
{
Vector currAttr;
Vector nextAttr;
Vector <Vector> values = new Vector<Vector>();
Vector <Vector> value;
Vector <Vector> v;
Vector <String> pair ;
Iterator caItr, naItr;
String currElement;
if(attributes.size()>1)
{
for(int i=0; i<attributes.size()-1; i++)
{
currAttr = (Vector) attributes.elementAt(i);
nextAttr = (Vector) attributes.elementAt(i+1);
caItr = currAttr.iterator();
naItr = nextAttr.iterator();
value = new Vector><Vector>();
while (caItr.hasNext())
{
v = new Vector();
currElement = (String) caItr.next();
while (naItr.hasNext())
{
pair = new Vector<String>();
pair.addElement(currElement);
pair.addElement((String) naItr.next());
v.addElement(pair);
}
value.addElement(v);
}
values.addElement(value);
}
combineValues(values);
}
else
{
; //Later
}
}
After the values vector was created I tried to produce the desired output by combining the pairs. With the code below I tried to iterate the values, value, v and pair vectors but as you should expect I couldn't produce an output.
private void combineValues(Vector<Vector> values) {
Vector currValue;
Vector nextValue;
Vector currV;
Vector nextV;
Vector currPair;
Vector nextPair;
Iterator cvaItr, nvaItr, cvItr, nvItr;
if (values.size()>1)
{
for (int i=0; i<values.size()-1; i++)
{
currValue = values.elementAt(i);
nextValue = values.elementAt(i+1);
cvaItr = currValue.iterator();
nvaItr = nextValue.iterator();
while (cvaItr.hasNext())
{
currV = (Vector) cvaItr.next();
nextV = (Vector) nvaItr.next();
cvItr = currV.iterator();
while(cvItr.hasNext())
{
currPair = (Vector) cvItr.next();
nvItr = nextV.iterator();
while (nvItr.hasNext())
{
nextPair = (Vector) nvItr.next();
/* ................*/
}
}
}
}
}
}
Please foregive my long post but as you can realise I'm confused so please help me.
Thank you!!>
# 3
> Hello prometheuzz ,
>
> Thanks for your answer.
You're welcome.
> I will try to explain my problem and the incomplete
> solution I have tried.
> ...
I'm sorry, but I find your algorithm rather confusing ; ). Therefore I'm afraid I cannot comment on it (which I hoped I could). I mainly asked for it to see whether you put in some effort of your own instead of just asking for some copy-n-paste solution.
Since you did put in some effort, here's my stab at the problem:
I first created a 2d array of int's to represent a combination-array. In your names-teams-class example that'd look like this:
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]
[2, 0, 0]
[2, 0, 1]
[2, 1, 0]
[2, 1, 1]
and with that 2d array, I printed the desired output. Here's my code:
public class Main {
private static void makeItHappen(String[][] arrays) {
int[][] combMatrix = getCombMatrix(arrays);
for(int[] row : combMatrix) {
int rowIndex = 0;
int colIndex = 0;
while(colIndex < arrays.length) {
System.out.print(arrays[rowIndex++][row[colIndex++]]+" ");
}
System.out.println();
}
}
private static int[][] getCombMatrix(String[][] arrays) {
final int NUM_COMB = getNumComb(arrays);
int[][] combMatrix = new int[NUM_COMB][arrays.length];
int repetition = 1;
for(int col = arrays.length-1; col >= 0; col--) {
int max = arrays[col].length;
int value = 0;
for(int row = 0; row < NUM_COMB;) {
for(int i = 0; i < repetition; i++, row++) {
combMatrix[row][col] = value;
}
value = value+1 >= max ? 0 : value+1;
}
repetition *= max;
}
return combMatrix;
}
private static int getNumComb(String[][] arrays) {
int n = 1;
for(String[] s : arrays) n *= s.length;
return n;
}
public static void main(String[] args) {
String[][] arrays = {{"John","Tom","Nick"}, {"A","B"}, {"F","N"}};
makeItHappen(arrays);
}
}
I did not comment it, so read, and (try to) understand what it does. Post back if there's something not clear to you.
Good luck.
