7 Replies Latest reply: Aug 10, 2009 6:54 AM by 791266 RSS

    All possible combinations of n vectors with k elements

    843853
      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
          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
            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
              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
                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
                  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
                    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
                      I'm locking this zombie.