2014年12月26日

C#でn人の中から公平にm人を選ぶ

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


■問題 (出題者:にしお さん)
n人の中から公平にm人を選ぶ、くじ引きプログラムを作ってください。

まず、このプログラムの内部で使う「n個からm個を選ぶメソッド」を考えてみます。
このメソッドのインターフェースは、以下の2つがが考えられます。
IEnumerable<T> DrawLots<T>(IList<T> bag, int m)

IEnumerable<int> DrawLots(int n, int m)

前者は、数値に限定しないメソド、後者は、全体の個数を渡すメソッド。
前者の場合は、重複無し乱数で作成した Shuffle拡張メソッドを使えば、

IEnumerable<T> DrawLots<T>(IList<T> bag, int m) {
    return bag.Shuffle().Take(m);
}

と書けますが、bag の要素数が多い場合、例えば、100万人から3人選ぶみたいな 場合は、すべてをシャッフルするのはどう考えても無駄です。
なので、別のやり方も考えて見ました。

        static IEnumerable<T> DrawLots<T>(IList<T> bag, int m) {
            Random rnd = new Random();
            var result = new List<int>();
            while (result.Count < m) {
                int j = rnd.Next(0, bag.Count);
                if (!result.Contains(j)) {
                    result.Add(j);
                    yield return bag[j];
                }
            }
        }

答えをすべて覚えておかなければなりませんが、Shuffle するよりはましかなと 思います。 でも、100万人から90万人選ぶみたいなケースだと、このコードもあまり良くないです。
その場合、どういったコードが適切なのか難しいですね。
ちなみに、result は、LIst<T>ではなく、Dictionary<int,bool>でも良いですね。


後者のメソッドの場合だと、

        static IEnumerable<int> DrawLots(int n, int m) {
            Random rnd = new Random();
            var result = new List<int>();
            int i = 0;
            while (result.Count < m) {
                int j = rnd.Next(0, n);
                if (!result.Contains(j)) {
                    result.Add(j);
                    yield return j;
                }
            }
        }
先ほどのコードと本質は同じです。
以下は、上記2つのメソッドの使い方を示すコード。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            var r = DrawLots(new List<char> { 'a','b','c','d','e','f','g','h','i','j','k','l' },5);
            r.ToList().ForEach(Console.WriteLine);
            Console.ReadLine();

            var r2 = DrawLots(100, 5);
            r2.ToList().ForEach(Console.WriteLine);
            Console.ReadLine();
        }
    }
}


たぶん、これが今年最後の投稿です。
来年も懲りずに、このどう書く? org シリーズを継続していくつもり。

それでは皆さん良いお年を。


  

Posted by gushwell at 23:00Comments(0)TrackBack(0)

2014年12月21日

C#で自然数をm個の和で表す全パターンを求める

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

この問題のオリジナルタイトルは、「自然数の分割」です。

■問題 (出題者:herumiさん)
自然数nとm(n>=m>0)が与えられたとき,nをm個の非負の整数の和で表すやり方を全て出力してください. その際,和の組(x_1, ..., x_m)は大きい順に出力してください. ここでm = 3の時の「(a, b, c)が(A, B, C)より大きい」とは
(a > A)
(a == A) かつ (b > B)
(a == A) かつ (b == B) かつ (c > C)のいずれかが成り立つとき(つまりは辞書的順序)とします.
    
例:n = 5, m = 3が与えられたときは
5, 0, 0,
4, 1, 0,
4, 0, 1,
3, 2, 0,
3, 1, 1,
...
0, 1, 4,
0, 0, 5,
を出力する.
以下、C#のコード。
コメントにある通り、再帰処理で解を求めています。
Solveの第3引数は、答えが格納されるリストです。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            Solver sol = new Solver();
            sol.Solve(5,2);
            Console.ReadLine();
        }
    }

    // 再帰呼び出しを使ってる。
    class Solver {
        public void  Solve(int n, int m) {
            Solve(n,m, new List<int>());
        }

        public void Solve(int n, int m, List<int> ans) {
            if (m == 0) {
                if (n == 0) {
                    // めんどくさいので、答えが見つかった時点で印刷。
                    // コンソールアプリ専用。
                    ans.ForEach(x => Console.Write("{0}, ", x));
                    Console.WriteLine();
                }
            } else {
                // 大きい順に出力するために、n, n-1, n-2... と処理していく
                for (int k = n; k >= 0; k--) {
                    ans.Add(k);
                    Solve(n-k, m-1, ans);
                    ans.RemoveAt(ans.Count - 1);
                }
            }
        }
    }
}

  
Posted by gushwell at 22:00Comments(0)TrackBack(0)

