11

各桁を並び替えてできる最大の数と
各桁を並び替えてできる最小の数(ただし、最高位は0以外にする)の差が
自身と一致するとき、高橋の数と呼びます。
http://masami.d2.r-cms.jp/blog_detail/blog_id=3&id=6

以下のコードで、9桁までの高橋の数を
求めようとしたのですが、
9桁の高橋の数の算出に何時間も
かかっています。
もっと高速に求める方法があれば、ご教示ください。

def takahashi_number(m)
  (10 ** (m - 1)..10 ** m - 1).each{|n|
    ary = n.to_s.split('').map(&:to_i)
    min_ary = ary.sort
    max = min_ary.reverse.join.to_i
    # 最高位を0以外にする←カプレカ数との違い
    i = 0
    while min_ary[i] == 0
      i += 1
    end
    min_ary[0], min_ary[i] = min_ary[i], min_ary[0]
    min = min_ary.join.to_i
    p [m, n] if n == max - min 
  }
end

(2..9).each{|m| takahashi_number(m)}

出力結果
[3, 495]
[4, 6174]
[6, 549945]
[6, 631764]
[6, 660852]
[8, 63317664]
[8, 66308652]
[9, 554999445]
[9, 864197532]

(追記)
(どの言語を用いるにせよ)今のところ、高橋の数は9の倍数であることと
yoh2さんのアイデアを用いていたコードが一番速いものと思われます。
このRuby版のコードを作ったので、回答に載せました。
皆様の参考になれば幸いです。

0

5 件の回答 5

8
+100

ある数について、それぞれ高橋の数か? と判定していくのではなく、各桁について、ある数が何回出現したかという出現数の組から、その組は高橋の数を構成できるか、という判定をしていけば、かなり数を減らせます。
この方法なら、完全に力技で判定しても、n桁での組み合わせは、C(9 + n, 9) 通り。9桁なら 48,620 通りしかありません。

判定の手順は以下の通り。

  1. 出現数の組で構成できる最小数を求める。
  2. 出現数の組で構成できる最大数を求める。
  3. 2 - 1 を求め、その各桁について出現数を求める。
  4. 3 の結果が、最初の出現数の組と一致しているなら、その出現数の組に対応する高橋の数は 2 - 1。一致していなければ、その出現数の組に対応する高橋の数はない。

以下ふたつばかり例を。
count[n] は、その数における n の出現数です。

例1

  • 0, 3, 8, 7 が一回ずつ出現する場合、conut = [1, 0, 0, 1, 0, 0, 0, 1, 1, 0]
  • ここから構成できる最小数: 3078
  • ここから構成できる最大数: 8730
  • 差は 5652 で、各桁を数えた結果 [0, 0, 1, 0, 0, 2, 1, 0, 0, 0]count なので、この出現数の組では高橋の数は構成できない。

例2

  • 1, 4, 6, 7 が一回ずつ出現する場合、conut = [0, 1, 0, 0, 1, 0, 1, 1, 0, 0]
  • ここから構成できる最小数: 1467
  • ここから構成できる最大数: 7641
  • 差は 6174 で、各桁を数た結果 [0, 1, 0, 0, 1, 0, 1, 1, 0, 0] = count なので、6174は高橋の数。

ruby はできないのですが、面白そうなので C で 1〜18 桁の高橋の数を求めるプログラムを組んでみました
このプログラムを使ったところ、 Core i5 2520M で5秒程度で結果を求めることができました。
既出の枝刈りを行えば、もっと速くできるかもしれません。

高橋の数は 9 の倍数であるという性質を利用した枝刈りを入れてみました。その結果、1〜18桁すべてを列挙するのに 0.5 秒程度まで縮まりました。

1
  • gistに載せたプログラム、2015-04-19 03:19 頃バグ修正しました。修正前は9桁までしか正しく求められませんので、修正前を参照した方はご注意を。
    – yoh2
    Commented 2015年4月18日 18:21
3

1.アルゴリズムは元のままで以下の修正を行ったものです。
 1)10 ** (m - 1) + 8 から 9 * 10 ** (m - 1) - 1 までの9の倍数から探す。
   (根拠)
   各桁を並び替えてできる最大の数を
   Σ a * 10 ** i
   とする。
   各桁を並び替えてできる最小の数は
   Σ a * 10 ** σ(i)
   となる。
   よって高橋の数は
   Σ a * (10 ** i - 10 ** σ(i))
   となる。10 ** i - 10 ** σ(i)は9の倍数なので、
   高橋の数は9の倍数。
 2)わざわざ整数の配列にする必要はなく、文字列の配列で良かった。

def takahashi_number(m)
  (10 ** (m - 1) + 8).step(9 * 10 ** (m - 1) - 1, 9){|n|
    ary = n.to_s.split('')
    min_ary = ary.sort
    max = min_ary.reverse.join.to_i
    # 最高位を0以外にする←カプレカ数との違い
    i = 0
    while min_ary[i] == '0'
      i += 1
    end
    min_ary[0], min_ary[i] = min_ary[i], min_ary[0]
    min = min_ary.join.to_i
    p [m, n] if n == max - min 
  }
