順列の問題

0~9までの数字のカードがN枚ある。同じ数字のカードは1枚とは限らない。
そこから、M枚使用しM桁の整数を作るとき、小さい方から数えi番目の数値は何か？
※先頭桁に0はこないものとする。

という問題が与えられた場合、これを効率よく説くにはどうすればよいか？

とりあえず、効率よくという部分は無視して、順列を作成して前から数えてみた。順列を作成するに当たりLinqを使用しているサイトが見つかったので、利用にさせていただいた。
http://d.hatena.ne.jp/taguo/20080722/1216745650

view plainprint?

1. class Program  
2. {  
3.     static void Main(string[] args)  
4.     {  
5.         int[] array = {0,0,1,2,2,3};  
6.         var result = array.GetPermutation(4)  
7.             .Where(x => x.ElementAt(0) != 0)  
8.             .Select(x => string.Join("", x.Select(i => i.ToString()).ToArray()))  
9.             .Distinct();  
10.   
11.         result = result.Skip(10).Take(1);  
12.         foreach (var item in result)  
13.         {  
14.             Console.WriteLine(item);  
15.         }  
16.     }  
17. }  
18.   
19. public static class Util  
20. {  
21.     public static IEnumerable<IEnumerable<T>> GetPermutation<T>(this IEnumerable<T> source, int count)  
22.     {  
23.         return Enumerable.Range(0, count)  
24.             .Select(_ => source)  
25.             .Select(et => et.Select((t, i) => new { t, i }))  
26.             .Aggregate(Enumerable.Repeat(Enumerable.Repeat(new { t = default(T), i = default(int) }, 0), 1)  
27.                 , (ac, et) => from a in ac  
28.                               from t in et  
29.                               where !a.Contains(t)  
30.                               select a.Concat(Enumerable.Repeat(t, 1)))  
31.             .Select(ea => ea.Select(a => a.t));  
32.     }  
33. }  

class Program
{
    static void Main(string[] args)
    {
        int[] array = {0,0,1,2,2,3};
        var result = array.GetPermutation(4)
            .Where(x => x.ElementAt(0) != 0)
            .Select(x => string.Join("", x.Select(i => i.ToString()).ToArray()))
            .Distinct();

        result = result.Skip(10).Take(1);
        foreach (var item in result)
        {
            Console.WriteLine(item);
        }
    }
}

public static class Util
{
    public static IEnumerable<IEnumerable<T>> GetPermutation<T>(this IEnumerable<T> source, int count)
    {
        return Enumerable.Range(0, count)
            .Select(_ => source)
            .Select(et => et.Select((t, i) => new { t, i }))
            .Aggregate(Enumerable.Repeat(Enumerable.Repeat(new { t = default(T), i = default(int) }, 0), 1)
                , (ac, et) => from a in ac
                              from t in et
                              where !a.Contains(t)
                              select a.Concat(Enumerable.Repeat(t, 1)))
            .Select(ea => ea.Select(a => a.t));
    }
}