Заказать строки по внешнему виду в Java

Question

У меня есть список строк, которые уже упорядочены по числовому значению.Теперь я хотел бы сгруппировать эти строки следующим образом.

Допустим, у меня есть текстовый файл, который выглядит следующим образом:DBCЕ.Б.CDЭДДACBEBCDACEDBCDAИ я хотел бы заказать его таким образом, чтобы в итоге получилось так:DBCDACЕ.Б.EBCЭДДEDBCDCDAACBТак что, как вы можете видеть, он должен группироваться по букве строки и объединять их вместе.Каков наиболее эффективный способ решения этой задачи?

ОБНОВЛЕНИЕ.Как видите, желаемый порядок не в алфавитном порядке, в том числе в обратном порядке.Как я уже говорил, цель состоит в том, чтобы сгруппировать строки и упорядочить их по первому появлению.В этом примере я использую письмо, чтобы упростить (намного) более сложную проблему, которую пытаюсь решить.Здесь нужно сконцентрироваться на порядке, в котором появляются буквы каждой строки.Группировка в определенном порядке, а не в заказе.

Answer 1

Вам нужно дерево префиксов (trie).Это дерево, где каждый уровень соответствует позиции в строке (корень = 0, уровень 1 = первая буква и т. Д.), А каждый узел соответствует букве.Узел также содержит логическое значение (скажем, isWord), указывающее, заканчивается ли здесь слово или нет, и в вашем случае вам нужен еще один int, скажем, index, чтобы указать индекс слова в вашем начальном порядке (в случае, еслиisWord == true).

Вы также можете использовать Набор, который изначально содержит все слова.

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

1. Найдите его в дереве, добавьте его в новый список, отметьте его как занятый.
2. Возьмите все слова в его поддереве, которые не взяты (то есть всеначинаются с того же префикса), упорядочите их по индексу и пометьте как добавленные, добавьте их в новый список.
3. Перейдите на один уровень выше к родительскому узлу текущего узла и делайте то же самое, пока не достигнете корня.

Надеюсь, это поможет.

Answer 2

ОК, это выглядит сложно.Если я правильно понимаю, вам нужно двухэтапное решение:

1. Вам необходимо сопоставить несколько строк с общим префиксом

   public static String mapKey(String value){
       // or whatever your mapping to a common key would be
       return value.substring(0, 2);
   }
   

2. Вам нужно отсортировать по этому префиксу в порядке появления

   Я бы предложил вам использовать Гуава Multimap, в частности, LinkedHashMultimap:

   Multimap<String, String> map = LinkedHashMultimap.create();
   // write data to map
   for(String word: yourData){
       map.put(mapKey(word), word);
   }
   // read items from map, grouped by prefix
   for (String value : map.values()) {
       System.out.println(value);
   }
   

   Объяснение: LinkedHashMultimap перебирает свои записи в порядке их ключей.Поскольку у вас есть несколько записей с общими ключами (как определено mapKey), они будут возвращены в виде группы.

На самом деле, при повторном чтении ваших требований, LinkedHashMultimap won 'Тоже вполне подходит (потому что предметы отдельных групп будут появляться в случайном порядке).Вам понадобится пользовательский Multimap:

Multimap<String,String> map = Multimaps.newListMultimap(
        new LinkedHashMap<String, Collection<String>>(),
        (Supplier<? extends List<String>>) new Supplier<List<String>>() {
    public List<String> get() {
        return new ArrayList<String>();
    }
});

(остальная часть кода остается без изменений)

Answer 3

public static List<String> crazySort(List<String> list) {
  LinkedHashMap<Character, List<String>> map = 
    new LinkedHashMap<Character, List<String>>();
  for (String s : list) {
    List<String> group = map.get(s.charAt(0));
    if (group == null)
      map.put(s.charAt(0), new ArrayList<String>());
    group.add(s);
  }
  List<String> sorted = new ArrayList<String>(list.size());
  for (List<String> group : map.values()) {
    sorted.addAll(group);
  }
  return sorted;
}

Answer 4

A trie , который поддерживает порядок вставки, например, с помощью LinkedHashMap, делает трюк.

Я взломал простой трюк, подобный этому:

import org.junit.Test;

import java.util.*;

import static java.util.Arrays.asList;
import static org.junit.Assert.assertEquals;

public class LinkedTrieTest {

    @Test
    public void testLinkedTrie() {

        List<String> input = asList(
                "dbc",
                "eb",
                "cd",
                "edd",
                "acb",
                "ebc",
                "dac",
                "edb",
                "cda"
        );

        List<String> expected = asList(
                "dbc",
                "dac",
                "eb",
                "ebc",
                "edd",
                "edb",
                "cd",
                "cda",
                "acb"
        );

        assertEquals(expected, iterableToList(new LinkedTrie(input)));
    }

    private List<String> iterableToList(Iterable<String> t) {
        List<String> result = new ArrayList<String>();
        for (String s : t) {
            result.add(s);
        }
        return result;
    }

    private class LinkedTrie implements Iterable<String> {

        private Node root = new Node();

        private LinkedTrie() {
        }

        private LinkedTrie(Iterable<String> strings) {
            addAll(strings);
        }

        private void addAll(Iterable<String> strings) {
            for (String string : strings) {
                add(string);
            }
        }

        public void add(String s) {
            root.add(s);
        }

        @Override
        public Iterator<String> iterator() {
            return root.iterator();
        }

        private class Node {
            private Map<Character, Node> nodes = new LinkedHashMap<Character, Node>();

            private void add(String s) {
                if (s.isEmpty()) {
                    nodes.put(null,null);
                    return;
                }
                Character c = s.charAt(0);
                Node node = nodes.get(c);
                if (null == node) {
                    node = new Node();
                }
                nodes.put(c, node);
                node.add(s.substring(1));
            }

            private Iterator<String> iterator() {
                return new TrieIterator();
            }

            private class TrieIterator implements Iterator<String> {

                private Iterator<Map.Entry<Character,Node>> prefixesWithSuffixes = nodes.entrySet().iterator();
                private Character currentPrefix;
                private Iterator<String> suffixesForCurrentPrefix = Collections.<String>emptyList().iterator();

                @Override
                public boolean hasNext() {
                    return suffixesForCurrentPrefix.hasNext() || prefixesWithSuffixes.hasNext();
                }

                @Override
                public String next() {
                    if (outOfSuffixesForCurrentPrefix()) {
                        if (outOfPrefixes()) {
                            throw new NoSuchElementException();
                        }
                        Map.Entry<Character, Node> prefixWithSuffixes = prefixesWithSuffixes.next();
                        currentPrefix = prefixWithSuffixes.getKey();
                        if (null == currentPrefix) {
                            return "";
                        }
                        suffixesForCurrentPrefix = prefixWithSuffixes.getValue().iterator();
                    }
                    return currentPrefix + suffixesForCurrentPrefix.next();
                }

                private boolean outOfPrefixes() {
                    return !prefixesWithSuffixes.hasNext();
                }

                private boolean outOfSuffixesForCurrentPrefix() {
                    return !suffixesForCurrentPrefix.hasNext();
                }

                @Override
                public void remove() {
                    throw new UnsupportedOperationException();
                }
            }
        }
    }
}