Sort Integer Array Ruby

Question

Have the function PermutationStep (num) take the num parameter being passed and return the next number greater than num using the same digits. For example: if num is 123 return 132, if it's 12453 return 12534. If a number has no greater permutations, return -1 (ie. 999)

Here's my code. I'd like to sort an array of large integers in numerical order. Using the regular sort method doesn't give the right order for some numbers. Is there a sort_by structure that I can replace 'sort' with in my code below?

def PermutationStep(num)
    num = num.to_s.split('').map {|i| i.to_i}
    permutations = num.permutation.to_a.sort #<= I want to sort by numerical value here
    permutations.each_with_index do |n, idx|
        if n == num
            if n == permutations[-1]
                return -1
            else
                return permutations[idx+1].join.to_i
            end
        end
    end
end

For example, 11121. When I run the code it gives me 11121.I want the next highest permutation, which should be 12111.

Also, when I try { |a,b| b <=> a }, I also get errors.

Provide a small example of array, and what you execte it to be sorted to. — Yu Hao, May 02 '15 at 04:01
It's unclear what you mean by *doesn't give the right order for some numbers.* What is the right order? What result does `sort` give? — Yu Hao, May 02 '15 at 04:04
Here's the question : Have the function PermutationStep (num) take the num parameter being passed and return the next number greater than num using the same digits. For example: if num is 123 return 132, if it's 12453 return 12534. If a number has no greater permutations, return -1 (ie. 999) — catcher, May 02 '15 at 04:07
Your question as given in your comment is very clear, but you are getting ahead of yourself with the title. You are assuming that it will be necessary to construct an array from the number, but that is not necessarily true. (For example, I can imagine a solution that converts the number to a string and then operates on the string without converting it to an array.) Also, a solution may not involve sorting. It would be better to just state the question (find the next higher number...) and show the code you've tried. — Cary Swoveland, May 02 '15 at 06:55

score 1 · Answer 1 · edited May 23 '17 at 10:27

1

You can pass a block to sort.

 num.permutation.to_a.sort { |x, y| x.to_i <=> y.to_i }

This SO thread may be of some assistance: How does Array#sort work when a block is passed?

edited May 23 '17 at 10:27

Community

1
1

answered May 02 '15 at 04:10

Karl Wilbur

5,898
3
44
54

Thanks, I actually browsed that thread and inputting what you wrote gives an error : `block in PermutationStep': undefined method `to_i' for ["1", "1", "1", "2", "1"]:Array (NoMethodError). – catcher May 02 '15 at 04:14

score 0 · Answer 2 · answered May 02 '15 at 04:41

num.permutation.to_a is an array of arrays, not an array of integers, which causes the result not what you expected.

Actually you don't need to sort since you only need the minimum integer that is bigger than the input.

def PermutationStep(num)
    nums = num.to_s.split('')
    permutations = nums.permutation.map{|a| a.join.to_i}
    permutations.keep_if{|n| n > num}.min || -1
end

puts PermutationStep(11121) # 11211
puts PermutationStep(999)   # -1

score 0 · Answer 3 · answered May 02 '15 at 05:10

Call to_i before your sort the permutations. Once that is done, sort the array an pick the first element greater than your number:

def PermutationStep(num)
  numbers = num.to_s.split('')
  permutations = numbers.permutation.map { |p| p.join.to_i }.sort
  permutations.detect { |p| p > num } || -1
end

Cary Swoveland · Answer 4 · 2015-05-02T20:34:04.990

You don't need to consider permutations of digits to obtain the next higher number.

Consider the number 126531.

Going from right to left, we look for the first decrease in the digits. That would be 2 < 6. Clearly we cannot obtain a higher number by permuting only the digits after the 2, but we can obtain a higher number merely by swapping 2 and 6. This will not be the next higher number, however.

We therefore look for the smallest digit to the right of 2 that is greater than 2, which would be 3. Clearly, the next higher number will begin 13 and will have the remaining digits ordered smallest to largest. Therefore, the next higher number will be 131256.

You can easily see that the next higher number for 123 is 132, and for 12453 is 12534.

The proof that procedure is correct is easily established by induction, first showing that it is correct for numbers with two digits, then assuming it is correct for numbers with n>=2 digits, showing it is correct for numbers with n+1 digits.

It can be easily implemented in code:

def next_highest(n)
  a = n.to_s.reverse.split('').map(&:to_i)
  last = -Float::INFINITY
  x,ndx = a.each_with_index.find { |d,i| res = d<last; last=d; res }
  return nil unless x
  swap_val = a[ndx]
  swap_ndx = (0...ndx).select { |i| a[i] > swap_val }.min_by{ |i| a[i] }
  a[ndx], a[swap_ndx] = a[swap_ndx], swap_val
  a[0...ndx] = a[0...ndx].sort.reverse
  a.join.reverse
end

next_highest(126531)       #=> "131256" 
next_highest(109876543210) #=> "110023456789"

Sort Integer Array Ruby

4 Answers4