Gaurang Singhal Gaurang Singhal -4 years ago 45
Java Question

Sorting an ArrayList of ArrayLists of Integers in which inner Lists are of varying lengths

Ques: Given a set of distinct integers, S, return all possible subsets. Elements in a subset must be in non-descending order. Also, the subsets should be sorted in ascending ( lexicographic ) order.

My Approach: I sorted the input first. Then found all the subsets and appended the new subsets found in each step to the "res". Now I tried sorting the "res" arraylist using custom comparator. But the output is coming wrong.

For the input arraylist

a={ 15, 12, 4 }


Output :
res={ {}, {4}, {4,12}, {4,15}, {4,12,15}, {12}, {12,15}, {15} }


Expected Output:
res={ {}, {4}, {4,12}, {4,,12,15}, {4,15}, {12}, {12,15}, {15} }


public static ArrayList<ArrayList<Integer>> subsets(ArrayList<Integer> a)
{ int i,j;
ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> temp;
res.add(new ArrayList<Integer>());
Collections.sort(a);
for(i=0;i<a.size();i++)
{ ArrayList<ArrayList<Integer>> str=new ArrayList<ArrayList<Integer>>();
for(ArrayList<Integer> al:res)
{ temp=new ArrayList<Integer>();
temp.addAll(al);
temp.add(a.get(i));
str.add(temp);
}
res.addAll(str);

}
Collections.sort(res,new Comparator<ArrayList<Integer>>()
{ public int compare(ArrayList<Integer> p,ArrayList<Integer> q)
{ if(q.size()==0)
return 1;
else
return Integer.compare(p.get(0),q.get(0));
}
});
return res;
}


To sort the inner lists with respect to each other I wrote this Comparator. But the Comparator is giving wrong answer. I suppose my Comparator is wrongly written.

Answer Source

You shouldn't just compare the first elements of the lists. What happens when you compare two lists with the same first element, but an arbitrary number of different elements after it?

To alleviate the issue, you'll have to compare each element until a difference is reached. I would suggest the following:

int oneSize = listOne.size();
int twoSize = listTwo.size();

for(int i = 0; i < oneSize; i++)
{
    if(i == oneSize || i == twoSize)
        return oneSize - twoSize;

    int elementOne = listOne.get(i);
    int elementTwo = listTwo.get(i);
    if(elementOne == elementTwo)
       continue;

    return Integer.compare(elementOne, elementTwo);
}
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download