9770


次の問題を考えています。  
（<http://www004.upp.so-net.ne.jp/s_honma/mathbun/mathbun113.htm>）

１からNまでのN個の整数で、  
ア）隣り合う２数の差は３以上、１つおいた数との差も３以上  
という条件を満たす順列は、何通りあるだろうか？  
ただし、 **順番を逆にしたものもそれぞれ１つずつ数えるものとします。**

（より一般的には次のような問題です。  
１からNまでのN個の整数で、  
イ）隣り合う２数の差はD以上、１個おいた数との差もD以上、… 、D - 2個おいた数との差もD以上  
という条件を満たす順列は、何通りあるだろうか？  
例えば、N = 9、D = 3 のとき、  
[3, 6, 9, 2, 5, 8, 1, 4, 7]  
[7, 4, 1, 8, 5, 2, 9, 6, 3]  
の２通りあります。)

この問題の答えを速く求めるコードを考えてください。  
以下、答えを求めるのが大変遅いコードです。

[code]

    N = 11
    D = 3
    
    def check(a, i)
      j = 1
      d_max = [i, D - 1].min
      while (a[i] - a[i - j]).abs >= D && j < d_max
        j += 1
      end
      (a[i] - a[i - j]).abs >= D
    end
    
    (D..N).each{|n|
      cnt = 0
      (1..n).to_a.permutation{|a|
        i = 1
        while check(a, i) && i < n - 1
          i += 1
        end
        if check(a, i)
          cnt += 1
        end
      }
      p [n, cnt]
    }
    
[/code]

出力結果  
[3, 0]  
[4, 0]  
[5, 0]  
[6, 0]  
[7, 0]  
[8, 0]  
[9, 2]  
[10, 40]  
[11, 792]

（追記）  
D = 3 のとき、N = 12 までならすぐ求まるコードを  
回答に載せました。


CC BY-SA 3.0
2015-05-02T05:20:53.937
9766
2016-12-18T06:12:09.997
2016-12-18T06:12:09.997
5363
5363
question
ruby アルゴリズム
隣り合う２数の差は３以上、１つおいた数との差も３以上の順列は何通りあるか？


rubyじゃなくC#ですが。

使用済みの値の判定用配列を用意して枝刈りして、ひとつ前・二つ前の値を渡す再帰にしてみた。  
N=12までなら一瞬。N=13から厳しい。

[code]

    class Program
    {
        static void Main(string[] args)
        {
            for (int n = 1; n < 100; n++)
            {
                int count = Calc.Check(n, 3);
                Console.WriteLine("N=" + n + "\t" + count);
            }
        }
    
        class Calc
        {
            public static int Check(int n, int d)
            {
                Calc data = new Calc();
                data.list = new int[n + 1]; //桁数分の配列を用意 ただしlist[0]は計算量削減のために未使用
                data.diff = d;
                data.Check(1, -n, -n);//
    
                return data.count;
            }
    
            int[] list; //使用された数の判定用//結果確認用にintですがboolでも十分
            int diff;//必要な差
            int count;//結果の数
    
            /// <param name="lv">再帰の深さ = n桁目</param>
            /// <param name="v1">ひとつ前の値</param>
            /// <param name="v2">ふたつ前の値</param>
            private void Check(int lv, int v1, int v2)
            {
                if (lv < list.Length)
                {
                    for (int n = 1; n < list.Length; n++)
                    {
                        if (list[n] > 0)
                        {
                            continue; //数値ｎは使用済みなので打ち切り
                        }
                        if (Math.Abs(n - v1) < diff || Math.Abs(n - v2) < diff)
                        {
                            continue; //前との差が条件に一致しないので打ち切り
                        }
    
                        list[n] = lv;//=true    //数値nがlv桁目で使用済みであるとマーク
                        Check(lv + 1, n, v1);   //次の桁位置、ひとつ前、二つ前の値　を渡して再帰
                        list[n] = 0; //=false   //数値nを未使用に戻す
                    }
                }
                else
                {
                    count++;
                    //Console.Write("[");
                    //for (int c = 1; c < list.Length; c++)
                    //{
                    //    if (c!=1)
                    //    {
                    //        Console.Write(",");
                    //    }
                    //    Console.Write(list[c]);
                    //}
                    //Console.WriteLine("]");
                }
            }
        }
    }
    
[/code]


CC BY-SA 3.0
2015-05-02T10:04:30.217
9769
2015-05-02T10:16:23.160
2015-05-02T10:16:23.160
8000
4926
9766
answer


条件に合うかしらみつぶしに調べるのではなく、  
条件を満たす順列を再帰的に作ってみました。  
N = 12 までならすぐ求まります。  
なお、副産物もつけてみました。

[code]

    N = 13
    D = 3
    
    def check(d, a, i)
      return true if i == 0
      j = 1
      d_max = [i, d - 1].min
      while (a[i] - a[i - j]).abs >= d && j < d_max
        j += 1
      end
      (a[i] - a[i - j]).abs >= d
    end
    
    def solve(d, len, a = [])
      b = []
      if a.size == len
        b << a
      else
        (1..len).each{|m|
          s = a.size
          if s == 0 || (s > 0 && !a.include?(m))
            if check(d, a + [m], s)
              b += solve(d, len, a + [m])
            end
          end
        }
      end
      b
    end
    
    (D..N).each{|b|
      p [b, solve(D, b).size]
    }
    
    # Dを固定したとき、条件を満たす順列が存在するための最小のN
    (2..5).each{|d|
      n = d
      while solve(d, n).size == 0
        n += 1
      end
      p ''
      p n
      p solve(d, n)
    }
    
[/code]

出力結果  
[3, 0]  
[4, 0]  
[5, 0]  
[6, 0]  
[7, 0]  
[8, 0]  
[9, 2]  
[10, 40]  
[11, 792]  
[12, 15374]  
[13, 281434]  
""  
4  
[[2, 4, 1, 3], [3, 1, 4, 2]]  
""  
9  
[[3, 6, 9, 2, 5, 8, 1, 4, 7], [7, 4, 1, 8, 5, 2, 9, 6, 3]]  
""  
16  
[[4, 8, 12, 16, 3, 7, 11, 15, 2, 6, 10, 14, 1, 5, 9, 13], [13, 9, 5, 1, 14,
10,  
6, 2, 15, 11, 7, 3, 16, 12, 8, 4]]  
""  
25  
[[5, 10, 15, 20, 25, 4, 9, 14, 19, 24, 3, 8, 13, 18, 23, 2, 7, 12, 17, 22, 1,
6,  
11, 16, 21], [21, 16, 11, 6, 1, 22, 17, 12, 7, 2, 23, 18, 13, 8, 3, 24, 19,
14,  
9, 4, 25, 20, 15, 10, 5]]


CC BY-SA 3.0
2015-05-02T10:35:27.893
9770
2016-12-18T06:10:23.517
2016-12-18T06:10:23.517
5363
5363
9766
answer