Here is a more relative way to represent a permutation with the same economical number of bits.

Index vs. offset

Long have programming languages differed on whether indexing should start at 1 or at 0. Dijkstra settled the matter (for himself at least) in his manuscript EWD831, Why numbering should start at zero. Still, languages in the Fortran tradition (Fortran itself, R, Matlab, Julia) used 1-based indexing. My opinion on this, after much reflection, accords with a comment by user ihnorton on Julia’s Discourse:

… [T]he choice comes down to a preference for counting (1-based) versus offsets (0-based).

I would prefer to have this read indexing versus offsets. Unfortunately then my stance will likely please no one. Contrary to Dijkstra I think indexing should start at 1. Contrary to Julia’s conventions, I prefer to work with offsets (for the reasons set out in EWD831) and eschew references to indices. But keeping the distinction in mind has finally made me think it possible for me to work productively in Julia.

Permutations by offsets

For this reason, the previous post’s code is not quite good enough. If possible it should be index-base agnostic. This is quite possible. Instead of recording the image under a transposition, one records the offset by a transposition. This is quite easily done; what is more, it has the great virtue of representing the identity map by all zeroes. Since Julia inspired this, I’ll write it in Julia with the necessary small modifications.

module TinyPermutations

function act(N, start, sigma, x)
    # to offset
    x -= start 
    
    f, nbits, mask = 0, 0, 0
    while f < N
        y = f - (mask&sigma)
        x = x + (x==f)*(y-x) + (x==y)*(f-x)
        sigma >>= nbits
        f += 1
        b = f > mask
        mask += b*(mask+1)
        nbits += b
    end
    
    # back to index
    return x+start
end

export act
end