Оптимизация этого алгоритма С#

Это вопрос с алгоритмом, у меня есть решение, но оно имеет проблемы с производительностью.

Описание вопроса

Существует n переменных и m требований. Требования представлены как (x <= y), что означает, что x-я переменная должна быть меньше или равна y-ой переменной. Назначьте неотрицательные числа, меньшие 10 для каждой переменной. Просьба рассчитать, сколько разных заданий соответствует всем требованиям. Два назначения различаются в том и только в том случае, если по меньшей мере одна переменная присваивается другому номеру в этих двух присваиваниях. Подберите ответ на 1007.

Формат ввода:

Первая строка ввода содержит два целых числа n и m. Затем следуют m строк, каждая из которых содержит 2 пространственно разделенных целых числа x и y, что означает требование (x <= y).

Формат вывода:

Выведите ответ в одной строке.

Ограничения:

0 < n < 14

0 < m < 200

0 <= x, y < п

Пример ввода:

6 7

1 3

0 1

2 4

0 4

2 5

3 4

0 2

Результат вывода:

1000

Ниже мое решение. требуется слишком много времени, чтобы получить результат при n = 13 и m = 199, но приемлемое время составляет 5 секунд.

Так может ли кто-нибудь подумать о лучшем способе оптимизировать это дальше? Спасибо.

Мое текущее решение:

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ConsoleApplication81 { class Program { const int N = 10; static List<Condition> condition = new List<Condition>(); static void Main(string[] args) { string[] line1 = Console.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(line1[0]); int m = int.Parse(line1[1]); for (int i = 0; i < m; i++) { string[] line = Console.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); condition.Add(new Condition() { X = int.Parse(line[0]), Y = int.Parse(line[1]) }); } // List<int[]> rlist = new List<int[]>(); for (int j = 0; j < N; j++) { int[] assignments = new int[n]; for (int i = 0; i < n; i++) assignments[i] = -1; assignments[0] = j; rlist.Add(assignments); } for (int j = 1; j < n; j++) { List<int[]> rlist2 = new List<int[]>(rlist.Count*5); for (int k = 0; k < rlist.Count; k++) { for (int l = 0; l < N; l++) { rlist[k][j] = l; if (CanPassCondition(rlist[k])) rlist2.Add((int[])rlist[k].Clone()); } } rlist = rlist2; } Console.Write(rlist.Count % 1007); } private static bool CanPassCondition(int[] p) { foreach (var c in condition) { if (p[c.X] == -1 || p[c.Y] == -1) continue; if (p[c.X] > p[c.Y]) return false; } return true; } } class Condition { public int X; public int Y; public override string ToString() { return string.Format("x:{0}, y:{1}", X, Y); } } }

Ответы

Ответ 1

Вот решение на Java, которое работает довольно быстро для меня даже с n = 13, m = 199:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Assignments
{
    private static Map <String, Long> solutions = new HashMap <String, Long> ();

    private static boolean [][] constraints;

    private static long solve (int n, int [] low, int [] high)
    {
        StringBuilder sb = new StringBuilder ();

        for (int i = 0; i < n; i++)
        {
            sb.append (low [i]);
            sb.append (high [i]);
        }

        String signature = sb.toString ();

        Long result = solutions.get (signature);
        if (result == null)
        {
            result = Long.valueOf (doSolve (n, low, high));
            solutions.put (signature, result);
        }

        return result.longValue ();
    }

    private static long doSolve (int n, int [] low, int [] high)
    {
        if (n == 0) return 1;
        else
        {
            long result = 0;

            for (int i = low [n - 1]; i <= high [n - 1]; i++)
            {
                int [] l = new int [n - 1];
                int [] h = new int [n - 1];

                for (int j = 0; j < n - 1; j++)
                {
                    l [j] = constraints [n - 1][j] ? Math.max (low [j], i) : low [j];
                    h [j] = constraints [j][n - 1] ? Math.min (high [j], i) : high [j];
                }

                result += solve (n - 1, l, h);
            }

            return result;
        }
    }

    public static void main(String[] args) throws Exception
    {
        BufferedReader reader = 
            new BufferedReader (
                new InputStreamReader(System.in));

        String nm = reader.readLine ();
        String [] pair = nm.split(" ");
        int n = Integer.parseInt(pair [0]);
        int m = Integer.parseInt(pair [1]);

        constraints = new boolean [n][];
        for (int i = 0; i < n; i++)
            constraints [i] = new boolean [n];

        int [] low = new int [n];
        int [] high = new int [n];
        for (int i = 0; i < n; i++)
            high [i] = 9;

        for (int i = 0; i < m; i++)
        {
            String ab = reader.readLine();
            pair = ab.split (" ");
            int a = Integer.parseInt(pair [0]);
            int b = Integer.parseInt(pair [1]);
            constraints [a][b] = true;
        }

        System.out.println(solve (n, low, high));
    }
}

Собственно, если у вас есть 13 переменных, у вас может быть только 156 (13 * 12) значимых ограничений, но хотя.

Пример ввода:

13 1
3 8

Вывод:

5500000000000

Другой пример ввода:

Вывод: