title: Compute Superset of Sequences
body: <p>Given any number of sequences I need to compute a superset "containing the input sequences". </p>
  
  <p>The result must be minimum in length and the order of the input elements must not be changed. Items of the input must not necessarily be kept together.</p>
  
  <p>A comparison is provided to determine precedence of any symbol / element when needed during computation.</p>
  
  <p>Curious what the particular problem is called in number theory.</p>
  
  <p>Preferably I'd like to solve this making use of .NET Types and IEnumerable Extensions.</p>
  
  <p>Example with the comparison based on the alphabet:</p>
  
  <pre><code>ABC, ABC -&gt; ABC
  
  ABC, ABD -&gt; ABCD
  
  ABCD, BCD, ACD, ACB -&gt; ABCDB
  
  ABCD, EBCD -&gt; AEBCD
  </code></pre>
  
  <p>My approach so far, not slving the last one (ABCD, EBCD)</p>
  
  <pre><code>namespace Ra.Essentials
  {
     using System;
     using System.Collections.Generic;
     using System.Linq;
  
     public static class SequenceReductionExtensions
     {
        public static IEnumerable&lt;T&gt; Reduce&lt;T&gt;(this IEnumerable&lt;IEnumerable&lt;T&gt;&gt; input)
        {
           return input.Reduce(Comparer&lt;T&gt;.Default.Compare);
        }
  
        public static IEnumerable&lt;T&gt; Reduce&lt;T&gt;(this IEnumerable&lt;IEnumerable&lt;T&gt;&gt; input, Comparison&lt;T&gt; comparison)
        {
           var enumerators = input.Select(o =&gt; o.GetEnumerator()).ToList();
  
           enumerators.RemoveAll(o =&gt; !o.MoveNext());
  
           while (enumerators.Any())
           {
              var symbols = enumerators.GroupBy(o =&gt; o.Current);
  
              // review: orderby key
              var spread = symbols.GroupBy(o =&gt; o.Count()).OrderByDescending(o =&gt; o.Count());
  
              T ret;
  
              var firstSpread = spread.First();
  
              // gleiche Anzahl verschiedener Symbole
              if (firstSpread.Count() &gt; 1)
              {
                 var a1 = firstSpread.First().Key;
                 var a2 = firstSpread.Skip(1).First().Key;
  
                 ret = comparison(a1, a2) &lt; 0 ? a1 : a2;
              }
              else
              {
                 ret = firstSpread.First().Key;
              }
  
              enumerators.RemoveAll(o =&gt; comparison(o.Current, ret) == 0 &amp;&amp; !o.MoveNext());
  
              yield return ret;
           }
        }
     }
  }
  </code></pre>
  
  <p>And Unit Test:</p>
  
  <pre><code>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&lt;string&gt; input)
        {
           "Ex:".ToOutput();
           expected.ToOutput();
  
           "In:".ToOutput();
           input.ForEach(o =&gt; o.ToOutput());
  
           CollectionAssert.AreEqual(expected, CallReduce(input));
        }
  
        private static string CallReduce(IEnumerable&lt;string&gt; input)
        {
           var sequences = input.Select(o =&gt; o.ToList());
  
           return string.Join(string.Empty, sequences.Reduce(Comparer&lt;char&gt;.Default.Compare));
        }
     }
  </code></pre>
  
  <p>}</p>