Test the randomness of a random permutations, that was generated without Fisher-Yates?

Question

Overview of the problem

Before this gets immediately flagged as duplicate, I'm not interested in testing the Fisher-Yates shuffle for randomness, since this can simply be done by testing the underlying RNG. I'm interested in testing the quality of any function that generates random permutations.

How can one test the quality of a random shuffle function, of which I don't know the underlying implementation?

My specific problem

To be a bit more specific to my conundrum, I'm currently trying to implement a 64 bit version of a permutation algorithm from this blog post.

TLDR: You can use a hash function, that is invertible for a given power-of-two sized domain, to generate random permutations, by rounding up the range to the next power-of-two and excluding and indexes generated that are smaller than the range.

A hacky solution

I came up with a hacky solution, but I'm not sure if there are better ones and how to calculate the bias introduced by this solution:

One thing that comes to mind when evaluating random permutations is what happens if we shuffle an array that contains consecutive integers and just use the first index as a randomly generated number, which can now be tested for randomness using test suites like PractRand.

This approach has an obvious problem though, since we are interested in the correlation of a single permutation and not between different permutations, since e.g. in the algorithms from above the initial index is always properly random.

Now the next idea would be to use the first k indexes as random numbers, but this also has a problem since once a number is generated it can't occur again.

This can be elevated to an extent, by storing the consecutive integers multiple times each in the array. So every integer in [0,n] is stored m times in the array and k shuffled integers are used for testing. With an increased m the bias in getting repeated integers would go down, and thus this is a theoretically useable solution.

This would require a huge amount of memory though, but fortunately the algorithm I'm interested in testing generates one random index at a time and thus this can be done quite efficiently, by using the mod n of the indexes generated.

Edit: To clarify what I'm talking about on a smaller scale: Say I had an array that contains m zeros and m ones (so n=1). I now shuffle the array and write the first k zeros and ones as bits to a testsuite like PractRand and then repeat this process. With a very large m (e.g. 2^50) and a smaller k (e.g. 2^8) the bias of repetitions should be so small that it's negligible.

I don't know though what values for k, n and m to choose and what the corresponding bias is.

Questions

1. Are there other methods of testing a function than shuffles an array for randomness, without knowing the underlying implementation of the function?
2. Is there anything wrong with my proposed method?
3. How do I calculate the bias my method introduces for given values of k, n and m?

Answer 1

One thing that comes to mind when evaluating random permutations is what happens if we shuffle an array that contains consecutive integers and just use the first index as a randomly generated number, which can now be tested for randomness using test suites like PractRand.

No, you can't do that, but almost. A pseudo/truly random sequence has multiple same values, repetitions and +/- runs of digits. Your solely incremental sequence will easily fail the test even when perfectly permuted, probably even fail something as simple as ent.

You test the shuffle algorithm by inference.

1. Generate a large file from something like /dev/urandom or the windows equivalent.

2. Sort it into order, either rising or falling.

3. Then permute that.

4. Then test for randomness.

The test hypothesis is that since the original sequence was cryptographically random with the correct $\chi^2$ distribution, a proper shuffle will not make it worse. And it will space out the values into random positions. So the standard randomness tests should then pass it.