9292


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

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

[code]

    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)}
    
[/code]

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

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


CC BY-SA 3.0
2015-04-18T09:54:45.993
9285
2015-05-15T23:34:24.830
2015-05-15T23:34:24.830
5363
5363
question
ruby c++ c アルゴリズム
高橋の数の算出について


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

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

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


CC BY-SA 3.0
2015-04-18T11:37:07.590
9286
2015-04-18T12:56:05.740
2015-04-18T12:56:05.740
5750
5750
9285
answer


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

[code]

    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)}
    
[/code]

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

[code]

    def takahashi_number(m)
      numbers = (0..9).to_a
      numbers.repeated_combination(m){|c_ary|
        # 後述のnが９の倍数ということはc_aryの和も９の倍数
        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)}
    
[/code]

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


CC BY-SA 3.0
2015-04-18T13:19:51.013
9289
2015-04-18T20:06:45.550
2015-04-18T20:06:45.550
5363
5363
9285
answer


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

[code]

    #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;//０を入れる
        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;
    }
    
[/code]


CC BY-SA 3.0
2015-04-18T17:11:42.327
9291
2015-04-18T17:39:20.677
2015-04-18T17:39:20.677
5044
5044
9285
answer


ある数について、それぞれ高橋の数か？
と判定していくのではなく、各桁について、ある数が何回出現したかという出現数の組から、その組は高橋の数を構成できるか、という判定をしていけば、かなり数を減らせます。  
この方法なら、完全に力技で判定しても、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
桁の高橋の数を求める[プログラムを組んでみました](https://gist.github.com/yoh2/970839faf5819326d8f4)。  
このプログラムを使ったところ、 Core i5 2520M で5秒程度で結果を求めることができました。  
既出の枝刈りを行えば、もっと速くできるかもしれません。

→ [高橋の数は 9
の倍数であるという性質を利用した枝刈りを入れてみました](https://gist.github.com/yoh2/970839faf5819326d8f4#file-
takahashi_num_opt_1_18-c)。その結果、1〜18桁すべてを列挙するのに 0.5 秒程度まで縮まりました。


CC BY-SA 3.0
2015-04-18T17:52:00.703
9292
2015-04-18T19:04:12.317
2015-04-18T19:04:12.317
7831
7831
9285
answer


@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 版**  

[code]

    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>");
[/code]

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

[code]

    #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;
    }
    
[/code]


CC BY-SA 3.0
2015-04-18T19:49:21.827
9293
2015-04-18T19:57:16.073
2015-04-18T19:57:16.073
5300
5300
9285
answer