end

(2..9).each{|m| takahashi_number(m)}

2.高橋の数は9の倍数であることとyoh2さんのアイデアを用いて
  改良を行ったものです。←すごく速くなりました。

def takahashi_number(m)
  numbers = (0..9).to_a
  numbers.repeated_combination(m){|c_ary|
    # 後述のnが9の倍数ということはc_aryの和も9の倍数
    if c_ary.inject(:+) % 9 == 0
      min_ary = c_ary.clone
      max = min_ary.reverse.join.to_i
      # 最高位を0以外にする←カプレカ数との違い
      i = 0
      while min_ary[i] == 0
        i += 1
      end
      min_ary[0], min_ary[i] = min_ary[i], min_ary[0]
      min = min_ary.join.to_i
      n = max - min
      p [m, c_ary, n] if c_ary == n.to_s.split('').map(&:to_i).sort
    end
  }
end

(2..9).each{|m| takahashi_number(m)}

出力結果
[3, [4, 5, 9], 495]
[4, [1, 4, 6, 7], 6174]
[6, [0, 2, 5, 6, 6, 8], 660852]
[6, [1, 3, 4, 6, 6, 7], 631764]
[6, [4, 4, 5, 5, 9, 9], 549945]
[8, [0, 2, 3, 5, 6, 6, 6, 8], 66308652]
[8, [1, 3, 3, 4, 6, 6, 6, 7], 63317664]
[9, [1, 2, 3, 4, 5, 6, 7, 8, 9], 864197532]
[9, [4, 4, 4, 5, 5, 5, 9, 9, 9], 554999445]

0
2

@yoh2 さんと同じアイディアですが、折角書いたので JavaScript版/C++版として投稿しておきます。
9の倍数の枝刈りは入れていません。

考え方

  • 高橋の数を t (n桁) とします。
  • 各桁を並び替えてできる最大の数を M = [Mn-1,…,M1,M0]10進数 = Σi=0n-1 Mi 10i とします
  • 各桁を並び替えてできる最小の数を m とします

この時、高橋の数は t = M - m を用いて M から求められますので、M についてのループを考えます。t の候補は (枝刈りなどなしで) 大体 10n 個程度になりますが、最大の数 M は各桁の数字が必ず降順になっているので候補の数は大幅に少なくなります (10Hn = 9+nC9 通り)。

プログラムの流れは、M の候補を列挙しつつ、各 M について以下を行います。

  1. M から t を計算
  2. t の各桁を並び替えて M に一致すれば採用 (t を出力)

M を各桁の数字の入った配列で表現する事にします。M に "0" が α 個含まれる時、t を M の各桁 Mi で表す事を考えます:
 M = [Mn-1,…,Mα,0,…,0]10進数,
 m = [Mα,0,…,0,Mα+1,…,Mn-1]10進数
  = [0,…,0,Mα,…,Mn-1]10進数 + Mα(10n-1 - 10n-1-α)
  = Σi=0n-1 Mi 10n-1-i + Mα(10n-1 - 10n-1-α),
 t = Σi=0n-1 Mi diffi - Mα(10n-1 - 10n-1-α), where diffi = 10i - 10n-1-i.

JavaScript 版

function get_takahashi_numbers(buff,ndigit){
  var difference=[];
  for(var i=0;i<ndigit;i++)
    difference[i]=Math.pow(10,i)-Math.pow(10,ndigit-1-i);

  function checkMax(M){
    var t=0,nzero=0;
    for(var i=0;i<ndigit;i++){
      if(M[i]==0)nzero++;
      t+=M[i]*difference[i];
    }

    if(nzero==ndigit)
      return;
    else if(nzero>0)
      t-=M[nzero]*(Math.pow(10,ndigit-1)-Math.pow(10,ndigit-1-nzero));

    var M2=(t+"").split("").sort();
    for(var i=0;i<ndigit;i++)
      if(M2[i]!=M[i])return;

    buff.push(t);
  }
  function enumerateMax(M,dmin,k,callback){
    if(k==ndigit){
      callback(M);
    }else for(var d=dmin;d<=9;d++){
      enumerateMax(M,M[k]=d,k+1,callback);
    }
  }
  enumerateMax([],0,0,checkMax);
}

var result=[];
for(var n=0;n<=9;n++)
  get_takahashi_numbers(result,n);
for(var i=0;i<result.length;i++)
  document.write("<p>["+(result[i]+"").length+", "+result[i]+"]</p>");

C++版
(C or C++ でも OK というコメントが一時表示されていた様な気がしたので C++ に翻訳したのですが、今見てもその様なコメントはないですね…)

#include <cstdio>
#include <cstring>
#define __STDC_FORMAT_MACROS
#include <cinttypes>
#include <cstdint>
#include <algorithm>

