How to sort a list into a custom order forming kind of distinct groups

Question

I have a list of unsorted strings, where entries are one of {A,B,C,D}:

List<String> strings = new ArrayList<>(Arrays.asList("A","C","B","D","D","A","B","C","A","D","B","D","A","C"));

I need to sort / (group) them in a custom order taking one item at time to have a result like:

[A, B, C, D, A, B, C, D, A, B, C, D, A, D]

I am struggling to come up with an idea how to do so. Any help?

I have tried to use a custom Comparator<String> but not able to implement the logic that first A < second A and first D < second A.

Also tried Stream. groupingBy:

Collection<List<String>> coll = strings.stream().collect(Collectors.groupingBy(s -> s)).values();

which groups same strings into groups.

[[A, A, A, A], [B, B, B], [C, C, C], [D, D, D, D]]

But I am not sure how to take one element at a time from above lists till no elements are available. Does anyone have any approach on how to proceed here? Need a hint in the right direction.

Answer 1

Building a whole new list could lead to some other solutions, for example:

Map<String, Long> counts = strings.stream().collect(groupingBy(identity(), TreeMap::new, counting()));
List<String> ordered = new ArrayList<>();
while (!counts.isEmpty()) {
    for (Iterator<Map.Entry<String, Long>> it = counts.entrySet().iterator(); it.hasNext(); ) {
        Map.Entry<String, Long> entry = it.next();
        ordered.add(entry.getKey());
        long newCount = entry.getValue() - 1;
        if (newCount == 0) {
            it.remove();
        } else {
            entry.setValue(newCount);
        }
    }
}

With strings being the input list and ordered the output.

Answer 2

Not as elegant but more clear as to what is going on. You can place an integer before each string indicating the amount of times that string value has been encountered. Then just sort normally and use a regex to replace the integer values.

public static void main(String[] args) {
    List<String> strings = new ArrayList<>(Arrays.asList("A","C","B","D","D","A","B","C","A","D","B","D","A","C"));
    List<String> sortableString = stringTransform(strings);
    sortableString.stream().sorted().forEach(s -> System.err.print(s.replaceAll("[0-9]", "")));
}


private static List<String> stringTransform(List<String> stringList) {
    Map<String, Integer> stringMap = new HashMap<>();
    List<String> result = new ArrayList<>();
    for (String string : stringList) {
        Integer integer = stringMap.get(string);
        if (integer == null) {
            integer = 0;
        } else {
            integer++;
        }
        stringMap.put(string, integer);
        result.add(integer + string);
    }
    return result;
}

Answer 3

Add a number prefix to each value, sort and remove the prefix, with limitation the array size cannot be far bigger than the number prefix

List<String> strings = new ArrayList<>(Arrays.asList("A","C","B","D","D","A","B","C","A","D","B","D","A","C"));
Map<String, Integer> m = new HashMap<>();
strings.stream()
    .map(i -> String.format("%dx%s", (100000 + m.merge(i, 1, (n, w) -> n+w)), i))
    .sorted()
    .map(i -> i.replaceFirst("^\\d+x", ""))
    .collect(Collectors.toList());

Answer 4

This is roughly the same logic as sp00m's answer, but implemented with two streams:

Map<String, Long> groups = strings.stream()
    .collect(Collectors.groupingBy(Function.identity(), 
            TreeMap::new, 
            Collectors.counting()));

List<String> result = IntStream.range(0, groups.values().stream()
                          .mapToInt(Long::intValue).max().orElseThrow())
    .mapToObj(c -> groups.keySet().stream().filter(k -> groups.get(k) > c))
    .flatMap(Function.identity())
    .collect(Collectors.toList());

The sorting is taken care of by TreeMap. Just be sure that your actual list elements are comparable (or that you give the right TreeMap supplier)

Answer 5

Well, here is another approach.

First, we could get a list of a list with all items, as you describe in your question.

[
    [A, A, A, A],
    [B, B, B],
    [C, C, C],
    [D, D, D, D]
]

Collection<List<String>> chunks = strs.stream()
    .collect(Collectors.groupingBy(Function.identity(), TreeMap::new, Collectors.toList()))
    .values();

You could insert a custom Comparator by replacing TreeMap::new by () -> new TreeMap<>(comparator).

Then we could just use this to get all ABCD groups.

IntStream.iterate(0, i -> i + 1)
    .mapToObj(i -> chunks.stream()
        .map(sublist -> i < sublist.size() ? sublist.get(i) : null)
        .filter(Objects::nonNull)
        .toList())
    .takeWhile(list -> !list.isEmpty())
    .forEach(System.out::println);

What happens here, is that we loop over each sublist and take the 1st element, then the take each 2nd element, et cetera.

---

This'll become better readable if you put the code to get a certain index of a bunch of lists into a separate method:

public static <T> Stream<T> nthElement(Collection<? extends List<T>> list, int index) {
    return list.stream()
        .map(sublist -> index < sublist.size() ? sublist.get(index) : null)
        .filter(Objects::nonNull);
}

IntStream.iterate(0, i -> i + 1)
    .mapToObj(i -> nthElement(chunks, i).toList())
    .takeWhile(list -> !list.isEmpty())
    .forEach(System.out::println);