3

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) can't be inputed 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 no B from any pair follows its A. Note that 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, 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;
    }
    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 1000000 and 100000 respectively, so I need to find a more efficient solution.

Kamil Ryszkowski
  • 31
  • 2
  • 1
    Can pairs overlap, for example k1 = (2,3), k2 = (2,4) ? – גלעד ברקן Oct 11 '14 at 18:03
  • When you say no pairs are identical, do you mean that it is impossible to have both the pair (1,2) and the pair (1,3) on the grounds that 1 is in both pairs? (Or are you just saying that the pair (1,2) cannot appear twice in the list?) – Peter de Rivaz Oct 11 '14 at 18:03
  • 2
    Given A=1 and B=4, I can understand why "1 4" is **not** OK. But why is "4 1" OK? Seems like B is next to A to me. Perhaps you meant to say that B cannot immediately follow A. – user3386109 Oct 11 '14 at 18:03
  • Edited. Pairs can overlap, the same pair can't appear twice in the same order, B can't follow A, but A can follow B, unless there is a pair (B, A). – Kamil Ryszkowski Oct 11 '14 at 18:19

1 Answers1

1

You can create a complete graph with all the numbers, and remove the edges corresponding to input pairs.

In the resulting graph, each hamiltonian path corresponds to a solution. So you need an algorithm to find the number of hamiltonian path in a given graph.

Unfortunately there is no time efficient solution. That is, you have to enumerate all possible paths to count them. So, in short, look for algorithms to count hamiltonian paths.

Here are some discussions:

A so thread that discusses this exact problem

wolfram link

Depending on number of input pairs, perhaps it is easier to count the number of solutions that break your conditions. You can subtract it from the total number of possibilities (n!) to get the answer you want.

Community
  • 1
  • 1
ElKamina
  • 7,747
  • 28
  • 43