1

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

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

(より一般的には次のような問題です。
1からNまでのN個の整数で、
 イ)隣り合う2数の差はD以上、1個おいた数との差も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]
の2通りあります。)

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

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]
}

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

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

1
  • とりあえずpermutationは枝刈りが出来ないので自前で並べ替えるべきかと思います。
    – pgrho
    Commented 2015年5月2日 9:29

2 件の回答 2

1

rubyじゃなくC#ですが。

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

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; //数値nは使用済みなので打ち切り
                    }
                    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("]");
            }
        }
    }
}
3
  • 「0...**D-2**個おいた数との差もD以上」ですから、D=3以外のロジックは問題に沿っていないかと。
    – unarist
    Commented 2015年5月2日 10:41
  • コメントアウトされている部分はstring.Join(",", list)で十分かと思います。
    – pgrho
    Commented 2015年5月2日 11:14
  • タイトルの質問ではなく一般解の方のロジックを要求されているとは読めませんでした。 string.Join<int>ではlist[0]が含まれてしまいます。
    – gekka
    Commented 2015年5月4日 1:32
0

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

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)
}

出力結果
[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]]

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。