Лучший способ уменьшить последовательности в массиве строк

Question

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

Этот вопрос касается удаления последовательностей из массива, а не дубликатов в строгом смысле.

Рассмотрим эту последовательность элементов в массиве;

[0] a
[1] a
[2] b
[3] c
[4] c
[5] a
[6] c
[7] d
[8] c
[9] d

В этом примере я хочу получить следующее ...

[0] a
[1] b
[2] c
[3] a
[4] c
[5] d

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

Кроме того, обратите внимание, что при повторении двух строк их следует сократить до одного набора (из двух строк).

[0] c
[1] d
[2] c
[3] d

... уменьшается до ...

[0] c
[1] d

Я пишу на C #, но алгоритмы на любом языке приветствуются.

Answer 1

РЕДАКТИРОВАТЬ: внесены некоторые изменения и новые предложения

Как насчет раздвижного окна ...

REMOVE LENGTH 2: (no other length has other matches)
//the lower case letters are the matches
ABCBAbabaBBCbcbcbVbvBCbcbcAB  
__ABCBABABABBCBCBCBVBVBCBCBCAB

REMOVE LENGTH 1 (duplicate characters):
//* denote that a string was removed to prevent continual contraction
//of the string, unless this is what you want.
ABCBA*BbC*V*BC*AB
_ABCBA*BBC*V*BC*AB

RESULT:
ABCBA*B*C*V*BC*AB == ABCBABCVBCAB

Это, конечно, начинается с длины = 2, увеличивается до L / 2 и итерация вниз.

Я также думаю о двух других подходах:

1. digraph - Установите в режиме орграфа с данными данные и переберите его со строкой, если цикл найден, у вас будет дублирование. Я не уверен, насколько легко проверить проверку для этих циклов ... возможно, какое-то динамическое программирование, так что это может быть эквивалентно методу 2 ниже. Мне придется подумать и об этом дольше.
2. матрица расстояний - используя матрицу расстояний Левенштейна, вы сможете обнаружить дублирование по диагональному перемещению (вне диагонали) со стоимостью 0. Это может указывать на дублирование данных. Мне придется подумать об этом больше.

Answer 2

Вот приложение C #, которое я написал, которое решает эту проблему.

принимает
aabccacdcd

выходы
abcacd

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

class Program
{
    private static List<string> values;
    private const int MAX_PATTERN_LENGTH = 4;

    static void Main(string[] args)
    {
        values = new List<string>();
        values.AddRange(new string[] { "a", "b", "c", "c", "a", "c", "d", "c", "d" });


        for (int i = MAX_PATTERN_LENGTH; i > 0; i--)
        {
            RemoveDuplicatesOfLength(i);
        }

        foreach (string s in values)
        {
            Console.WriteLine(s);
        }
    }

    private static void RemoveDuplicatesOfLength(int dupeLength)
    {
        for (int i = 0; i < values.Count; i++)
        {
            if (i + dupeLength > values.Count)
                break;

            if (i + dupeLength + dupeLength > values.Count)
                break;

            var patternA = values.GetRange(i, dupeLength);
            var patternB = values.GetRange(i + dupeLength, dupeLength);

            bool isPattern = ComparePatterns(patternA, patternB);

            if (isPattern)
            {
                values.RemoveRange(i, dupeLength);
            }
        }
    }

    private static bool ComparePatterns(List<string> pattern, List<string> candidate)
    {
        for (int i = 0; i < pattern.Count; i++)
        {
            if (pattern[i] != candidate[i])
                return false;
        }

        return true;
    }
}

исправлены начальные значения для соответствия значениям вопросов

Answer 3

Я бы выбросил их всех в вашу любимую реализацию Set.

РЕДАКТИРОВАТЬ: Теперь, когда я понимаю вопрос, ваше оригинальное решение выглядит как лучший способ сделать это. Просто проведите цикл по массиву один раз, сохраняя массив флагов, чтобы отметить, какие элементы сохранить, и счетчик, чтобы отслеживать размер нового массива. Затем повторите цикл, чтобы скопировать все хранители в новый массив.

Answer 4

Я согласен, что если вы можете просто записать строки в набор, то это может быть самым простым решением.

Если по какой-то причине у вас нет доступа к реализации Set, я просто отсортировал бы строки по алфавиту, а затем прошел один раз и удалил дубликаты. Как их отсортировать и удалить дубликаты из списка, будет зависеть от того, на каком языке и в какой среде вы запускаете свой код.

РЕДАКТИРОВАТЬ: О, ик .... Я вижу на основе вашего разъяснения, что вы ожидаете, что шаблоны могут происходить даже в отдельных строках. Мой подход не решит вашу проблему. Сожалею. Вот вопрос для вас. Если бы у меня был следующий файл.

а

а

B

с

с

а

а

B

с

с

Ожидаете ли вы, что это упростится до

а

б

с