3
1
Permutations of a set have a natural order called lexicographic order in which two permutations are compared by comparing the first position at which they differ. For the purposes of this question we're working with base 64 and the order of the digits is
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/
Note that this is not the same order as their ASCII values.
This ordering can be extended naturally to handle subpermutations of a given length.
Task
Write a program, function or named verb which takes as input (via stdin in the case of a program or as an argument otherwise) a 12-character subpermutation of the base-64 alphabet given above, and which produces (respectively to stdout or as the return value) the lexicographically next 12-character subpermutation. If working with typed input you may use strings or character arrays holding the ASCII values of the digits listed above.
Your solution should be relatively efficient; and in particular, it is forbidden to loop through base-64 numbers testing them until you find one which doesn't repeat any digits.
It is only required that your program handle 12-character subpermutations, but you do not need to verify that the input is 12 characters in length; if it handles other lengths too you may wish to mention that in your answer.
If the input is the lexicographically greatest subpermutation, the output should wrap round to the lexicographically smallest subpermutation.
Test cases
Input Output
ABCDEFGHIJKL ABCDEFGHIJKM
ABCDEFGHIJK+ ABCDEFGHIJK/
ABCDEFGHIJK/ ABCDEFGHIJLK
ABCDEFGHIJLK ABCDEFGHIJLM
ABCD/9876542 ABCD/9876543
ABCD/9876543 ABCD/987654+
ABCD/987654+ ABCD/98765+E
ABCD/98765+E ABCD/98765+F
ABCDEF+/9875 ABCDEF+/9876
ABCDEF+/9876 ABCDEF/GHIJK
ABCDEF/GHIJK ABCDEF/GHIJL
ABCDEF/GHIJL ABCDEF/GHIJM
ABCDEFG+/987 ABCDEFG/HIJK
A+/987654321 A/BCDEFGHIJK
/+9876543210 ABCDEFGHIJKL
Updated link to original challenge: http://6ftdan.com/danielpclark/2014/05/03/golf-challenge-unique-base-64-incrementor/
– 6ft Dan – 2014-12-17T10:48:54.863Anyone who wants to submit their code samples can go ahead via a fork & pull request on github
– 6ft Dan – 2014-05-03T10:43:13.957You write
named verb
. You don't writenamed function
, so as written anonymous functions are OK but anonymous verbs are not. Is that an oversight or do you just not like J? – marinus – 2014-05-10T13:54:27.780All of those test cases are correct. But the last one starts with the highest possible adaptation. Why do you start back at the beginning? – 6ft Dan – 2014-05-10T17:47:20.580
It's okay, it's just my sample code wasn't made to handle that edge case. – 6ft Dan – 2014-05-10T18:13:26.960
@marinus I'm not sure what you're referring to. This question has been rewritten by Peter. If you'd like to see the original post you can here http://6ftdan.com/2014/05/03/golf-challenge-unique-base-64-incrementor/
– 6ft Dan – 2014-05-17T03:35:22.830