What data structure should I use to store a pair of strings in Java , if my goal is to find unique pairs?

Question

I am a beginner in Java. I have some sample data of nodes:

A -> B

B -> F

C -> R

A -> B

B -> C

R -> C

I have already taken out 2 lists: [A,B,C,A,B,R] and [B,F,R,B,C,C]

However, how should I go about storing the pairs [AB, BF, CR, AB, BC, RC] so that I can find unique pairs? By unique, I mean AB is not equal to BA .

1) So Basically I would like to identify unique pairs.

2) I also want to count the number of times each unique pair has appeared.

EDITED:

3) I am also interested in finding how many different nodes each node connects to.

4) And how many different nodes connect to each node

I am struggling to decide whether I really need to write my own class or is there an easier method?

Solution 1

Hashtable (datastructure) should work for your requirement. In java, you could consider type HashMap<String,Integer>

key is the string pair, Integer is count:

something like:

{
"AB":2,
"CR":1,
"BF":1,
...

}

The complexity of finding unique pairs would be O(n)

EDIT

it seems that putting codes here helps to explain the solution:

Map<String, Integer> map = new HashMap<String,Integer>();

//you have two lists with those strings, called list1 and list2.
// list1<String> and list2<String> have same size

String key = null;
for(int i=0;i<list1.size();i++){
    key = list1.get(i) + list2.get(i);
    if(map.containsKey(key))
        map.get(key)++;
    else
        map.put(key,1);
}

//now the map has been filled, you can go through the map, 
//and check the value, if value == 1, then the key is unique.
//for those value >1, you know, which string pair is not unique, 
// and how many times it shows.

codes were not written in IDE, so there could be typoes.

Solution 2

You can create a custom class to store pairs of strings and then use a HashMap to keep track of the count

public class StringPair {
   String leftString;
   String rightString;

   //NOTE: override hashcode and equals methods
}

And then you can use HashMap for keeping tracking of the count:

Map<StringPair, Integer> pairCountMap = new HashMap<StringPair, Integer>();

if(pairCountMap.containsKey(aPairObject)) {
   pairCountMap.put(aPairObject, pairCountMap.get(aPairObject)+1);
} else {
   pairCountMap.put(aPairObject, 0);
}

Solution 3

You need a class to designate pair:

public class Pair{
 String prv;
 String next;
 //override hashcode and equals
}

If you use Set and fill it in with all pair, you'll end-up having unique pairs:

Set<Pair> pairs = new HashSet<Pair>();
..
pairs.add(new Pair(prv, next));
int uniquePairs = pairs.size();

If you use TreeSet and make Pair implement Comparable, you'll have a sorted list of pairs

Set<Pair> pairs = new TreeSet<Pair>();
..
System.out.println(pairs);

Further, you can use a combination of List and Set and apply some logic to figure out exact number of duplicates etc, can also explore removeAll and retainAll for implementing logic.

Also, Map doesn't seem to be a fit in your use case since a class can wrap required mapping and list or set will help to apply desired logic over multiple pairs.

To get counts of total number of original pairs:

Set<Pair> pairs = new HashSet<Pair>();
int count =0;
while(..) { //iterating over list of pairs
    pairs.add(new Pair(prv, next));
    count ++;
   }
int uniquePairs = pairs.size();
int totalPairs = count;

Comments

[Sotirios Delimanolis]

Encapsulate it into a Pair class and then use a set to count unique and a list to hold all. You'll need equals and hashCode implementations.

[Sotirios Delimanolis]

This assumes you can concatenate the Strings.

[Kent]

@SotiriosDelimanolis OP has already done that, right? If I understood the Q right. let me read it again.

[Dave Newton]

@Kent OP only mentioned pairs; IMO it's general enough that it shouldn't really matter since the question is about the underlying data structure, not the nature of the data. That the OP is a beginner, however, throws a spanner in the works, so I'm not sure how generalized an answer should be.

[Kent]

@SotiriosDelimanolis if there are two arrays/lists of string, as long as they have same length/size, hashtable works anyway., still O(n) for (int i=0;i<size/length;i++) String k = a[i]+b[i]

[srikanta]

How do you count how many times a pair has occurred? Using a set will only tell you how many unique pairs there are but will not provide the count of the pairs.

[harsh]

One way is while collecting pairs, I've modified my answer. Using HashMap to track count seems to be a hack (which works) but certainly not right use case of a map.

[srikanta]

I guess the OP wants to count how many times a pair occurs. For e.g A->B pair occurs 10 times, B->C occurs only 5 times etc. For this usecase, HashMap is perfect. Why is it a hack? Your solution is counting total pairs not the count of individual pair. Think of 'group by' functionality in a SQL query.

[user2394904]

Thanks a lot for your great answers. Since AB is not equal to BA, I tried to put 2 strings together and then put them into a hashset to obtain set of strings with no duplicates. Is this a feasible method for getting unique pairs??