2014年12月17日

C#でn個の数値を10個ずつ折り返して表示

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

この問題のオリジナルタイトルは、、「ビンゴの結果を整形表示」です。

■問題 (出題者:raynstard さん)
「重複無し乱数」の続編です。 「重複無し乱数」で作ったbingo関数の結果を下のように「何番目の乱数か」と セットにして10個ずつ折り返して表示するコードを書いてください。

>>> bingo(30)
 1  2  3  4  5  6  7  8  9 10
29 14 16 13 30 15 22 11 25  9

11 12 13 14 15 16 17 18 19 20
23  4 18  5 28 17  8 12 21 20

21 22 23 24 25 26 27 28 29 30
26  6  2 19  1  7 10 27  3 24

>>> bingo(35)
 1  2  3  4  5  6  7  8  9 10
 7 15  3 32  1 16 17 28  6 29

11 12 13 14 15 16 17 18 19 20
19 23 30 26 20  5 12  2 25 31

21 22 23 24 25 26 27 28 29 30
35 13 24 18 11  8 10 34 22 21

31 32 33 34 35
 9  4 27 33 14



前回作成した Bingoクラスに、Printメソッドを追加しました。
表示する個数が100を超えても、数字がくっつかないように工夫しています。 それ以外は、いたって普通のコードです。特に説明するまでもないかと。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            var result = Bingo.Create(9);
            Bingo.Print(result);
            Console.ReadLine();
        }
    }

    static class Bingo {
        // シャッフル拡張メソッド : Fisher-Yates shuffle アルゴリズムを採用
        public static IEnumerable<int> Create(int n) {
            return Enumerable.Range(1, n).Shuffle();
        }

        // これが新たに追加したメソッド
        public static void Print(IEnumerable<int> list) {
            string head = "";
            string data = "";
            // listの個数によって、幅を調整している。
            string format = string.Format("{{0,{0}}}", (int)(Math.Log10(list.Count()) + 2));
            int i = 1;
            foreach (var val in list) {
                head += string.Format(format, i);
                data += string.Format(format, val);
                if (i++ % 10 == 0) {
                    Print10(head, data);
                    head = "";
                    data = "";
                }
            }
            if (head.Length > 0)
                Print10(head, data);
        }

        private static void Print10(string head, string data) {
            Console.WriteLine(head);
            Console.WriteLine(data);
            Console.WriteLine();
        }


    }

    static class IEnumerableExtentions {
        static Random rnd = new Random();
        // シャッフル拡張メソッド : Fisher-Yates shuffle アルゴリズムを採用
        public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> list) {
            T[] result = list.ToArray();
            for (int i = result.Length - 1; i > 1; i--) {
                int j = rnd.Next(0, i);
                T a = result[i];
                result[i] = result[j];
                result[j] = a;
            }
            return result;
        }       
    }
}
  
Posted by gushwell at 22:30Comments(0)TrackBack(0)

2014年12月14日

C#で重複無し乱数を生成する

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その56
■問題 (出題者: raynstard さん)
整数nを渡すと1 〜 n までの整数を重複しないようランダムに出力する関数「bingo」を作ってください。

この問題は、1 〜 n までの数をシャッフルせよ、って問題と同義ですね。
.NET Framework に List<T> や IEnumerable<T>に要素をシャッフルするメソッドがあればいいんですが、無いみたいなので IEnumerable<T> の拡張メソッド Shuffle を自作しました。

Fisher-Yates shuffle アルゴリズムを採用しています。

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

namespace Doukaku.Org {
    static class ListExtentions {
        static Random rnd = new Random();
        // シャッフル拡張メソッド : Fisher-Yates shuffle アルゴリズムを採用
        public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> list) {
            T[] result = list.ToArray();
            for (int i = result.Length - 1; i > 1; i--) {
                int j = rnd.Next(0, i);
                T a = result[i];
                result[i] = result[j];
                result[j] = a;
            }
            return result;
        }
    }
}

このShuffle メソッドがあれば、Bingoメソッドを作るのは簡単ですね。
ここでは、BingoクラスのCreate static メソッドとしました。

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

namespace Doukaku.Org {

    static class Bingo {
        // シャッフル拡張メソッド : Fisher-Yates shuffle アルゴリズムを採用
        public static IEnumerable<int> Create(int n) {
            return Enumerable.Range(1, n).Shuffle();
        }
    }
}