template<typename F>
void enumerateMax(char* M,int idigit,int ndigit,char dmin,F const& proc){
  if(idigit==ndigit){
    if(dmin!='0')proc(M);
  }else{
    for(char d=dmin;d<='9';d++)
      enumerateMax(M,idigit+1,ndigit,M[idigit]=d,proc);
  }
}

int main(){
  // pow10[i] = 10^n
  std::int64_t pow10[19]={1};
  for(int i=1;i<sizeof pow10/sizeof *pow10;i++)
    pow10[i]=pow10[i-1]*10;

  const int maxdigits=18;
  char M[maxdigits];
  std::int64_t differences[maxdigits];

  for(int n=1;n<=maxdigits;n++){
    // diff_i = 10^i - 10^{n-1-i}
    for(int i=0;i<n;i++)
      differences[i]=pow10[i]-pow10[n-1-i];

    enumerateMax(M,0,n,'0',[&](char* _max){
      std::int64_t takahashi=0;

      int nzero=0;
      for(int i=0;i<n;i++){
        int const digit=_max[i]-'0';
        if(digit==0)nzero++;
        takahashi+=digit*differences[i];
      }

      if(nzero)
        takahashi-=(_max[nzero]-'0')*(pow10[n-1]-pow10[n-1-nzero]);

      if(takahashi<pow10[n-1])return;

      char _max2[22];
      std::sprintf(_max2,"%" PRId64,takahashi);
      std::sort(_max2,_max2+n);
      if(std::memcmp(_max,_max2,n)==0)
        std::printf("[%d, %" PRId64 "]\n",n,takahashi);
    });
  }

  return 0;
}
1
  • 「その様なコメントはない」 タグが追加されて削除されたようです。
    – BLUEPIXY
    Commented 2015年4月18日 20:14
1

最小値・最大値の計算で毎回全ての桁をソートする必要はないと思います。

例えば418の最小・最大は148841ということが分かっていれば、4185についても挿入ソートで14588541を求めることが出来るはずです。最小値では0が先頭に来ないようにする必要がありますが。
なので先頭x桁の最大値・最小値を保持しておいて適宜更新するようにすれば計算量は減らせると思います。

また途中桁の計算結果から最終的な最大・最小の範囲も制限されると思います。例えば最大値の上限は99…9、最小値の下限は10…0なので差が9で始まることはないはずです。なので9で始まる場合は該当しないというような枝刈りが出来ると思います。

1
  • 調べる範囲は(10 ** (m - 1)..10 ** m - 1)でなく、(10 ** (m - 1)..9 * 10 ** (m - 1) - 1)とすべきでした。
    – TOM
    Commented 2015年4月18日 11:55
1

基本的な流れは同じですが、文字列への変換・リバース・ソートの部分のために単純な数値の配列を使用します。結合して数値に戻すことはしません。
ソートは値が0-9の数字と決まっているのでカウントソートにします。
ソートの部分でかなりの時間の短縮ができるはずです。
このC言語版でウチのマシンで概ね35秒くらい(最適化オプション指定で20秒くらい)で完了しました。

#include <stdio.h>

int match(int n){
    int max[9], min[9], num[9], len;
    int i, j, x, digit, temp[10] = {0};

    for(len = 0, x = n; x ; x /= 10, ++len){
        num[len] = digit = x % 10;//切り分けsplit
        ++temp[digit];//各数字のカウント
    }
    for(i=0, digit = 9; digit >= 0; --digit){
        for(j = 0; j < temp[digit]; ++j)
            max[i++] = digit;//max へのセット
    }

    for(i = 1; temp[i]==0; ++i)
        ;
    digit = i;
    for(i = j = 0; j < temp[digit]; ++j)
        min[i++] = digit;//minの最初の数値
    for(j = 0; j < temp[0]; ++j)
        min[i++] = 0;//0を入れる
    for(++digit; digit < 10; ++digit){
        for(j = 0; j < temp[digit]; ++j)
            min[i++] = digit;//残りを入れる
    }
    for(i = len-1, j = 0; j < len; ++j, --i){
        x = max[i] - min[i];//一桁の引き算
        if(x < 0){ //借りが生じたか?
            x += 10;
            --max[i-1];//上位の桁から借りる、この場合ボローの繰り越しは必要無い
        }
        if(x != num[j])//判定
            return 0;
    }
    return 1;
}

typedef struct pair {
    int first, second;
} Range;

int main(void){
    Range range[] = {
        {108,             900},
        {1008,           9000},
        {10008,         90000},
        {100008,       900000},
        {1000008,     9000000},
        {10000008,   90000000},
        {100000008, 900000000}
    };
    int i, j;
    for(i = 0; i < 7; ++i)
        for(j = range[i].first; j < range[i].second; j += 9)
        if(match(j))
            printf("%d\n", j);
    return 0;
}
2
  • pgrhoさんの指摘で気づいたことですが、rangeは{108, 899}, … ,{100000008, 899999999}で十分だと思います。
    – TOM
    Commented 2015年4月18日 17:19
  • なるほど。 そのように修正しました。 さらに数秒短縮できました。
    – BLUEPIXY
    Commented 2015年4月18日 17:28

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

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