c++ - How many permutations of N integers with K pairs of numbers that can't be adjacent? -

c++ - How many permutations of N integers with K pairs of numbers that can't be adjacent? -

there n integers {1, 2, ..., n} , k ordered pairs of numbers (a, b); != b; a, b <= n. no pairs identical (for illustration (2, 4) can't inputed more once). same element can appear in many pairs. have write c++ programme algorithm find number of permutations of n integers, no b pair follows a. note pair (a, b) != (b, a).

example:

n = 5 k = 4 k1: (2, 3) k2: (1, 4) k3: (3, 2) k4: (2, 4) perm. ok: 4 1 3 5 2 not ok: 3 1 4 2 5

here brute forcefulness solution, checking recursively 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; } (int = 1; <= n; i++) { if (!visited[i] && !conflict[a][i]) { count(i); } } visited[a] = false; currentlength--; } int main() { int k; cin >> n >> k; (int = 0; < k; i++) { int a, b; cin >> >> b; conflict[a][b] = 1; } (int = 1; <= n; i++) { count(i); } cout << result << endl; homecoming 0; }

n , k go 1000000 , 100000 respectively, need find more efficient solution.

you can create finish graph numbers, , remove edges corresponding input pairs.

in resulting graph, each hamiltonian path corresponds solution. need algorithm find number of hamiltonian path in given graph.

unfortunately there no time efficient solution. is, have enumerate possible paths count them. so, in short, algorithms count hamiltonian paths.

here discussions:

a thread discusses exact problem

wolfram link

depending on number of input pairs, perhaps easier count number of solutions break conditions. can subtract total number of possibilities (n!) reply want.

c++ algorithm permutation combinatorics