c# - Compute Superset of Sequences -

given number of sequences need compute superset "containing input sequences".

the result must minimum in length , order of input elements must not changed. items of input must not kept together.

a comparison provided determine precedence of symbol / element when needed during computation.

curious particular problem called in number theory.

preferably i'd solve making use of .net types , ienumerable extensions.

example comparison based on alphabet:

abc, abc -> abc  abc, abd -> abcd  abcd, bcd, acd, acb -> abcdb  abcd, ebcd -> aebcd 

my approach far, not slving last 1 (abcd, ebcd)

namespace ra.essentials {    using system;    using system.collections.generic;    using system.linq;     public static class sequencereductionextensions    {       public static ienumerable<t> reduce<t>(this ienumerable<ienumerable<t>> input)       {          return input.reduce(comparer<t>.default.compare);       }        public static ienumerable<t> reduce<t>(this ienumerable<ienumerable<t>> input, comparison<t> comparison)       {          var enumerators = input.select(o => o.getenumerator()).tolist();           enumerators.removeall(o => !o.movenext());           while (enumerators.any())          {             var symbols = enumerators.groupby(o => o.current);              // review: orderby key             var spread = symbols.groupby(o => o.count()).orderbydescending(o => o.count());              t ret;              var firstspread = spread.first();              // gleiche anzahl verschiedener symbole             if (firstspread.count() > 1)             {                var a1 = firstspread.first().key;                var a2 = firstspread.skip(1).first().key;                 ret = comparison(a1, a2) < 0 ? a1 : a2;             }             else             {                ret = firstspread.first().key;             }              enumerators.removeall(o => comparison(o.current, ret) == 0 && !o.movenext());              yield return ret;          }       }    } } 

and unit test:

namespace ra.essentials.tests {    using system.collections.generic;    using system.linq;    using nunit.framework;    using xbase.essentials;     [testfixture]    public class sequencereductionextensionstests    {       [testcase("abc", new[] { "abc" })]       [testcase("abc", new[] { "abc", "abc" })]       [testcase("abcd", new[] { "abc", "abd" })]       [testcase("abcdb", new[] { "abcd", "bcd", "acd", "acb" })]       [testcase("aebcd", new[] { "abcd", "ebcd" })]       public void should_reduce(string expected, ienumerable<string> input)       {          "ex:".tooutput();          expected.tooutput();           "in:".tooutput();          input.foreach(o => o.tooutput());           collectionassert.areequal(expected, callreduce(input));       }        private static string callreduce(ienumerable<string> input)       {          var sequences = input.select(o => o.tolist());           return string.join(string.empty, sequences.reduce(comparer<char>.default.compare));       }    } 

}