Find the next subpermutation of base-64 digits

Question

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

Answer 1

GolfScript, 115 characters

:I,,0\{26,{65+.32+}%$10,{`}%'+/'++:A,1$-@*\)I<)A@-?+}/1I,,{A,\-*}/\)1$%\I,,{A,\-/\.2$%\2$/@\}%*>A\{1$=\[1$]-\}%\0<+

It passes all the test cases and works also for subpermutations of size other than 12 and for full permutations as well.

Online tester

Annotated Code:

:I                        # save input to variable I

### get the numerical index of the (sub)permutation 
,,0\                      # push 0 (accumulator) and [0 .. <Length I>-1]
{                         # loop over

  ### construct the alphabet A
  26,{65+.32+}%$          # A-Z and a-z
  10,{`}%                 # 0-9
  '+/'++                  # append '+/'
  :A                      # save to variable A

  ,1$-                    # length of alphabet (i.e. 64) minus loop variable
                          # i.e. 64 -> 63 -> 62 -> 61 -> ...
                          # (this is the number of possible characters at
                          # the current position)
  @*                      # multiply the accumulator by this value
  \)I<                    # get anything from the input up to the current character
  )                       # extract the current character of input
  A@-                     # remove anything from the alphabet which was in the rest,
                          # i.e. the already processed chars cannot be used any more
  ?                       # find the index of the current input character
  +                       # add to the accumulator
}/

### calculate the total number of (sub)permutations
1                         # push 1 (accumulator)
I,,{                      # loop for i = 0 .. <Length I>-1
  A,\-                    # length of alphabet minus loop variable
  *                       # multiply to accumulator
}/

### at this point the stack is <Index of input (sub)permutation> 
###   <Total number of (sub)permutations>
\)                        # increment the index (i.e. next (sub)permutation)
1$%                       # warp around for the last possible (sub)permutation
\                         # swap back order

### backwards transformation into the (sub)permutation space
I,,{                      # map for each index [0 .. <Length I>-1]
  A,\-/                   # divide the weight factor by length of alphabet minus 
                          # loop variable
  \.2$%                   # take index % new weight factor
  \2$/                    # and index / new weight factor (result for the map operation)
  @\                      # re-order stack
}%
*>                        # get rid of 0 1 on the stack

### back to the alphabet
A\                        # push the full alphabet under the index array
{                         # map on the index array
  1$=                     # take the i-th element of the alphabet
  \[1$]-\                 # and reduce the alphabet by this characters
}%

\0<                       # transforms the remaining alphabet into an empty string
+                         # make string from array by joining with the empty string

Answer 2

GolfScript, 77 70 characters

Another more direct approach in GolfScript which happens to work in the general case also.

:I{)26,{65+.32+}%$10,{`}%'+/'++:^2$-:S\?).S,<{S[=]+0}*1$!!*}do^1$-+I,<

Also this solution can be tested online.

Answer 3

Ruby: Whittled down to 658 Characters

class B;def initialize(g)@l=12;@b=(("A".."Z").to_a+("a".."z").to_a+("0".."9").to_a+["+","/"]
).each_with_index.map{|x,i|{x=>i}}.inject(:update);@g=g;@[email protected];@[email protected]{|i|
@i[@b.length-i-1]}.join;end;def n;c(@g)?@g:r;end;def c(s);@b[s[-1]][email protected]?(return false
):s==@m?r: f(s,s[-1]) ?s[-1]=f(s,s[-1]):f(s,s[-2])?r: (s[-1]=f(s);f(s,s[-2])?s[-2]=f(s,s[-2]):r)
true;end;def h(s)v=s.split("").map{|x|@b[x]};v.index(v.compact.max)end;def r;@g==@m?@[email protected]{
|j| @i[j]}.join: (v=@g[0..h(@g)-1];c(v);u=@g[h(@g)..-1].length;u.times{v+=f(v)};@g=v);end
def f(s,a=@i[0])(@b[a][email protected]).each{|p|unless !!s[@i[p]];return @i[p]end};false;end;end

Running test cases:

puts "      IN   *******   OUT"
["ABCDEFGHIJKL","ABCDEFGHIJK+","ABCDEFGHIJK/","ABCDEFGHIJLK","ABCD/9876542",
"ABCD/9876543","ABCD/987654+","ABCD/98765+E","ABCDEF+/9875","ABCDEF+/9876",
"ABCDEF/GHIJK","ABCDEF/GHIJL","ABCDEFG+/987","A+/987654321","/+9876543210"
    ].each do |v|
    t = B.new(v.dup)
    puts " #{v}   #{t.n}"
end

Outputs:

      IN   *******   OUT
 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

For the long understandable version of this code see my github post https://github.com/danielpclark/b64challenge

This code was tested with Ruby version 1.9.3. I can only vouch for is version.