This discussion is archived
7 Replies Latest reply: Aug 10, 2009 4:54 AM by 791266 RSS

All possible combinations of n vectors with k elements

843853 Newbie
Currently Being Moderated
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
    800282 Newbie
    Currently Being Moderated
    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
    843853 Newbie
    Currently Being Moderated
    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. Re: All possible combinations of n vectors with k elements
    800282 Newbie
    Currently Being Moderated
    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.
  • 4. Re: All possible combinations of n vectors with k elements
    843853 Newbie
    Currently Being Moderated
    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

    Many thanks for your help!
  • 5. Re: All possible combinations of n vectors with k elements
    843853 Newbie
    Currently Being Moderated
    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
    Thanks for your time.
  • 6. Re: All possible combinations of n vectors with k elements
    800282 Newbie
    Currently Being Moderated
    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
    Thanks for your time.
    [http://forums.sun.com/thread.jspa?threadID=5401707]
  • 7. Re: All possible combinations of n vectors with k elements
    791266 Explorer
    Currently Being Moderated
    I'm locking this zombie.