How to generate all possible test cases of length $n$ for comparison sorts

Question

Comparison sorts only care about the relative order of elements, not their exact values. So if the relative order of two arrays are the same, a comparison sort algorithm will act the same way on those two arrays.

For example, [0, 3, 1, 9, 1] is the same as [-3, 12, 7, 13, 7], since their relative orders are the same.

I want to generate all possible test cases of length $n$ for comparison sorts that all possible relative orders are considered, and no two different test cases have the same relative order.

The number of possible test cases of length $n$ is given by A000670.

Here are all possible test cases of length 0:

[]

Here are all possible test cases of length 1:

[0]

Here are all possible test cases of length 2:

[0, 0]
[0, 1]
[1, 0]

Here are all possible test cases of length 3:

[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[0, 1, 2]
[0, 2, 1]
[1, 0, 0]
[1, 0, 1]
[1, 0, 2]
[1, 1, 0]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]

Is there a generic way rather than brutal force to generate these test cases?

Answer 1

Yes, there is an algorithm to generate all the possible test cases with length equal to $n$ and only them, significantly faster than the naive brute force algorithm would do.

Firstly, let's sort the numbers of each testcase you provided with length equal to 3 in ascending order and list only the different testcases that we get as result.

[0, 0, 0]
[0, 0, 1]
[0, 1, 1]
[0, 1, 2]

There are $4 = 2^2 = 2^{3 - 1}$ results. Note that the first value always has to be zero and while we move to the left within a specific testcase we can keep the previous value or increase it by one. So the number of different sorted testcases of length $n$ is $2^{n - 1}$. You can produce these sorted testcases by using a binary array whose value is initially zero and it's increased by one after each step.

After creating the sorted testcases you would like to have all the permutations of each one of them. Note that the number of permutations of a testcase is lower than $n!$ for all testcases except one (the $[1, 2, 3, \dots, n]$). Also note that the permutations of the different sorted testcases do not overlap. There is a built-in function in C++ which can create these permutations efficiently, named "next_permutation". The algorithm used for its implementation is nicely described on a Stack Exchange accepted answer which you can read here: std::next_permutation Implementation Explanation. I encourage you to read this description of the algorithm.

Bellow I provide you with a C++ implementation of the full algorithm that takes $n$ as input and produces all the different testcases that you want efficiently.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 105  // Assumed maximum value of n

int A[MAXN];  // The binary array used to create the sorted testcases
// Initially A is 0 (every number in it is zero)

vector<int> C;
// A vector that stores current sorted testcase and is used to obtain its permutations

int main()
{
    int n;
    cin >> n;  // Read n
    do
    {
        C.clear();  // Clear the vector C to create a new sorted testcase
        int cnt = 0;
        // cnt counts how many times we have increased the number to be inserted in the testcase
        for (int i = 0; i < n; i++)  // Create the sorted testcase of length n number by number
        {
            if (A[i]) cnt++;  // Binary array at current index shows if we should increase the number
            C.push_back(cnt);  // Put the current number in the end of the current sorted testcase
        }

        // Output all permutations of the current testcase
        do
        {
            for (int i = 0; i < n; i++) cout << C[i] << ' ';
            cout << '\n';
        } while (next_permutation(C.begin(), C.begin() + n));  // Continue while there are unprinted permutations

        // Increase binary array by one
        A[n - 1]++;  // We add one at the position n - 1 (least significant bit)
        int p = n - 1;
        while (p && A[p] == 2)  // We move the carry from right to left
        {
            A[p] = 0;
            A[--p]++;
        }
    } while (!A[0]);  // First number of sorted testcase must be 0, so when it becomes 1 we have finished
    return(0);
}