5
\$\begingroup\$

Was looking at this question (which I initially misunderstood completely), to which Peter Taylor posted a good answer outlining a much better algorithm.

For kicks, I implemented it in Ruby, but I feel like it can be done more cleanly:

def next_greater_permutation(integer)
  digits = integer.to_s.chars.map(&:to_i)               # get digits
  k = digits.each_cons(2).to_a.rindex { |a, b| a < b }  # find k
  return integer if k.nil?                              # no k found, return the input unaltered
  head, tail = digits[0..k], digits[k+1..-1]            # split digits into two arrays
  l = tail.rindex { |n| n > head.last }                 # find l (local to the tail)
  head[k], tail[l] = tail[l], head[k]                   # swap the two values
  (head + tail.reverse).join.to_i                       # glue back together, return
end

(The k and l names are in keeping with the names used in the algorithm; usually I'd use more verbose names.)

It's not super complex or anything, but I just feel like there's a bit too much going on. I'm used to array-manipulation in Ruby being a matter of finding the right methods and chaining them, rather than fiddling with indices. Just feels like I'm missing some obvious shortcut.

To wit, the algorithm (quoted from Wikipedia) is:

  1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
  2. Find the largest index l greater than k such that a[k] < a[l].
  3. Swap the value of a[k] with that of a[l].
  4. Reverse the sequence from a[k + 1] up to and including the final element a[n].
\$\endgroup\$
  • \$\begingroup\$ Ruby 2.3.1 (for certain) has a function, Enumerable.slice_when that looks like it could be used for getting head and tail, and maybe l too. I'd play around with it, but I don't have that version installed on this computer. \$\endgroup\$ – Zack Oct 11 '16 at 18:36
  • \$\begingroup\$ @Zack I actually did try using slice_when at some point. However, it'll slice anywhere the conditions are met, giving you N arrays. You could do *head, tail = x.slice_when... but then you also have to flatten head afterward, and... eh', just seemed like not much was gained, as far as I could tell. I do wish for a slice_at or split_at kinda thing, just to clean things up a bit for a known index \$\endgroup\$ – Flambino Oct 11 '16 at 20:03
  • \$\begingroup\$ I'm out of ideas then. You could try writing it entirely in an imperative style and see if anything jumps out at you \$\endgroup\$ – Zack Oct 11 '16 at 20:07
  • \$\begingroup\$ Flambino, you are right that working with indexes instead of stream of values is usually a code smell. In this particular case, however, working with indexes seems more declarative. I'd only change the in-place update head[k], tail[l] = tail[l], head[k] to something functional and be that would be it. Are you sure you want to return the same number if there is no bigger permutation, though? A nil seems more fitting. \$\endgroup\$ – tokland Oct 11 '16 at 20:28
  • \$\begingroup\$ @tokland Good point about returning nil; makes more sense with the method's name (was a better fit when I first wrote it). As for the in-place swap, it seemed the most direct route (and the array's local, so no external side-effects), but I'd love to see other suggestions :) \$\endgroup\$ – Flambino Oct 11 '16 at 20:35
1
\$\begingroup\$

This is a great question with deep implications imo. And I think the correct answer is that there is no good answer.

I managed some minor cleanup which is almost not worth posting:

def next_greater_permutation(integer)
  digits = integer.to_s.chars
  k = digits.each_cons(2).to_a.rindex { |a, b| a < b }
  return integer if k.nil?                           

  l = digits.rindex { |n| digits[k] < n }           
  digits[k], digits[l] = digits[l], digits[k]      
  [digits[0..k], digits[k+1..-1].reverse].join.to_i
end

But when you say "I'm used to array-manipulation in Ruby being a matter of finding the right methods and chaining them," what you are saying is that ruby code -- and this applies to functional code in general -- looks pleasing and natural when the problem you're solving can be modeled as a series of successive data transformations.

In the case of an array, that means a series of transformations of the array which require no additional temporary variables. When you do need temporary variables, the solution starts to get uglier, even if you try to paper over the fact by hiding your variables in the accumulator of the faux-functional method reduce (or something similar).

From this perspective, I think it becomes clear that the algorithm you're implementing is by nature procedural, and there is no way around those k and l temporary variables (certainly not k). In fact, I suspect (but don't know) that there might even be a way to make this intuition rigorous.

Of course, you could imagine a standard library (or a monkey patched one) which provided additional array methods like swap(i,j) and reverse_after(i) that would make this solution prettier. But again, you'd still be stuck with what is truly making you uneasy imo -- the need of k and l.

So, my non-answer to your question is that, at bottom, this question is unanswerable -- that is, minor improvements may be possible, but not a fundamental one.

UPDATE

Thinking about this more, I just wanted to elaborate on what I see as the larger problem posed by this question -- that is, what categories of problem cannot be solved cleanly with a functional pipeline.

I think it's worth pointing out that this problem can be solved with a pipeline, although probably not with the built-in ruby functional constructs. Essentially, you need to transform the data, and then pass both the result of that transformation and the original data down the pipe, to functions of more than one argument. In the J language, forks and hooks provide this mechanism in an elegant way. But even then, you'd still be passing your k value down multiple steps of the pipe, and at that point you've simply implemented a local temporary variable through a pipe. And I don't think you've gained anything in readability -- in fact, you've probably lost something. Indeed, you can view the lines of a procedural program as steps in a pipe each of which have access to the results of every calculation above them.

So I think the general lesson here may be something like: If you need to use the result of a calculation in multiple places in a sequence of functions, then a procedural solution is probably going to be less verbose and more readable than a purely functional one, unless you're using a language like J with special constructs for this -- and even then it might be a draw.

The only question that remains would be: Is there some clever equivalent version of this algorithm which wouldn't require the use of temporary variables or their equivalent? I'd still guess the answer is no.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.