まとめようと思ったけれど、駄目だったよ。
コード(C#)
using System; using System.Collections.Generic; using System.Linq; namespace ConsoleApplication2013_05_28 { class Program { static void Main(string[] args) { Func<int, float> func = (d => (float)d); var data = new List<int> { 10, 9, 8, 5, 4, 3, -1, -2 }; //Func<string, float> func = (d => float.Parse(d)); //var data = new List<string> { "10", "9", "8", "5", "4", "3", "-1", "-2" }; Console.Out.WriteLine("data:\t\t{{ {0} }}\t({1})", string.Join(", ", data), data.Count()); var topGroup = TopGroupOf<int>(data, func); //var topGroup = TopGroupOf<string>(data, func); Console.Out.WriteLine("topGroup:\t\t{{ {0} }}\t({1})", string.Join(", ", topGroup), topGroup.Count()); } static private IEnumerable<Tuple<T, float>> _scores<T>(IEnumerable<T> target, Func<T, float> toScoreFunc) { var ret = new List<Tuple<T, float>> { }; { var sorted = target.OrderByDescending(d => toScoreFunc(d)); var _datum = sorted.First(); foreach (var datum in sorted) { float diff = toScoreFunc(_datum) - toScoreFunc(datum); ret.Add(new Tuple<T, float>(datum, diff)); _datum = datum; } } return ret; } static IEnumerable<T> TopGroupOf<T>(IEnumerable<T> group, Func<T, float> toScoreFunc) { var scores = _scores<T>(group, toScoreFunc); Console.Out.WriteLine("scores :\t{{ {0} }}\t({1})", string.Join(", ", scores), scores.Count()); var diffs = scores.Select(e => e.Item2); var scores2 = _scores<float>(diffs, (d => (float)d)); Console.Out.WriteLine("scores2:\t{{ {0} }}\t({1})", string.Join(", ", scores2), scores2.Count()); var threshould2 = scores2.OrderByDescending(d => d.Item2).ToList().First(); //// Max() var topgroup2 = scores2.TakeWhile(e => !e.Equals(threshould2)).Select(e => e.Item1); Console.Out.WriteLine("scores2-threshould:\t{0}", threshould2); var threshould = scores.First(e => topgroup2.Contains(e.Item2)); //// Find var topgroup = scores.TakeWhile(e => !e.Equals(threshould)).Select(e => e.Item1); Console.Out.WriteLine("scores-threshould:\t{0}", threshould); return topgroup; } } }
実行結果。
data: { 10, 9, 8, 5, 4, 3, -1, -2 } (8) scores : { (10, 0), (9, 1), (8, 1), (5, 3), (4, 1), (3, 1), (-1, 4), (-2, 1) } (8) scores2: { (4, 0), (3, 1), (1, 2), (1, 0), (1, 0), (1, 0), (1, 0), (0, 1) } (8) scores2-threshould: (1, 2) scores-threshould: (5, 3) topGroup: { 10, 9, 8 } (3)
{ 10, 9, 8, 5, 4, 3, -1, -2 } (要素数8)の先頭集団は { 10, 9, 8 } の3つ。
メモ
以下、まとまらなかったメモ。
再帰はしないほうがいい。繰り返しても結果は一緒だし。
「先頭集団を求めること」を抽象化すると…トップクラス(最大級)の部分集合を選び出すということ。
つまり曖昧な最大値判定。
ソートした数列の「前要素との差」を求めて、その先頭集団を求めると…差の開いているところが網羅できると。
で、それらのうちの(ソート前の数列上で)先頭に近い位置にある「差の開き」で数列を分割すると、より人の感覚に近い先頭集団判定ができると。
入力データをソートしてから「前要素との差」を算出
↓
(前要素との)差を入力データにする
↓
入力データをソートしてから「前要素との差」を算出(差の差)、最大の差(差の差のうちの最大)を探す
↓
最大''級''の隔たり
↓
…のうちのもっとも先頭にある1件…までが入力データの先頭集団
「ソートして差を求める」というのは元々の差ではないので、入力データ上に存在しない差(隔たり)になっている。無意味。