Choose elements with lowest cardinality from Java List structure

Question

A simple question, but having trouble finding the answer on google. Since normally I work with SQL, I'm used to having access to set based operations like this:

select Q, qCount
from (
  select Q, qCount, min(qCount) over () as minQCount
  from (
    select Q, count(*) as qCount
    from table_A
    group by Q
  ) 
)
where qCount = minQCount

This finds all the values of Q from the table that have the lowest cardinality amongst the set of distinct Q values.

Is there an established efficient way of doing that for a Java List? Say:

List<Q> listOfQ //gets populated with different objects of Q
//objects of Q can represent the same value through an overridden equals()
//get each object from Q for which the cardinality of the value it represents 
//is the lowest amongst the distinct values in the list

a simple example being:

List<Integer> list = new ArrayList<Integer>(); 
list.addAll(Arrays.asList(new Integer[] {1,1,1,2,2,3,3,3,4,4,4,4,5,5}));
//want to retrieve {2,2,5,5}
//would also be nice to easily retrieve a map with {k:2 v:2, k:5 v:2} 
//this being the equivalent of the SQL query above

Thanks!

"Cardinality" is a fancy word for Java. Google "count occurrences" or "frequency" and you'll have more luck. Relevant SO question: http://stackoverflow.com/questions/14260134/elegant-way-of-counting-occurrences-in-a-java-collection — Andrew Janke, Apr 30 '15 at 20:09

score 3 · Answer 1 · edited Apr 30 '15 at 20:00

3

Consider using GUAVA's Multiset.

On it you can get the number with count(key) method

edited Apr 30 '15 at 20:00

Martin Serrano

3,727
1
35
48

answered Apr 30 '15 at 19:40

user3666833

39
2

score 1 · Answer 2 · answered Apr 30 '15 at 20:22

private static <K> Map<K, Integer> getElementsWithLessCardinality(
        List<K> list) {
    Map<K, Integer> map = new TreeMap<K, Integer>(); //or HashMap
    Map<K, Integer> res = new TreeMap<K, Integer>();
    Integer min = null;
    for (K listElem : list) {
        if (map.containsKey(listElem)) {
            map.put(listElem, map.get(listElem) + 1);
        } else {
            map.put(listElem, 1);
        }
    }

    for (Entry<K, Integer> pair : map.entrySet()) {
        K key = pair.getKey();
        Integer value = pair.getValue();
        if (min == null) {
            // Initial state
            min = value;
            res.put(key, value);
        } else if (min.equals(pair.getValue())) {
            res.put(key, value);
        } else if (value.compareTo(min) == -1) {
            res.clear();
            min = value;
            res.put(key, value);
        }
    }

    return res;
}

I think you could do something like this:

-First you get a map complete.

-Then you find the ones with less cardinality and put it in another map.

Note that this solution use a parametric type, so you can use it when you need to count objects of any type. (But make sure compareTo(), equals() and hashCode() are well implemented in class K)

score 1 · Accepted Answer · answered Apr 30 '15 at 20:32

Using apache commons collections:

  final List<Integer> list = Arrays.asList(new Integer[]{1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5});
  final Map<Integer, Integer> cardinalityMap = CollectionUtils.getCardinalityMap(list);
  final int minCardinality = Collections.min(cardinalityMap.values());
  System.out.println("min cardinality: " + minCardinality);
  for (final Map.Entry<Integer, Integer> entry: cardinalityMap.entrySet()) {
    if (minCardinality == entry.getValue()) {
      System.out.println("key: " + entry.getKey());
    }
  }

Console output:

min cardinality: 2
key: 2
key: 5

That's a lot of final, yikes – Steve Kuo Apr 30 '15 at 20:34 — Steve Kuo, Apr 30 '15 at 20:34

Alaa Abuzaghleh · Answer 4 · 2015-05-01T21:05:06.197

-1

Hashtable<String, Integer> ht = new Hashtable<String, Integer>() ; 
for(Integer i : list){
    if(ht.contain(i+""){
          Integer v = ht.get(i+"") + 1 ; 
    }else{
         ht.put(i+"" , 1) ; 
    }
}

// now we need order it 
TreeMap<String, Integer> tm= new TreeMap<Integer, String>(ht);

now the tree map will be sorted key and value

edited May 01 '15 at 21:05

answered Apr 30 '15 at 19:39

Alaa Abuzaghleh

1,023
6
11

Couple issues with this implementation: No need to convert the keys to `String`; just leave them as `Object` or a generic parametrized type. New code should avoid `Hashtable` in favor of `HashMap`. And `new TreeMap(Hashtable)` is bound to fail due to both type mismatch and possible key collisions. – Andrew Janke Apr 30 '15 at 20:18
first of all I am trying to show idea how to solve this issue, not trying to make complete code running, otherthing String is best choice for you key in hash since it is provide excellent hash code, and equal implementation. and yes the TreeMap has to be – Alaa Abuzaghleh May 01 '15 at 21:04

Choose elements with lowest cardinality from Java List structure

4 Answers4