8698


各桁の数字がその桁の出現回数を表すような数を  
Self-descriptive numberと呼びます。  
（<http://en.wikipedia.org/wiki/Self-descriptive_number>）  
以下のコードで、10桁までのSelf-descriptive numberを  
求めようとしたのですが、  
9桁、10桁のSelf-descriptive numberの算出に時間が  
かかっています。  
もっと高速に求める方法があれば、ご教示ください。

[code]

    N = 10
    (1..N).each{|b|
      (0..b - 1).to_a.repeated_permutation(b){|a|
        if a[0] > 0
          i = b - 1
          flag = true
          while i > -1 && flag
            if a.count(i) == a[i]
              i -= 1
            else
              flag = false
            end
          end
          p a.join.to_i if i == -1
        end
      }
    }
    
[/code]


CC BY-SA 3.0
2015-04-02T11:33:47.377
8696
2015-04-03T15:40:14.177
2015-04-02T12:07:35.713
5363
5363
question
ruby アルゴリズム
10桁までのSelf-descriptive numberの求め方について


各桁の合計が目的の桁数を超える時点で計算を打ち切っています。

[code]

    def sdn(len, x = [])
      a = []
      if x.size == len
        if (0..len - 1).all? {|i| x.count(i) == x[i]}
          a << x.join.to_i
        end
      elsif x.inject(0) {|sum, n| sum + n } <= len
        s = x.size > 0 ? 0 : 1
        (s..len - 1).each { |n|
          a += sdn(len, x + [n])
        }
      end
      a
    end
    
    N = 10
    (1..N).each{|b|
      sdn(b).each {|n| p n}
    }
    
[/code]


CC BY-SA 3.0
2015-04-02T13:34:30.900
8698
2015-04-02T22:17:59.547
2015-04-02T22:17:59.547
3639
3639
8696
answer


（コメントでコードを書くと上手く表示されないので、回答を使っています。）  
h2so5さんのコードを用いて少しばかり高速化しました。

[code]

    def sdn(len, l = 0, m = 0, x = [])
      a = []
      if l == len
        if (0..len - 1).all?{|i| x.count(i) == x[i]}
          a << x.join.to_i
        end
      elsif m <= len
        s = l > 0 ? 0 : 1
        (s..len - 1).each{|n| a += sdn(len, l + 1, m + n, x + [n])}
      end
      a
    end
    
    N = 10
    (1..N).each{|b|
      sdn(b).each{|n| p n}
    }
    
[/code]


CC BY-SA 3.0
2015-04-03T15:20:29.797
8733
2015-04-03T15:40:14.177
2015-04-03T15:40:14.177
5363
5363
8696
answer