7 Replies Latest reply on Aug 10, 2009 11:54 AM by 791266

# 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.
• ###### 1. Re: All possible combinations of n vectors with k elements
Could you explain your algorithm? Posting some code* along with it would be nice, but your explanation is more important. Perhaps I, or someone else can spot the error.

* when posting code, please use code tags: http://forum.java.sun.com/help.jspa?sec=formatting
• ###### 2. Re: All possible combinations of n vectors with k elements
Hello prometheuzz ,

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();

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>();
}
}
}
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();

/* ................*/

}
}
}

}
}
}``````

Thank you!!
• ###### 3. Re: All possible combinations of n vectors with k elements
Hello prometheuzz ,

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.
• ###### 4. Re: All possible combinations of n vectors with k elements
Dear prometheuzz,

There is only one thing I couldn't figure out on this great piece of code!
how is it possible for a person to have thought this?!?!?!?

You are great! Respect

• ###### 5. Re: All possible combinations of n vectors with k elements
Hello prometheuzz,

I was looking for a code that is doing the same thing to what you posted here, but with a little modification. In this code if we have an input like this:
``String[][] arrays = {{"John", "Tom", "Nick"}, {"A", "B", "C"}};``
we will have this output:
``````John A
John B
John C
Tom A
Tom B
Tom C
Nick A
Nick B
Nick C``````
So I want your help to have an output like this:
``````John A
John B
John C
John AB
John AC
John BC
Tom A
Tom B
Tom C
Tom AB
Tom AC
Tom BC
Nick A
Nick B
Nick C
Nick AB
Nick AC
Nick BC``````
• ###### 6. Re: All possible combinations of n vectors with k elements
GabrielGSXR wrote:
Hello prometheuzz,

I was looking for a code that is doing the same thing to what you posted here, but with a little modification. In this code if we have an input like this:
``String[][] arrays = {{"John", "Tom", "Nick"}, {"A", "B", "C"}};``
we will have this output:
``````John A
John B
John C
Tom A
Tom B
Tom C
Nick A
Nick B
Nick C``````
So I want your help to have an output like this:
``````John A
John B
John C
John AB
John AC
John BC
Tom A
Tom B
Tom C
Tom AB
Tom AC
Tom BC
Nick A
Nick B
Nick C
Nick AB
Nick AC
Nick BC``````