Generating possible unordered pairs of combinations from a Hashset

Question

I realise that this question may have been asked many times before, but for this particular application using loops won't really work because I can't index into a set

What I'm looking to do is getting a set of possible unordered pairs from data in a hashset as efficiently as possible.

So if my hashset contained A, B, C, D , E Then the following combinations are possbile: AB, AC, AD, AE, BC, BD, BE, CD, CE, DE

What options do I have available to achieve this efficiently?

Any ideas would be greatly appreciated

score 1 · Answer 1 · answered Oct 16 '14 at 02:29

As far as the efficiency goes, there aren't too many options out there: you need to produce a set of N² items, meaning that the timing would also be at least of the same order.

Since enumerating a set is linear, two nested loops will deal with this as efficiently as any other method would.

The loop on the outside should iterate the collection from the beginning. The loop on the inside should start at the position of the outer loop's iterator, incremented by one position.

Pham Trung · Accepted Answer · 2014-10-16T02:44:38.563

0

You can still index your data, just add an additional HashMap<Your_Class, Integer> map to store the index of a particular data.

 HashSet<Your_Class> set = ...//HashSet that contains data
 int index = 0;
 HashMap<Your_Class,Integer> map = new HashMap<>();
 for(Your_Class item : set){
     map.put(item, index++);
 }
 //Generate all the set with those indexes, and replace them with map.get(index)

So, in the example case, A has index 0, B has index 1,...., So for each pair 01, 02, 03..., just need to convert it back into AB, AC ,...

edited Oct 16 '14 at 02:44

answered Oct 16 '14 at 02:30

Pham Trung

11,204
2
24
43

actually sorry I just really it's a set of data not a hashset - does that change things? – user3601148 Oct 16 '14 at 02:47
@user3601148 It will not change anything , but you need to provide `equals` and `hashCode` method for `Your_Class` to make sure each data being index is unique (which means if you have 2 instances `A` in your data, it will only has one index, not two). You can take a look [here](http://stackoverflow.com/questions/17027777/relationship-between-hashcode-and-equals-method-in-java) – Pham Trung Oct 16 '14 at 02:57
would converting a set to an array be a better option in the case? – user3601148 Oct 16 '14 at 03:07
@user3601148 not quite get you :), but if you want to use an array in order to indexing your data, when you need its index, you need to have a for loop to look for a particular data, so the time complexity can be a little bit worse – Pham Trung Oct 16 '14 at 03:16

score 0 · Answer 3 · edited Jan 05 '16 at 18:36

There aren't too may options. You can arrange your objects in an imutable object Class with the two objects like this:

public T Class Arrangement<T>{
      private final T object1;
      private final T object2;

      public Arrangement(T object1, T)

      // get methods... 
}

Set<MyType> mySet = new HashSet<MyType>();

mySet.add(new Arrangement(myObject1, myObject2);

Something like this!

Generating possible unordered pairs of combinations from a Hashset

3 Answers3