[aplusbi]

Interestingly enough no one I've interviewed has every suggested lexicographical ordering although I have implemented it that way myself to see how hard it would be (answer: it's kind of hard).

That said, C++'s standard library has a next_permutation function that returns the lexicographical next permutation of a pair of iterators (actually it does it in-place and returns a bool). If a candidate used that I'd allow it (as long as there was some discussion as to how it worked).

I've since stopped asking that question and now stick primarily with the split array question as I think it's less tricky. There's more than one way to solve it and most of the solutions build up on simpler solutions which makes for good discussion. I also don't ask for actual code for that problem unless I get the feeling the candidate will understand the problem better by expressing it in code.

[eropple]

Given that I've been back in C++ mode for the last week, this is exactly what I was considering (using next_permutation). ;)