私は与えられた整数の文字からなる整数のうち、次に大きい整数を探したいと思っています。与えられた整数が最大の場合は、-1を返します。次の最大整数の検索
def next_bigger(n)
perm = n.to_s.chars.sort.permutation.to_a.uniq
to_return = []
perm.each do |x|
to_return.push(x.join)
end
tracker = to_return.find_index(n.to_s)
if to_return[tracker + 1] != nil
return to_return[tracker + 1].to_i
else
-1
end
end
このコードは機能します。私はそれをより軽くする方法を知らない。今すぐ実行するには永遠にかかる。どこから始めるのですか？
非常に効率的な手順を得るために再帰を使用できます。
コード
def next_largest(n)
nxt = nl(n.to_s.chars.map(&:to_i))
return nil if nxt.nil?
nxt.map(&:to_s).join.to_i
end
def nl(arr, remaining_digits=arr.sort)
if arr.size == 1
return (remaining_digits.first > arr.first) ? remaining_digits : nil
end
first = arr.first
remaining_arr = arr.drop(1)
remaining_digits.each_index do |i|
d = remaining_digits[i]
rest =
case i
when 0 then remaining_digits.drop(1)
when remaining_digits.size-1 then remaining_digits[0..-2]
else [*remaining_digits[0..i-1], *remaining_digits[i+1..-1]]
end
return [d, *rest] if d > first
if d == first
arr = nl(remaining_arr, rest)
return [d, *arr] if arr
end
end
nil
end
例
(1..10000).to_a.sample(10).sort.each do |n|
v = next_largest(n)
print "%4d => " % n
puts(v ? ("%4d" % v) : "No next number")
end
647 => 674
1137 => 1173
4010 => 4100
4357 => 4375
6542 => No next number
6832 => 8236
6943 => 9346
7030 => 7300
8384 => 8438
9125 => 9152
next_largest(613_492_385_167)
#=> 613492385176
これらの計算のすべては、第二のごく一部を取りました。
説明
（時間の許すとして提供される...）
すでにhttp://codereview.stackexchange.comで動作するコードを改善するための適切な場所。 –
私は@マークに同意しません。この質問の本質は、ブルートフォースの使用よりも優れたアルゴリズムがあるかどうかです。そのように見れば、それだけでなく、それはかなり興味深い質問です。 Christopher、あなたの質問を変更することを検討してください。コードを削除し、番号の桁の順列を列挙して解決しようとしていると言っていますが、それは時間がかかりすぎて、問題を解決する方法がより効率的かどうかを尋ねます。また、最初の行で "characters"を "digits"に変更し、あまりにも小さい例番号と望ましい戻り値を与えます。 –
私はそれは間違いなくここに話題になる可能性があると認めます。しかし、私はこれがcodereviewでもっと話題になっていると主張しています。これは本質的に効率的な質問のためのリファクタリングです。一方、ここではより多くの眼球が得られます。 –