2015年02月25日

C#で数値リストの圧縮

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その72

整列済みの number のリストがある。

[1, 3, 4, 5, 6, 12, 13, 15, 20, 25, 26, 27]
このようなリストで数が3つ以上連続している部分を[1, 2, 3] -> [1, 3] のように両端のみを書くような記法を導入する。 ただし2個とびや3個とびなどn個とびの場合、[1, 3, 5, 7] -> [1, 7, 2]のように[start, stop, step]のような並びにする。 最初の例のリストであれば以下のようになる。
[1 [3, 6] 12, 13, [15, 25, 5], 26, 27]
このようなリストに変換をするコードを書いてください。

すみんせん。この問題が、どう書く?orgに掲載されたものなのかの確認ができていません m(_ _)m
僕のPCのどう書く?org用のフォルダ内にあったコードなので、たぶん、そうなのだろうと思いますので、ここに載せることとします。

C#のような言語だとリスト表現をどうするのか判断に迷いますね。
あくまでも文字列として表示することだけを目的とするのか、
内部表現として、問題が求めているようなリスト構造にするのか?
ここでは両方で書いてみました。
でも、どっちもあまりきれいなコードにはなりませんでした。

まずは、文字列として表現すれば良しとするコード。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            int[] nums = { 1, 3, 4, 5, 6, 12, 13, 15, 20, 25, 26, 27, 28, 29, 30, 33, 36, 37, 90 };
            var str = CompactNumbers9(nums);
            Console.WriteLine(str);
        }

        private static string CompressNumbers(int[] nums) {
            return string.Format("[{0}]", CompressNumbers(nums, 0, int.MinValue, new List<int>()));
        }

        // もっと簡潔に書けそうなきがするが、僕の頭ではこれが精一杯。
        private static object CompressNumbers(int[] nums, int index, int prev, List<int> list) {
            int diff = (list.Count < 2) ? -1 : list[1] - list[0];
            if (index >= nums.Length)
                return Symbolize(list, diff);
            int curr = nums[index];
            string s = "";
            if (diff == curr - prev || list.Count <= 1) {
                list.Add(curr);
            }  else {
                if (list.Count == 2) {
                    list.RemoveAt(list.Count - 1);
                    s = Symbolize(list, diff) + ", ";
                    list = new List<int> { prev, curr };
                } else {
                    s = Symbolize(list, diff) + ", ";
                    list = new List<int> { curr };
                }
            }
            return s + CompressNumbers(nums, index + 1, curr, list);
        }

        private static string Symbolize(List<int> list, int diff) {
            int count = list.Count;
            if (count == 1)
                return string.Format("{0}", list[0]);
            else if (count == 2)
                return string.Format("{0}, {1}", list[0], list[1]);
            else if (diff > 1)
                return string.Format("[{0}, {1}, {2}]", list[0], list[count - 1], diff);
            else
                return string.Format("[{0}, {1}]", list[0], list[count - 1]);
        }
}

次に、内部表現として、圧縮したリストを表現するもの。
こっちは、CompressNumbers というクラスを定義しています。
結果は、List して、objectには、int or int[] が入るものとしましたが、 うーーん、これってどうなんだろう?C#的には、あまり良いデータ設計じゃないですね。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            CompressNumbers cn = new CompressNumbers(new int[] { 1, 3, 4, 5, 6, 12, 13, 15, 20, 25, 26, 27 });
            cn.Execute();
            cn.Print();
            Console.ReadLine();
        }
    }

    class CompressNumbers {
        private List<object> result = new List<object>();
        private int[] nums;

        public CompressNumbers(int[] nums) {
            this.nums = nums;
        }

        public List<object> Execute() {
            Execute(0);
            return result;
        }

        private void Execute(int index, int start = -1, int stop = -1, int step = -1) {
            if (index >= nums.Length) {
                Symbolize(start, stop, step);
            } else {
                int curr = nums[index];
                int diff = curr - stop;
                if (step == -1)
                    Execute(index + 1, curr, curr, 0);
                else if (step == 0 || diff == step)
                    Execute(index + 1, start, curr, diff);
                else if (start + step == stop) {
                    Symbolize(start, start, 0);
                    Execute(index + 1, stop, curr, diff);
                } else {
                    Symbolize(start, stop, step);
                    Execute(index + 1, curr, curr, 0);
                }
            }
        }

        private void Symbolize(int start, int stop, int step) {
            if (step == 0)
                result.Add(start);
            else if (start + step == stop) {
                result.Add(start);
                result.Add(stop);
            } else if (step == 1)
                result.Add(new int[] { start, stop });
            else
                result.Add(new int[] { start, stop, step });
        }

        public void Print() {
            Console.Write("[");
            int count = 0;
            foreach (var o in result) {
                if (count++ > 0)
                    Console.Write(", ");
                if (o.GetType().IsArray) {
                    Console.Write("[{0}]", string.Join(", ", o as IEnumerable<int>));
                } else {
                    Console.Write("{0}", o);
                }
            }
            Console.Write("]");
        }
    }
}



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52407165