Поиск следующего наименьшего номера с такими же цифрами

Question

Я работаю с Ruby и пытаюсь написать код, который будет принимать числовой ввод и возвращать следующее наибольшее число с теми же цифрами.

Я видел этот же вопрос, заданный здесь ранее, но код слишком сильно отличается, чтобы помочь мне решить мою конкретную проблему.

def next_smaller n
  ndigitsarray=n.digits.reverse
  bigdigitsarray=ndigitsarray.sort.reverse
  bigdigitsjoint=bigdigitsarray.join.to_i
    while bigdigitsjoint>n do 
  bigdigitsarray.insert(1, bigdigitsarray.delete_at(0)) 
    end
  return bigdigitsarray.join.to_i
end

Время ожидания кода истекло; Я не уверен, почему это не зацикливается правильно. Любая помощь будет принята с благодарностью!

РЕДАКТИРОВАТЬ - я выяснил, почему существует бесконечный цикл, но я оставлю это пока на тот случай, если у кого-нибудь есть какие-либо предложения по решению более крупной проблемы!

Answer 1

Вы используете цикл while, в котором переменная, используемая в условии while, не изменяется внутри цикла.

Один из вариантов решения проблемы с помощью грубой силы - использование Array # permutation onмассив Integer # digits :

n = 1231
n.digits.permutation.uniq.map { |e| e.join.to_i }.sort.keep_if { |k| k > n }.first
#=> 1312

Используется Array # keep_if , чтобы все числа (k) были больше n.

Возвращает nil, если наибольшего числа нет.

---

Используя Enumerable # section , вы можете увидеть "что внутри":

n.digits.permutation.uniq.map { |e| e.join.to_i }.sort.partition { |k| k > n }
#=> [[1312, 1321, 2113, 2131, 2311, 3112, 3121, 3211], [1123, 1132, 1213, 1231]]

Answer 2

Давайте начнем с создания метода, аргумент которого digits является массивом цифр и который возвращает ("подсчитывающий") хеш, ключи которого являются цифрами 0-9 и значения которого digits.count(d) для каждого ключа d ,

def count_digits(digits)
  digits.each_with_object((0..9).to_a.product([0]).to_h) { |d,h| h[d] += 1 }
end

Например,

digits = 35145.digits
  #=> [5, 4, 1, 5, 3] 
digit_counts = count_digits(digits)
  #=> {0=>0, 1=>1, 2=>0, 3=>1, 4=>1, 5=>2, 6=>0, 7=>0, 8=>0, 9=>0}

(См. Массив # product и Целые # цифры ). Теперь мы можем написать метод, который возвращает желаемый результат.

def next_smallest(n)
  digits = n.digits
  digit_counts = count_digits(digits)
  (n-1).downto(0).find { |m| count_digits(m.digits) == digit_counts }
end

require 'time'

def doit(n)
  t = Time.now
  n = next_smallest(n)
  puts "Elapsed time in seconds = #{(Time.now-t).round(7)}"
  n
end

doit  44444
  # Elapsed time in seconds = 0.2008061
  #=> nil 
doit  35154
  # Elapsed time in seconds = 5.18e-05
  #=> 35145 
doit  35154217464215716524742391453862
  # Elapsed time in seconds = 0.0005618
  #=> 35154217464215716524742391453826 
doit  351542174642157165247423914538623999
  # Elapsed time in seconds = 3.4207082
  #=> 351542174642157165247423914538399962 

Хотя это может быть несколько академично, мы можем добиться большего. Учитывая digits и digit_counts выше, для обновления digits для

n = 35153

мы можем написать (потому что последняя цифра больше нуля):

digits[0] -= 1
digits
  #=> [4, 4, 1, 5, 3] 

Аналогично, после создания глубокой копии digit_counts:

h = digit_counts.transform_values(&:itself)
  #=> {0=>0, 1=>1, 2=>0, 3=>1, 4=>1, 5=>2, 6=>0, 7=>0, 8=>0, 9=>0}

мы можем обновить этот хеш, написав:

d0 = digits.first
  #=> 4 
h[d0] += 1
h[d0+1] -= 1
h #=> {0=>0, 1=>1, 2=>0, 3=>1, 4=>2, 5=>1, 6=>0, 7=>0, 8=>0, 9=>0} 

вместо звонка count_digits. (См. Hash # transform_values ​​). Теперь давайте изменим метод следующим образом.

def next_smallest(n)
  digits = n.digits
  digit_counts = count_digits(digits)
  h = digit_counts.transform_values(&:itself)
  (n-1).downto(10).find do |m|
    d0 = digits.first
    if d0 > 0
      digits[0] -= 1
      h[d0] -= 1
      h[d0-1] += 1
    else
      digits = m.digits
      h = count_digits(digits)
    end
    h == digit_counts
  end
end

doit  44444
  # Elapsed time in seconds = 0.0607323
  #=> nil 
doit  35154
  # Elapsed time in seconds = 0.0001582
  #=> 35145 
doit  35154217464215716524742391453862
  # Elapsed time in seconds = 0.000216
  #=> 35154217464215716524742391453826 
doit  351542174642157165247423914538623999
  # Elapsed time in seconds = 0.5180595
  #=> 351542174642157165247423914538399962 

Дальнейшие улучшения возможны в случае, когда последняя цифра равна нулю (чтобы не вызывать count_digits). Если, например,

n = 2130
digits = n.digits
  #=> [0, 3, 1, 2]
h = count_digits(digits)
  #=> {0=>1, 1=>1, 2=>1, 3=>1, 4=>0, 5=>0, 6=>0, 7=>0, 8=>0, 9=>0}

digits и h можно обновить для n = 2129 следующим образом:

n -= 1
  #=> 2129
d1 = digits[1] 
  #=> 3 
digits
  #=> [9, 2, 1, 2] 
h[0] -= 1
h[9] += 1
h[d1] -= 1
h[d1-1] += 1
h #=> {0=>0, 1=>1, 2=>2, 3=>0, 4=>0, 5=>0, 6=>0, 7=>0, 8=>0, 9=>1} 

Можно сделать что-то подобное, если n = 2100 или 2000, но быстро становится быстрее просто позвонить count_digits,

Answer 3

Если вам не поручено создавать массив чисел самостоятельно, существует метод Array # permutation , позволяющий генерировать все комбинации чисел на основе вашего исходного числа.

Затем, после некоторой очистки и сортировки, вы можете найти индекс своего номера, а затем добавить 1, чтобы найти следующее наибольшее число.

def next_number(i)
  puts "Your number is #{i}"
  permutations = i.to_s.split('').permutation.to_a.map(&:join).map(&:to_i).uniq.sort
  index = (permutations.find_index(i) + 1)

  puts "Next highest is #{permutations[index]}"
end

# Usage
next_number(4357)
next_number(81541)

Предостережения:

• Не указывается, является ли ваш номер самой высокой перестановкой (например, next_number(999))
• Вероятно, не самый быстрый способ сделать это, если это является частью проблемы с кодом