Suche nach der nächstgrößeren Ganzzahl

Question

Ich möchte die nächstgrößere Ganzzahl aus ganzen Zahlen finden, die aus den Zeichen in einer bestimmten Ganzzahl bestehen. Wenn die angegebene Ganzzahl die größte ist, geben Sie -1 zurück.

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 

Dieser Code funktioniert. Ich weiß nicht, wie ich es leichter machen kann. Im Moment dauert es ewig, um zu rennen. Wo würdest du anfangen?

Answer 1

Sie können Rekursion verwenden, um eine hocheffiziente Prozedur zu erhalten.

-Code

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 

Beispiele

(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 

dieser Berechnungen Alle nahm einen kleinen Bruchteil einer Sekunde.

Erklärung

zur Verbesserung der Code, der bereits arbeitet http://codereview.stackexchange.com (sofern es die Zeit erlaubt ... werden)