Сортировка наборов в алфавитном порядке, буквы в наборах, разделенные запятыми

public static void main(String[] args) throws IOException
{

    HashSet set = new HashSet<String>();

    set.add("{}");
    set.add("{a}");
    set.add("{b}");
    set.add("{a, b}");
    set.add("{a, c}");

    sortedSet(set);
}

public static void sortedSet(HashSet set)
{
    List<String> setList = new ArrayList<String>(set);
    List<String> orderedByAlpha = new ArrayList<String>(set);

    //sort by alphabetical order
    orderedByAlpha = (List<String>) setList.stream()
        .sorted((s1, s2) -> s1.compareToIgnoreCase(s2))
        .collect(Collectors.toList());
    System.out.println(orderedByAlpha);
}

Я пытаюсь сортировать в алфавитном порядке, но вывод, который я получаю, таков:

[{a, b}, {a, c}, {a}, {b}, {}]

но это должно быть:

[{a}, {a, b}, {a, c}, {b}, {}]

Всего 4 ответа


Ну, как уже отмечали @Aomine и @Holger, вам нужен пользовательский компаратор.

Но ИМХО их решения выглядят чрезмерно. Вам не нужны никакие дорогостоящие операции, такие как split и substring :

  • String.substring создает новый объект String и вызывает System.arraycopy() под капотом
  • String.split еще более дорогостоящий. Он выполняет String.substring по вашей строке и вызывает String.substring несколько раз. Кроме того, он создает ArrayList для хранения всех подстрок. Если количество подстрок достаточно велико, то ваш ArrayList должен будет увеличить свою емкость (возможно, не только один раз), вызвав другой вызов System.arraycopy() .

Для вашего простого случая я бы немного String.compareTo код встроенного метода String.compareTo :

Comparator<String> customComparator =
            (s1, s2) -> {
                int len1 = s1.length();
                int len2 = s2.length();

                if (len1 == 2) return 1;
                if (len2 == 2) return -1;

                int lim = Math.min(len1, len2) - 1;

                for (int k = 1; k < lim; k++) {
                    char c1 = s1.charAt(k);
                    char c2 = s2.charAt(k);
                    if (c1 != c2) {
                        return c1 - c2;
                    }
                }
                return len1 - len2;
            };

Он будет сравнивать строки со сложностью O(n) , где n - длина более короткой строки. В то же время он не будет создавать никаких новых объектов и не выполнять репликацию массива.

Тот же компаратор может быть реализован с использованием Stream API :

Comparator<String> customComparatorUsingStreams =
            (s1, s2) -> {
                if (s1.length() == 2) return 1;
                if (s2.length() == 2) return -1;
                return IntStream.range(1, Math.min(s1.length(), s2.length()) - 1)
                        .map(i -> s1.charAt(i) - s2.charAt(i))
                        .filter(i -> i != 0)
                        .findFirst()
                        .orElse(0);
            };

Вы можете использовать свой собственный компаратор следующим образом:

List<String> orderedByAlpha = setList.stream()
                                     .sorted(customComparatorUsingStreams)
                                     .collect(Collectors.toList());
System.out.println(orderedByAlpha);

Вы вывод не соответствует вашему коду. Вы показываете списки 2D-массивов, но ваше преобразование в 1D arraylist не имеет смысла.

public static void main(String[] args)
{
    test(Arrays.asList("a", "d", "f", "a", "b"));
}

static void test(List<String> setList)
{
    List<String> out = setList.stream().sorted((a, b) -> a.compareToIgnoreCase(b)).collect(Collectors.toList());
    System.out.println(out);
}

Это правильно сортирует 1D массивы, поэтому вы там верны.

Вам, вероятно, потребуется реализовать собственный компаратор для сравнения списков 2D-массивов для их сортировки.


вместо того, чтобы иметь источник как List<String> я бы порекомендовал вам его как List<Set<String>> eg

List<Set<String>> setList = new ArrayList<>();
setList.add(new HashSet<>(Arrays.asList("a","b")));
setList.add(new HashSet<>(Arrays.asList("a","c")));
setList.add(new HashSet<>(Collections.singletonList("a")));
setList.add(new HashSet<>(Collections.singletonList("b")));
setList.add(new HashSet<>());

Затем примените следующий компаратор вместе с операцией отображения, чтобы получить ожидаемый результат:

List<String> result = 
     setList.stream()
         .sorted(Comparator.comparing((Function<Set<String>, Boolean>) Set::isEmpty)
                        .thenComparing(s -> String.join("", s),
                        String.CASE_INSENSITIVE_ORDER))
         .map(Object::toString)
         .collect(Collectors.toList());

и это печатает:

[[a], [a, b], [a, c], [b], []]

обратите внимание, что в настоящее время результатом является список строк, где каждая строка представляет собой строковое представление заданного набора. если, однако, вы хотите, чтобы результат был List<Set<String>> затем просто удалил операцию map выше.

Редактировать:

Удалось найти решение, основанное на вашей первоначальной идее ....

Итак, во-первых, вам нужен совершенно новый компаратор вместо просто (s1, s2) -> s1.compareToIgnoreCase(s2) поскольку этого будет недостаточно.

Учитывая ввод:

Set<String> set =  new HashSet<>();

set.add("{}");
set.add("{a}");
set.add("{b}");
set.add("{a, b}");
set.add("{a, c}");

и следующий поток:

List<String> result = set.stream()
            .map(s -> s.replaceAll("[^A-Za-z]+", ""))
            .sorted(Comparator.comparing(String::isEmpty)
                    .thenComparing(String.CASE_INSENSITIVE_ORDER))
            .map(s -> Arrays.stream(s.split(""))
                            .collect(Collectors.joining(", ", "{", "}")))
            .collect(Collectors.toList());

Тогда мы получим результат:

[{a}, {a, b}, {a, c}, {b}, {}]

Возьмите его (слегка похожий на ответ Аомина ), чтобы разбить строки символов, которые заставляют String#compareTo() терпеть неудачу, в этом случае ( '{' и '}' ). Кроме того, особый случай, когда пустую строку ( "{}" ) следует сортировать после того, как остальное нужно позаботиться.

Следующий код реализует такой компаратор:

static final Comparator<String> COMPARE_IGNORING_CURLY_BRACES_WITH_EMPTY_LAST = (s1, s2) -> {
  Function<String, String> strip = string -> string.replaceAll("[{}]", "");
  String strippedS1 = strip.apply(s1);
  String strippedS2 = strip.apply(s2);
  return strippedS1.isEmpty() || strippedS2.isEmpty() ?
      strippedS2.length() - strippedS1.length() :
      strippedS1.compareTo(strippedS2);
};

Конечно, это не самое эффективное решение. Если эффективность здесь действительно важна, я бы перебирал символы, например String#compareTo() , как это было предложено ETO .


Есть идеи?

10000