[Math] Number of distinct Arrays formed from swapping pairs

combinatoricspermutations

Given an Array $A$ as a permutation of first $N$ natural numbers and an integer $m$, how can we find the number of distinct arrays that we can generate from $A$ by performing exactly $m$ swap operations.
Eg : $A =\{1,2,3\}$ and $m=1$
Then possible resulting arrays can be $\{2,1,3\}, \{1,3,2\}, \{3,2,1\}$. So answer is $3$.

Best Answer

Duplicate but also unanswered

Here's a piece of c++ code i just wrote to help find and answer to this.

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


int main() {
    int n, m;
    cout << "Enter number of distinct numbers in array: ";
    cin >> n;
    vector<int> startNumbers;
    startNumbers.reserve(n);
    for (int i = 1; i < n + 1; ++i)
        startNumbers.push_back(i);
    vector<vector<int>> permutations;
    permutations.push_back(startNumbers);
    cout << "Enter number of swaps: ";
    cin >> m;
    for (int i = 0; i < m; ++i){
        vector<vector<int>> newPermutations;
        newPermutations.reserve(n*permutations.size());
        for (auto vec : permutations){
            for (int j = 0; j < n; ++j){
                for (int k = 0; k < n; ++k){
                    if (j != k){
                        auto tempVec = vec;
                        iter_swap(tempVec.begin() + j, tempVec.begin() + k);
                        newPermutations.push_back(tempVec);
                    }

                }

            }
        }
        sort(newPermutations.begin(), newPermutations.end());
        newPermutations.erase(unique(newPermutations.begin(), newPermutations.end()), newPermutations.end());
        newPermutations.shrink_to_fit();
        permutations = newPermutations;
    }
    cout <<"Number of distinct arrays: " << permutations.size() <<"\n";
    cout << "Distinct arrays: ";
    for (auto& p : permutations){
        cout << "[ ";
        for (auto& n : p){
            cout << n << " ";
        }
        cout << "] ";
    }
    cout << "\n";

    system("pause");
    return 0;
}

Notice this gets slow really fast.

Things to note for $N =$ numbers in array, $m =$ number of swaps:

  • maximum number of distinct arrays seems to be $\frac{N!}{2}$ and is reached at $m = N-2$ and stays at that value for bigger $m \geq N-2$
  • the corresponding OEIS-sequence

By checking out the paper mentioned in the OEIS article, you can find that the formula for calculating the number of half of the linearly inducible orderings of points in d-space is (Quote):

$$\frac{Q(n, d)}{2}= \sum_{k=0}^{d-1} \hspace{2pt}{}_{n}S_{k} = 1 + \sum_{2 \leq i \leq >d-1}{i} + \sum_{2 \leq i \leq j \leq d-1}ij + \text{ }... \text{ (d Terms)}$$

where ${}_{n}S_{k}$ is the sum of the possible products of numbers taken k at a time without repetition from the set $\{2, 3, ... ,n - 1 \}$.

I wrote a short program to calculate that formula:

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

int nSk(int n, int k){
    if (n < 2)
        return 1;
    if (k > n-2)
        return 0;
    vector<int> numbers;
    numbers.reserve(n - 2);
    for (int i = 0; i < n - 2; ++i){
        numbers.push_back(i + 2);
    }


    std::vector<bool> v(numbers.size());
    std::fill(v.end() - k, v.end(), true);
    int ret = 0;
    do {
        int tmpnum = 1;
        for (int j = 0; j < numbers.size(); ++j) {
            if (v[j])
            {
                tmpnum *= numbers[j];
            }
        }
        ret += tmpnum;
    } while (std::next_permutation(v.begin(), v.end()));
    return ret;
}

int main(){
    int n, d;
    cout << "enter n: ";
    cin >> n;
    cout << "ender d: ";
    cin >> d;
    int sum = 0;
    for (int k = 0; k < d; ++k){
        sum += nSk(n, k);
    }
    //sum *= 2;
    cout << "Q(n, d) =  "<< sum << endl;
    system("pause");
}

Entering $n=$ number of arrays and $d=$ number of swaps $+ 1$ gives you what you are looking for.

I have not figured out yet why the number of distinct arrays which can be formed by swapping exactly m times is related to the number of linearly inducible orderings of n points in d-space precisely, but will update as soon as i do.

Related Question