这是一道算法题，我有解法但是有性能问题。

Question Description

There are n variables and m requirements. Requirements are represented as (x <= y), which means the x-th variable must be smaller or equal to the y-th variable. Assign nonnegative numbers smaller than 10 to each variable. Please calculate how many different assignments that match all requirements. Two assignments are different if and only if at least one variable is assigned different number in these two assignment. Module the answer by 1007.

Input Format:

First line of the input contains two integers n and m. Then following m lines each containing 2 space-seperated integers x and y, which means a requirement (x <= y).

Output Format:

Output the answer in one line.

Constraints:

0 < n < 14

0 < m < 200

0 <= x, y < n

Sample Input:

6 7

1 3

0 1

2 4

0 4

2 5

3 4

0 2

Sample Output:

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);
        }
    }
}

最佳答案

这是一个 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

另一个示例输入:

13 12
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12

输出:

497420

关于c# - 优化此 C# 算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14950853/