Как объединить несколько последовательностей

У меня есть несколько последовательностей следующим образом

введите здесь описание изображения

Я храню их в списке списка строк

List<List<String>> Sequences;

Я хотел бы объединить их, чтобы удалить последовательности, которые покрыты другими последовательностями. Например, последовательность V VPC VPS S покрывается последовательностью V MV VPC VPC VPS VPA S, поскольку последняя содержит все элементы первой и в том же порядке (этого примера нет в приведенных выше списках).

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

Мой подход состоит в том, чтобы перебирать последовательности и для каждой последовательности находить последовательности, которые пересекаются с ней сами по себе и имеют тот же порядок, если да, то удалить его, что-то вроде

foreach (var item in Sequences)
{
    if (Sequences.Any(x => x.Intersect(item).SequenceEqual(item)))
    {
        Sequences.Remove(item);
    }
}

c# linq algorithm sequences
person Ahmad    schedule 11.02.2016    source источник
comment
Вы хотите собрать всю коллекцию в одну?   -  person CodeNotFound    schedule 11.02.2016
comment
@CodeNotFound Нет, я просто хочу удалить последовательности, которые можно вывести из других последовательностей. например, вы можете вывести a c f из a b c d e f   -  person Ahmad    schedule 11.02.2016
comment
Вы можете показать свой не освоенный подход, а какой-то мастер покажет более искусный.   -  person Salvador Dali    schedule 11.02.2016
comment
последовательность V VPC VPS S покрывается последовательностью V MV VPC VPC VPSD VPA S, поскольку последняя содержит все элементы первой и в том же порядке. - Нет, VPS есть в первом, а не во втором.   -  person Enigmativity    schedule 11.02.2016
comment
Не могли бы вы написать свои списки как действительный код С#? Тогда не могли бы вы объяснить в мучительных подробностях, как вычислить охватываемые отношения?   -  person Enigmativity    schedule 11.02.2016
comment
так что у вас есть список последовательностей, и каждая последовательность имеет список элементов. если все элементы последовательности A появляются в другой последовательности B в том же порядке в B, что и в A, но не обязательно рядом друг с другом в B, то вы хотите удалить A?   -  person matt    schedule 11.02.2016
comment
Порядок не имеет значения, я думаю.   -  person CodeNotFound    schedule 11.02.2016

Ответы (2)


arrow_upward
3
arrow_downward

Если порядок имеет значение:

bool IsSubsequence<T>(IEnumerable<T> subseq, IEnumerable<T> superseq)
    where T : IEquatable<T>
{
    var subit = subseq.GetEnumerator();
    if (!subit.MoveNext()) return true; // Empty subseq -> true
    foreach (var superitem in superseq)
    {
        if (superitem.Equals(subit.Current))
        {
            if (!subit.MoveNext()) return true;
        }
    }
    return false;
}

List<List<T>> PruneSequences<T>(List<List<T>> lists)
    where T : IEquatable<T>
{
    return lists
        .Where(sublist =>
            !lists.Any(superlist =>
                sublist != superlist &&
                IsSubsequence(sublist, superlist)))
        .ToList();
}

Использование:

var Sequences = new List<List<string>> {
    new List<string> { "N", "MN", "MN", "S" },
    new List<string> { "PUNC" },
    new List<string> { "N" },
    new List<string> { "V", "VPC", "VPS", "S" },
    new List<string> { "N", "NPC" },
    new List<string> { "N", "MN" },
    new List<string> { "N", "NPA" },
    new List<string> { "ADJ" },
    new List<string> { "V", "MV", "VPC", "VPC", "VPSD", "VPA", "S" },
    new List<string> { "PREP", "PPC", "PPC" },
    new List<string> { "PRONC", "NPC" },
    new List<string> { "JONJ", "CPC", "CPC", "VPC", "VPSD", "CLR" },
    new List<string> { "CONJ" },
    new List<string> { "AUX" },
    new List<string> { "V", "MV", "VPC" },
    new List<string> { "N", "NPA", "NPC", "NPC" }
};
var PrunedSequences = PruneSequences(Sequences);

Результат:

N MN MN S 
PUNC 
V VPC VPS S 
ADJ 
V MV VPC VPC VPSD VPA S 
PREP PPC PPC 
PRONC NPC 
JONJ CPC CPC VPC VPSD CLR 
CONJ 
AUX 
N NPA NPC NPC
person Markus Jarderot    schedule 11.02.2016
comment
Большое спасибо за полный ответ! - person Ahmad; 11.02.2016
comment
Однако теперь я думаю, что если я удалю повторяющиеся элементы (которые сразу следуют друг за другом) из каждой последовательности, результат будет лучше. - person Ahmad; 11.02.2016

arrow_upward
1
arrow_downward 

Sequences.Where(i=>!Sequences.Any(x => ReferenceEquals(i,x) == false && x.Intersect(i).SequenceEqual(i)));

Ваше решение может потерпеть неудачу, потому что оно проверяет элемент против самого себя?

person matt    schedule 11.02.2016
comment
Спасибо, однако кажется, что если бы я мог сначала удалить повторяющиеся элементы из каждой блестки, а затем применить решение, было бы лучше - person Ahmad; 11.02.2016