How many permutations of N integers with K pairs of numbers that cannot be adjacent?
There are N integers {1, 2, ..., N} and K ordered pairs of numbers (A, B); A! = B; A, B <= N. No pairs are identical (for example, (2, 4) cannot be entered more than once). The same element can appear in many pairs. I have to write a C ++ program with an algorithm to find the number of permutations of all N integers, where none of B should follow its A. Note that the pair (A, B)! = (B, A).
Example:
n = 5
k = 4
k1: (2, 3)
k2: (1, 4)
k3: (3, 2)
k4: (2, 4)
This perm. is OK: 4 1 3 5 2
This is not OK: 3 1 4 2 5
Here is my brute-force solution recursively checking every possibility:
#include <iostream>
using namespace std;
int n;
bool conflict[1000][1000];
bool visited[1000];
int result = 0;
int currentlength = 0;
void count(int a) {
visited[a] = true;
currentlength++;
if (currentlength == n) {
result++;
visited[a] = false;
currentlength--;
return;
}
for (int i = 1; i <= n; i++) {
if (!visited[i] && !conflict[a][i]) {
count(i);
}
}
visited[a] = false;
currentlength--;
}
int main()
{
int k;
cin >> n >> k;
for (int i = 0; i < k; i++) {
int a, b;
cin >> a >> b;
conflict[a][b] = 1;
}
for (int i = 1; i <= n; i++) {
count(i);
}
cout << result << endl;
return 0;
}
N and K go up to 1,000,000 and 100,000 respectively, so I need to find a more efficient solution.
source to share
You can create a complete graph with all numbers and remove the edges corresponding to the input pairs.
In the resulting graph, each path corresponds to the Hamiltonian solution. So, you need an algorithm to find the number of a Hamiltonian path in a given graph.
Unfortunately, there is no effective time solution. That is, you must list all the possible ways to count them. So, in short, look for algorithms to compute Hamiltonian paths.
Here are some discussions:
See this thread that discusses this exact issue
Depending on the number of input pairs, it might be easier to count the number of decisions that violate your conditions. You can subtract it from the total number of possibilities (n!) To get the answer you want.
source to share