3
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ There are $\binom{N}{2}$ ways of performing a swap, for any given swap, and $N!$ possible permutations in total... perhaps one could use inclusion-exclusion? $\endgroup$ Sep 18, 2016 at 10:29
  • $\begingroup$ Let $x=C(n,2)$ For $k$ swaps, you have $C(x,k)$ ways to select swaps, then $k!$ ways to perform these swaps. $\endgroup$
    – maverick
    Sep 18, 2016 at 10:33

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Let $f(n,m)$ be the number of permutations of that can be obtained by exactly $m$ transpositions. Then $f(n+1,m)=f(n,m)+nf(n,m-1)$: there are $f(n,m)$ permutations that can be obtained by transpositions not involving $n+1$, and there are $nf(n,m-1)$ that can be obtained by applying $m-1$ transpositions to $12\ldots n$ and then one transposition interchanging $n+1$ and the desired last element. This is the same recurrence as the one for $Q(n,d)$, but where that has initial conditions $Q(n,1)=2$ for $n\ge 2$ and $Q(2,d)=2$ for $d\ge 1$, this one has $f(n,0)=1$ for $n\ge 1$ and ... $\endgroup$ Sep 18, 2016 at 22:33
  • 2
    $\begingroup$ ... $f(2,m)=1$ for $m\ge 0$. It follows immediately that $f(n,m)=\frac12Q(n,m+1)$. $\endgroup$ Sep 18, 2016 at 22:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .