There is no such thing as randomness of a sequence (or of a permutation, or of a string, etc.). There is only randomness of a process for choosing sequences (permutations, strings, etc.), which is intrinsically not something you can test by looking at its outputs.
What you can do is write a decision procedure that will, with some probability, return a different answer depending on which of two different random processes generated the outputs. Of course, the probability distribution on its decisions depend on the probability distribution on its inputs! Here's a couple examples:
-
What this illustrates is that the utility of any distinguishing test depends entirely on the distributions you are trying to distinguish. You cannot simply ask: ‘Is this sequence random?’ or ‘Is this sequence independent uniform Bernoulli trials?’
- Input data: String of eight Smarties in unique colors.
- Procedure:
- If a mauve candy appears before a yellow candy, return 0; otherwise return 1.
Probability distributions:
We hypothesize that a factory, which produces the colors in alphabetical order [blue brown green mauve orange pink red yellow], has not been randomly permuting them with all possible permutations—specifically, it has been permuting the first four as a group, and the last four as a group, but never interchanging anything in the first group with anything in the last group. So we have:
- A3: Smarties with uniform permutation
- B3: Smarties with blue/brown/green/mauve permuted uniformly, followed by orange/pink/red/yellow permuted uniformly.
Under distribution A3, there is a 50% chance of mauve appearing before yellow, and a 50% chance of yellow appearing before mauve. So the procedure returns 0 and 1 with equal probability, 50%.
Under distribution B3, there is a 100% chance of mauve appearing before yellow, and a 0% chance of yellow appearing before mauve. So the procedure returns 0 with 100% probability, and returns 1 with 0% probability.
In cryptography, we usually work with distributions that are so similar that any procedure to distinguish them has almost the same probability of returning 1 for both distributions—so that even procedures that were designed by extremely smart cryptanalysts with knowledge of how your system works can't tell the distributions apart with more than negligible probability. In other words, if the NIST tests can break your system, then it can be broken by someone so stupid that they don't even know they're trying to break your system—and I mean that quite literally: a programmer at NIST, who is not stupid in the general sense but specifically lacks knowledge of your system, was able to devise a test years ago that would break it before you even designed your system.
So, we can't help you find a test for randomness of your permuted sequences—that is a nonsensical question, on its face. It's also not really interesting to try to psychoanalyze you to guess what processes might have generated your permutations and then derive tests based on those. But if you can describe the candidate processes, or describe a process and compare it to the uniform distribution on permutations, maybe then there is a test that will distinguish them.
For example, maybe you're trying to permute $\{0,1,2,\dots,2^{128} - 1\}$, and your permutation is chosen by (a) picking a 256-bit key $k$ uniformly at random, and then (b) selecting $\operatorname{AES}_k$ as the permutation. In that case, you have no hope of distinguishing it from a uniform random permutation of $\{0,1,2,\dots,2^{128} - 1\}$ (barring side channel attacks).