How do I rewrite this in a cleaner way?

Hello, I have a large set of strings and I need to find all combinations
of two of those string and perform an algorithm on them (the algorithm
is actually an XQuery that runs over a large dataset so I won't post
that here). The combinations foo-bar and bar-foo are considered to be
equal so only one should be generated.

I wrote a static class method that takes an array of Strings and returns
all combinations in a Vector. The Vector stores a class Pair which I've
written myself too. The complete code is posted below with output from a
sample run. It seems to work, but how can it be improved and get rid of
the Pair class? Thanks!

package utility;

import java.util.HashSet;
import java.util.Set;
import java.util.Vector;

public class MiscUtils {

    public static void main(String[] args) {
       Vector<Pair> combos = findCombinations(new String[]{"chebi",
"kegg.compound"});
       System.out.println(combos.size());
       System.out.println(combos);
    }

    public static Vector<Pair> findCombinations(String[] strings) {
       Vector<Pair> combinations = new Vector<Pair>();
       Set<String> alreadyPaired = new HashSet<String>();

       for (int i = 0; i < strings.length; ++i) {
          for (int j = 0; j < strings.length; ++j) {
             if (i != j && !alreadyPaired.contains(strings[j])) {
                combinations.add(new Pair(strings[i], strings[j]));
             }
          }

          alreadyPaired.add(strings[i]);
       }

       return combinations;
    }
}

class Pair {
    public Pair(String s1, String s2) {
       this.s1 = s1;
       this.s2 = s2;
    }

    public String getFirst() {
       return s1;
    }

    public String getSecond() {
       return s2;
    }

    public String toString() {
       return s1 + ":" + s2;
    }

    private String s1 = null;
    private String s2 = null;
}

Sample run:
1
[chebi:kegg.compound]

- Fencer