8

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?

user2394904
  • 71
  • 2
  • 2
  • 7
  • 2
    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 May 17 '13 at 20:53
  • Here is a useful resource for implementing your own pair class: http://stackoverflow.com/questions/521171/a-java-collection-of-value-pairs-tuples – Kevin Somers-Higgins May 17 '13 at 21:08
  • `I also want to count the number of times each unique pair has appeared.` what does it mean? if a pair is unique, it appears only once right? – Kent May 17 '13 at 21:15
  • This means: if we have 2 pairs (A,B) and (B,A). They are 2 different pairs. However, if we have (A,B) and (A,B), then they are considered as one unique pair. – user2394904 May 17 '13 at 23:30

3 Answers3

10

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);
}
srikanta
  • 2,914
  • 3
  • 21
  • 35
2

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.

Kent
  • 189,393
  • 32
  • 233
  • 301
  • This assumes you can concatenate the Strings. – Sotirios Delimanolis May 17 '13 at 21:06
  • @SotiriosDelimanolis OP has already done that, right? If I understood the Q right. let me read it again. – Kent May 17 '13 at 21:09
  • @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. – Dave Newton May 17 '13 at 21:11
  • @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 – Kent May 17 '13 at 21:12
  • 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?? – user2394904 May 17 '13 at 23:15
1

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;
harsh
  • 7,502
  • 3
  • 31
  • 32
  • 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. – srikanta May 17 '13 at 21:17
  • 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. – harsh May 17 '13 at 21:23
  • 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. – srikanta May 17 '13 at 21:26