Iterate two distinct elements in set?

Question

I want to get the pair of every two distinct element in set. I think that if using for-each loop I have to iterate with complexity of O(n^2). If using iterator, I can have two iterators where the second one points to the next of the first one, which means for the second loop I don't have to loop from the start. However, I can't seem to print my method correctly.

public static void main(String[] args){
    Set<String> s = new HashSet<String>();
    s.add("A");
    s.add("B");
    s.add("C");
    s.add("D");
    Iterator<String> itr1 = s.iterator();
    while (itr1.hasNext()){
        Iterator<String> itr2 = itr1;
        String s1 = itr1.next();
        while (itr2.hasNext()){
            String s2 = itr2.next();
            System.out.println(s1 + " " + s2);
        }
    }
}

The output is

A B
A C
A D

However what I want is:

A B
A C
A D
B C
B D
C D

Answer 1

I don't think that

Iterator<String> itr2 = itr1;

does what you think it does. It means that itr2 is literally the same object as itr1. It is not a deep or stateful copy.

This would be easier if you were working with a list, since we could rely on indices for order. In order to use Iterator and Set, you'll need to maintain a collection of objects that you've already used:

Iterator<String> itr1 = s.iterator();
Set<String> used = new HashSet<>(); // track the elements that have been used in the first column
while (itr1.hasNext()) {
    Iterator<String> itr2 = s.iterator(); // a new iterator
    String s1 = itr1.next();
    used.add(s1); // track what we've used
    while (itr2.hasNext()) {
        String s2 = itr2.next();
        if (used.contains(s2));
            continue; // we've alread used s2
        System.out.println(s1 + " " + s2);
    }
}

Theoretically, it would be better to use an array (or list) and for loop to do what you want to do:

String[] elements = s.toArray(new String[s.size()]);
for (int i = 0; i < elements.length; ++i) {
    String s1 = elements[i];
    // loop through all successive elements
    for (int j = i + 1; j < elements.length; ++j) {
        String s2 = elements[j];
        System.out.println(s1 + " " + s2);
    }
}

Answer 2

You're general logic is right, your problem is that the line

Iterator<String> itr2 = itr1;

does not copy the iterator and instead you are using the same iterator object for both loops.

I think this honestly might be a case where using a simple for loop with an index variable is a lot easier than using loops iterators.

However since you cannot iterate over a set using an index variable i would recommend either using a simple List, or at least converting the Set to a List for this specific function:

public static void main(String[] args) {
    List<String> s = new ArrayList<String>();
    s.add("A");
    s.add("B");
    s.add("C");
    s.add("D");

    for (int i = 0; i < s.size(); i++) {
        String s1 = s.get(i);
        for (int x = i+1; x < s.size(); x++) {
            String s2 = s.get(x);
            System.out.println(s1 + " " + s2);
        }
    }
}