このメソッドがただしく動作するかどうかも以下のコードで確認しました。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            for (int x = 0; x < 40; x++) {
                var nums = Bingo.Create(20);
                foreach (int n in nums)
                    Console.Write("{0} ", n);
                Console.WriteLine(IsBingo(nums, 20));
            }
            Console.WriteLine();
            Console.ReadLine();
        }

        static bool IsBingo(IEnumerable<int> seq, int n) {
            if (seq.Count() != n)
                return false;
            for (int i = 1; i <= n; i++) {
                if (!seq.Contains(i))
                    return false;
            }
            return true;
        }
    }
}

ちなみに、Bingo.Createは、LINQ 使った以下のような実装もありますね。

public static IEnumerable<int> Create(int n) {
    var list = Enumerable.Range(1, n).OrderBy(x => rnd.Next(n));
    return list;
}

  
Posted by gushwell at 21:52Comments(0)TrackBack(0)

2014年12月10日

C#でテキスト行の長さ合わせ

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

■問題
改行文字を複数個含むテキストデータを格納する文字列を 最大長の行を除く各行末に指定したパディング文字を適切な数だけ追加して、 すべての行が最大長の行と同じ長さに揃う文字列に変換する 手続あるいは関数を書いてください。
元の文字列の最後は改行です。 行の長さはその行に含まれる(行末の改行を除く)文字の数です。

変換前の文字列例
"○○○○\n○○○○○○○\n\n○○○○○\n"

上の文字列例をパディング文字'☆'を指定して変換した文字列
"○○○○☆☆☆\n○○○○○○○\n☆☆☆☆☆☆☆\n○○○○○☆☆\n"

必須ではありませんが、 テキストデータをトラバースする回数を減らす工夫をすると面白いかもしれません。
         ※ ごめんなさい、出題者がわかりません。

オリジナルの問題のタイトルは、「テキスト行の正規化」なのですが、漠然としているので、「テキスト行の長さ合わせ」としました。

最初に書いたものは、かなり力技のコードです。データが、string[] ではなく、stringだというのが ちょっと厄介ですね。

using System;
using System.Linq;
using System.Text;


namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            var s = Padding("○○○○\n○○○○○○○\n\n○○○○○\n",'あ');
            Console.WriteLine(s);
        }

        static string Padding(string text, char p) {
            int maxlength = int.MinValue;
            int length = 0;
            foreach (char c in text) {
                if (c == '\n') {
                    if (maxlength < length)
                        maxlength = length;
                    length = 0;
                } else
                    length++;
            }
            StringBuilder sb = new StringBuilder();
            length = 0;
            foreach (var c in text) {
                if (c == '\n') {
                    sb.AppendLine(new string(p,maxlength-length));
                    length = 0;
                } else {
                    length++;
                    sb.Append(c);
                }
            }
            if (length > 0)
                sb.AppendLine(new string(p, maxlength - length));
            return sb.ToString();
        }
    }
}

入力文字列の最後が必ず \n という前提があれば、最後の if 文は不要です。

次に書いたのは、LINQ to Objectを使ったコード。
効率は無視していますが、上のPaddingメソッドに比べると、随分とすっきりしました。

    static string Padding2(string text, char p) {
        var lines = text.Split('\n');
        int maxlength = lines.Max(t => t.Length);
        int count = lines.Last() == "" ? lines.Length - 1 : lines.Length;
        return lines.Take(count)
                    .Aggregate("", (r, s) => r += s.PadRight(maxlength,p) + '\n');
    }

  
Posted by gushwell at 23:00Comments(0)TrackBack(0)

2014年12月07日

C#で年間カレンダーを表示する

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

■問題 (出題者:186 さん)
nを入力としてn年の年間カレンダーを返すプログラムを作ってください
少なくとも日曜日と土曜日が判別出来るようにしてください
出力は標準出力でもファイルでも構いません
デザインは各自のお好みで

表示とカレンダーを作成する部分を分離したかったので、まずは、CalenderMakerCore という クラスを作成しました。

using System;
using System.Collections.Generic;

