先頭集団を求めるアルゴリズム (1)

で、もし与えられる集合が

{ 10, 9, 8, 5, 4, 3, -1, -2 }

だったりして、

{ 10, 9, 8 } { 5, 4, 3, -1, -2 }

にならないかなと思っても…

count:6, ret:10, 9, 8, 5, 4, 3

…のように「最大の隔たりは 3 → -1 間の4でしょ」ということになる。
「他は1しか差が開いてないんだから、3つ差も4つ差も一緒だろ」ということにはならない。

これを解決するためには再帰で「差の先頭集団」を求めればいい。で「差の先頭集団」から「その集団内の（入力リスト上の位置で）最も先頭に近い差」をしきい値として使う。分かりにくい。

コード(C#)

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication2013_05_28
{
    class Program
    {
        static void Main(string[] args)
        {
            var data = new List<int> { 10, 9, 8, 5, 4, 3, -1, -2 };
            Func<int, float> func = (datum => (float)datum);
            var ret = cl<int>(data, func, 2);
            Console.Out.WriteLine("count:{0}, ret:{1}", ret.Count(), string.Join(", ", ret));

        }

        static IEnumerable<T> cl<T>(IEnumerable<T> target, Func<T, float> toScoreFunc, int recursionCount)
        {
            recursionCount--;
            var sorted = target.OrderByDescending(d => toScoreFunc(d));
            var scores = new List<Tuple<T, float>> { };

            var _datum = sorted.First();
            foreach (var datum in sorted)
            {
                float diff = toScoreFunc(_datum) - toScoreFunc(datum);
                scores.Add(new Tuple<T, float>(datum, diff));
                _datum = datum;
            }


            Tuple<T, float> threshould;
            if (recursionCount >= 1)
            {
                var diffs = scores.Select<Tuple<T, float>, float>(s => s.Item2);
                Func<float, float> func = (datum => (float)datum);
                var ret2 = cl<float>(diffs, func, recursionCount);
                threshould = scores.First(d => ret2.Contains(d.Item2));
            }
            else
            {
                threshould = scores.OrderByDescending(d => d.Item2).ToList().First();
            }

            var ret = sorted.TakeWhile(d => !d.Equals(threshould.Item1));
            return ret;
        }
    }
}

実行結果。

count:3, ret:10, 9, 8

「他は1しか差が開いてないんだから、3つ差も4つ差も一緒」ということになった。3つ差の位置を先頭集団の終わりと見なしている。