Find the next subpermutation of base-64 digits
GolfScript, 115 characters
:I,,0\{26,{65+.32+}%$10,{`}%'+/'++:A,1$-@*\)I&lt;)A@-?+}/1I,,{A,\-*}/\)1$%\I,,{A,\-/\.2$%\2$/@\}%*&gt;A\{1$=\[1$]-\}%\0&lt;+

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 .. &lt;Length I&gt;-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 -&gt; 63 -&gt; 62 -&gt; 61 -&gt; ...
                          # (this is the number of possible characters at
                          # the current position)
  @*                      # multiply the accumulator by this value
  \)I&lt;                    # 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 .. &lt;Length I&gt;-1
  A,\-                    # length of alphabet minus loop variable
  *                       # multiply to accumulator
}/

### at this point the stack is &lt;Index of input (sub)permutation&gt; 
###   &lt;Total number of (sub)permutations&gt;
\)                        # 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 .. &lt;Length I&gt;-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
}%
*&gt;                        # 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&lt;                       # transforms the remaining alphabet into an empty string
+                         # make string from array by joining with the empty string