namespace Doukaku.Org {
    // カレンダーを作成する部分を、CalenderMakerCoreとして独立させている。
    public static class CalenderMakerCore {
        // IEnumerable<int[]>を返すメソッドで、int[]には日曜日から始まる1週間分の
        // 日にちが入っています。0 は、日付の無い箇所(空白表示)を示している。
        // それが、一ヶ月分のカレンダー上の行数分返されます。
        public static IEnumerable<int[]> GetMonthCalender(int year, int month) {
            List<int> oneWeek = new List<int>();
            DateTime dt = new DateTime(year, month, 1);
            // 空白の箇所(日付の無い箇所)は、0 で示す
            for (int i = 0; i < (int)dt.DayOfWeek; i++)
                oneWeek.Add(0);
            for (; dt.Month == month; dt = dt.AddDays(1)) {
                oneWeek.Add(dt.Day);
                if (dt.DayOfWeek == DayOfWeek.Saturday) {
                    yield return oneWeek.ToArray();
                    oneWeek.Clear();
                }
            }
            if (oneWeek.Count != 0)
                yield return oneWeek.ToArray();
        }
    }
}

このクラスを使って、ConsoleCalenderクラスを定義します。
一ヶ月分のカレンダーを表示する PrintMonthCalender メソッドを定義し、 1年分を表示する PrintYearCalender メソッドは、このPrintMonthCalender を12回呼び出しています。

このようにクラスを分離すれば、コンソール出力以外でも、いろんな用途にCalenderMakerCore が使えるようになりますよね。

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

namespace Doukaku.Org {

    // CalenderMakerCoreを利用して、カレンダーを作成する。
    // このクラスは、表示に専念
    class ConsoleCalender {
        public void PrintYearCalender(int year) {
            for (int m = 1; m <= 12; m++) {
                PrintMonthCalender(year, m);
                Console.WriteLine();
            }
        }

        public void PrintMonthCalender(int year, int month) {
            GetMonthCalender(year, month).ForEach(s => Console.WriteLine(s));
        }

        IEnumerable<string> GetMonthCalender(int year, int month) {
            List<string> lines = new List<string>();
            yield return string.Format("      {0}年{1}月", year, month);
            yield return " 日 月 火 水 木 金 土";
            var seq = CalenderMakerCore.GetMonthCalender(year, month);
            var q = seq.Select(w => w.Aggregate("", (line, d) => line += String.Format("{0,3:#}", d)));
            foreach (var s in q)
                yield return s;
        }
    }
}

で、最後は、このConsoleCalender クラスを呼び出す Mainメソッドを定義します。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            ConsoleCalender calender = new ConsoleCalender();
            calender.PrintYearCalender(2014);

            // calender.PrintYearCalender(2014,11);  2014/11だけ表示 こんな呼び出し方もできる。
            Console.ReadLine();
        }
    }
}

  
Posted by gushwell at 21:40Comments(0)TrackBack(0)

2014年12月03日

C#で指定されたフォルダ以下のファイルをゴミ箱へ

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

■問題 (出題者:にしお さん)
指定したフォルダ以下にある、ファイル名が"~"で終わるファイルを削除するプログラムを作ってください。 指定したフォルダの中にあるフォルダのさらに中にあるファイルも削除の対象です。

今回は、シリーズ53回目にちなんで、ごみ箱に関する問題を取り上げます(^^;;
問題文から判断すると、普通にファイルの削除をすればOKそうな問題ですが、せっかくなので ゴミ箱へ移動するコードとしてみました。

以下のようなクラスを書きました。
Microsoft.VisualBasicアセンブリを参照に加えています。
このアセンブリのなかの、FileSystem.DeleteFile メソッドを使えば、簡単にゴミ箱への移動ができます。
作成したCleanメソッドの第3引数は省略可能です。
RecycleOption.DeletePermanentlyを指定すれば、ゴミ箱への移動ではなく、削除することができます。
ちなみに、再帰処理を書くのが面倒なので、Directory.GetFiles をつかって、指定フォルダ以下のすべてのファイルを求めています。

using System;
using System.IO;
using Microsoft.VisualBasic.FileIO;
using System.Linq;

namespace Doukaku.Org {

    public static class FileCleaner {
        public static void Clean(string dir, Func<string,bool> filter,
                                 RecycleOption option = RecycleOption.SendToRecycleBin) {
            var files = Directory.GetFiles(dir, "*", System.IO.SearchOption.AllDirectories);
            foreach (var filepath in files) {
                if (filter(filepath) == true)
                    FileSystem.DeleteFile(filepath, UIOption.OnlyErrorDialogs, option);
            }
        }
    }
}

使うときには、こんな風に書きます。

FileCleaner.Clean("C:\\TEMP", s => s.Last() == '~');

  
Posted by gushwell at 22:30Comments(0)TrackBack(0)