Does it? I'm seeing two O(n) processes: one to confirm order and the other to confirm permutation of set.

In almost-Lua pseudocode:

   function isOrdered(array, predicate)
      -- zero and one length arrays are trivially ordered
      if len(array) < 2 then return true end
      local ordered = true
      for i = 0, len(array) - 1 do
         ordered = ordered and predicate(array[i], array + 1)
      end
   
      return ordered
   end
   
   function popCount(array)
      local pops = {}
      for item in iterate(array) do
         pops = pops[item] and pops[item] + 1 or 1
      end
   
      return pops
   end

Then you compare the two popcounts, if they're the same and the result is in-order then something made them that way.