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$.
[Math] Number of distinct Arrays formed from swapping pairs
combinatoricspermutations
Related Solutions
First of all, I claim that the sum of all order $n$ permutations matrices is equal to the matrix whose entries are all equal to $(n-1)!$. This is because for each $1\le i \le n$ and $1\le j\le n$, the number of permutations for which $\pi(i)=j$ is $(n-1)!$.
Another way of writing this constant matrix is $(n-1)!\def\1{{\bf1}}\1\1^T$, where $\1$ is a column vector of all ones.
Therefore, letting $B$ be any fixed $n\times n$ matrix, and $A_\pi$ be the permutations matrix corresponding to $\pi$, then \begin{align} \sum_{\pi\in S_n}\mathrm{tr}(A_\pi B) &=\mathrm{tr}\left(\left(\sum_{\pi}A_\pi\right)B\right) \\&=\mathrm{tr}\big((n-1)!\1\1^TB\big) \\&=(n-1)!\mathrm{tr}(\1^TB\1) \end{align} The last equality is the cyclic property of trace. Finally, $\mathrm{tr}(\1^TB\1)$ is the sum of the entries of $B$. Therefore, the sum of the traces of the permutations of a matrix is equal to $(n-1)!$ times the sum of the entries of that matrix.
This was a programming problem asked on HackerEarth. I will address it as a programming problem rather than a Mathematical one.
We have to write code that runs for the given input in under $1$ second.
You are given a permutation of $6$ elements and an integer $N$. Give the probability that the permutation will be sorted after exactly $N$ swaps. $$1 \le N \le 100$$ If the probability is $\frac{P}{Q}$, where $P, Q$ are integers in the reduced form, print $P \cdot Q^{-1} \pmod {10^9 + 7}$
The general rule of thumb in any programming problem is that the computer can perform $10^7$ instructions per second and the time limit is usually $1$ second. Hence, any code we write must be able to obtain the answer in fewer than $10^7$ computer instructions.
Recurrence
Let $P(A, i)$ be the probability of sorting an array $A$ in exactly $i$ moves.
Let $A'$ be an array that we can obtain from $A$ in exactly one swap. In any array $A$, we can make $\binom{6}{2} = 15$ swaps. $$P(A, i) = \frac{1}{\binom{6}{2}}\sum P(A', i - 1)$$
Explanation of the Recurrence
We know that the probability of an event is the size of the the event set divided by the size of the total space set.
In order to know the probability of sorting an array $A$ in $i$ moves, we need to know the probability of sorting $A'$ in $i - 1$ moves, and then divide by the number of different arrays we can get in $1$ move.
For example, from ${1, 2, 3}$, we can transition to $3$ different arrays with swaps.
- $\{1, 2, 3\} \to \{2, 1, 3\}$
- $\{1, 2, 3\} \to \{3, 2, 1\}$
- $\{1, 2, 3\} \to \{2, 1, 3\}$
In order to know the probability of sorting $\{1, 2, 3\}$ in $x$ moves, we need to add the probability of sorting these $3$ arrays in $x - 1$ moves and divide by $3$
The probabability of sorting an array $\{1, 2, 3\}$ in $2$ moves is $$P(\{1, 2, 3\}, 2) = \frac{1}{3} \cdot \big( P(\{1, 3, 2\}, 1) + P(\{2, 1, 3\}, 1) + P(\{3, 2, 1\}, 1) \big)$$
Space and Time Complexity
Let us now try to estimate the time and space complexity. How many states does this DP have ? We have $6! = 720$ different arrays and $$N = 100$$ moves. So, we will have $720 \times 100$ different states.
How many transitions are there in each state ? Each state has $\binom{6}{2} = 15$ transitions.
The total number of steps is roughly $720 \times 100 \times 15 \approx 10^7$
C++ Code
Here is a function which computes the probability of sorting an array with $N$ random swaps. For convenience, I have stored the array as a string.
I used Fermat's Little Theorem to compute the modular inverse of the denominator. $$x^{m - 1} = 1 \pmod m \implies x \cdot x^{m - 2} = 1 \pmod m$$
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7, NO_OF_ELEMENTS = 6;
map <pair <string, int>, long long> probability;
long long power_mod(long long x, long long p, long long m)
{
long long answer = 1;
while(p > 0)
{
if(p%2 == 1)
{
answer = (answer*x)%m;
}
x = (x*x)%m;
p = p >> 1;
}
return answer;
}
long long inverse(long long x, long long m)
{
return power_mod(x, m - 2, m);
}
int is_sorted(string S)
{
for(int i = 0; i + 1 < NO_OF_ELEMENTS; i++)
{
if(S[i] > S[i + 1])
{
return false;
}
}
return true;
}
long long get_probability(string S, int no_of_moves)
{
pair <string, int> current_state = make_pair(S, no_of_moves);
if(probability.find(current_state) != probability.end())
{
return probability[current_state];
}
if(no_of_moves == 0)
{
probability[current_state] = (is_sorted(S) ? 1 : 0);
return probability[current_state];
}
long long numerator = 0, new_arrays = 0;
for(int i = 0; i < NO_OF_ELEMENTS; i++)
{
for(int j = i + 1; j < NO_OF_ELEMENTS; j++)
{
string new_S = S;
swap(new_S[i], new_S[j]);
numerator += get_probability(new_S, no_of_moves - 1);
new_arrays++;
}
}
probability[current_state] = numerator*inverse(new_arrays, MOD);
probability[current_state] %= MOD;
return probability[current_state];
}
void solve()
{
int no_of_moves;
cin >> no_of_moves;
vector <int> A(NO_OF_ELEMENTS);
for(int i = 0; i < NO_OF_ELEMENTS; i++)
{
cin >> A[i];
}
string S;
for(int i = 0; i < NO_OF_ELEMENTS; i++)
{
S += A[i];
}
cout << get_probability(S, no_of_moves) << "\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int no_of_test_cases;
cin >> no_of_test_cases;
while(no_of_test_cases--)
solve();
return 0;
}
Best Answer
Duplicate but also unanswered
Here's a piece of c++ code i just wrote to help find and answer to this.
Notice this gets slow really fast.
Things to note for $N =$ numbers in array, $m =$ number of swaps:
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):
I wrote a short program to calculate that formula:
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.