java - 具有N个标记顶点和K个未标记边的简单连接图的数量

TL；博士
我的递归关系所占的图形数比应该的少。
我需要找到有N个标记顶点和K个未标记边的简单连通图的数目Link to full source with complete question
[我看到了this post但它没有解决我的问题]
约束条件：2我用两种不同的想法来解决这个问题（不完全是，我后来意识到）。
第一个想法：Connect N nodes with K edges such that there is 1 path between 2 nodes
构思：考虑N-1节点和K-1边。有多少种方法可以添加第n个节点？
在节点N和其他任何N-1节点之间分布一条边；
这很简单，{N-1}1，即给定N-1选择1。
在…之间分布两条边。。。。
....
....
在…之间分布边缘。
我想到的“公式”看起来像这样：

我们只看k∈[n-1，n（n-1）/2]的值（其他值没有意义）。当k=n-1时，它实际上属于Cayley's formula。复发关系是我想到的部分。问题是我计算的图表数量比应该的要少代码：

static Map<List<Integer>, String> resultMap = new HashMap<List<Integer>, String>();
// N -> number of nodes
// K -> number of edges
// N will be at least 2 and at most 20.
// K will be at least one less than n and at most (n * (n - 1)) / 2
public static String answer(int N, int K) {
    /* for the case where K < N-1 */
    if(K < N-1)
        return BigInteger.ZERO.toString();

    /* for the case where K = N-1 */
    // Cayley's formula applies [https://en.wikipedia.org/wiki/Cayley's_formula].
    // number of trees on n labeled vertices is n^{n-2}.
    if(K == N-1)
        return BigInteger.valueOf((long)Math.pow(N, N-2)).toString();

    /* for the case where K > N-1 */
    // check if key is present in the map
    List<Integer> tuple = Arrays.asList(N, K);
    if( resultMap.containsKey(tuple) )
        return resultMap.get(tuple);

    // maximum number of edges in a simply
    // connected undirected unweighted graph
    // with n nodes = |N| * |N-1| / 2
    int maxEdges = N * (N-1) / 2;

    /* for the case where K = N(N-1)/2 */
    // if K is the maximum possible
    // number of edges for the number of
    // nodes, then there is only one way is
    // to make a graph (connect each node
    // to all other nodes)
    if(K == maxEdges)
        return BigInteger.ONE.toString();

    /* for the case where K > N(N-1)/2 */
    if(K > maxEdges)
        return BigInteger.ZERO.toString();

    BigInteger count = BigInteger.ZERO;

    for(int k = 1; k <= N-1 ; k++) {
        BigInteger combinations = nChooseR(N-1, k);
        combinations = combinations.multiply(new BigInteger(answer(N-1, K-k)));
        count = count.add(combinations);
    }

    // unmodifiable so key cannot change hash code
    resultMap.put(Collections.unmodifiableList(Arrays.asList(N, K)), count.toString());

    return count.toString();
}

我发现MSE上的this帖子解决了同样的问题以此作为参考，“公式”看起来有点像这样：

这完全符合预期本节代码如下。

static Map<List<Integer>, String> resultMap2 = new HashMap<List<Integer>, String>();
// reference: https://math.stackexchange.com/questions/689526/how-many-connected-graphs-over-v-vertices-and-e-edges
public static String answer2(int N, int K) {
    /* for the case where K < N-1 */
    if(K < N-1)
        return BigInteger.ZERO.toString();

    /* for the case where K = N-1 */
    // Cayley's formula applies [https://en.wikipedia.org/wiki/Cayley's_formula].
    // number of trees on n labeled vertices is n^{n-2}.
    if(K == N-1)
        return BigInteger.valueOf((long)Math.pow(N, N-2)).toString();

    /* for the case where K > N-1 */
    // check if key is present in the map
    List<Integer> tuple = Arrays.asList(N, K);
    if( resultMap2.containsKey(tuple) )
        return resultMap2.get(tuple);

    // maximum number of edges in a simply
    // connected undirected unweighted graph
    // with n nodes = |N| * |N-1| / 2
    int maxEdges = N * (N-1) / 2;

    /* for the case where K = N(N-1)/2 */
    // if K is the maximum possible
    // number of edges for the number of
    // nodes, then there is only one way is
    // to make a graph (connect each node
    // to all other nodes)
    if(K == maxEdges)
        return BigInteger.ONE.toString();

    /* for the case where K > N(N-1)/2 */
    if(K > maxEdges)
        return BigInteger.ZERO.toString();

    // get the universal set
    BigInteger allPossible = nChooseR(maxEdges, K);

    BigInteger repeats = BigInteger.ZERO;
    // now, to remove duplicates, or incomplete graphs
    // when can these cases occur?
    for(int n = 0 ; n <= N-2 ; n++) {

        BigInteger choose_n_from_rem_nodes = nChooseR(N-1, n);

        int chooseN = (N - 1 - n) * (N - 2 - n) / 2;

        BigInteger repeatedEdges = BigInteger.ZERO;
        for(int k = 0 ; k <= K ; k++) {
            BigInteger combinations = nChooseR(chooseN, k);

            BigInteger recurse = new BigInteger(answer2(n+1, K-k));

            repeatedEdges = repeatedEdges.add(combinations.multiply(recurse));
        }

        repeats = repeats.add(choose_n_from_rem_nodes.multiply(repeatedEdges));
    }

    // remove repeats
    allPossible = allPossible.subtract(repeats);

    // add to cache
    resultMap2.put(Collections.unmodifiableList(Arrays.asList(N, K)), allPossible.toString());
    return resultMap2.get(tuple);
}

如果有人能指点我的方向，这样我就能在第一次接近时发现错误，我将不胜感激。第二种方法可以工作，但是它会进行O（N K）递归调用，K在N中是平均二次方的。所以，显然不是很好，尽管我已经尝试使用DP最小化计算下面是nchooser（）和factorial（）函数。
NChooser代码：

static Map<List<Integer>, BigInteger> nCrMap = new HashMap<List<Integer>, BigInteger>();
// formula: nCr = n! / [r! * (n-r)!]
private static BigInteger nChooseR(int n, int r) {
    // check if key is present
    List<Integer> tuple = Arrays.asList(n, r);
    if( nCrMap.containsKey(tuple) )
        return nCrMap.get(tuple);

    // covering some basic cases using
    // if statements to prevent unnecessary
    // calculations and memory wastage

    // given 5 objects, there are 0 ways to choose 6
    if(r > n)
        return BigInteger.valueOf(0);

    // given 5 objects, there are 5 ways of choosing 1
    // given 5 objects, there are 5 ways of choosing 4
    if( (r == 1) || ( (n-r) == 1 ) )
        return BigInteger.valueOf(n);

    // given 5 objects, there is 1 way of choosing 5 objects
    // given 5 objects, there is 1 way of choosing 0 objects
    if( (r == 0) || ( (n-r) == 0 ) )
        return BigInteger.valueOf(1);

    BigInteger diff = getFactorial(n-r);

    BigInteger numerator = getFactorial(n);

    BigInteger denominator = getFactorial(r);
    denominator = denominator.multiply(diff);

    // unmodifiable so key cannot change hash code
    nCrMap.put(Collections.unmodifiableList(Arrays.asList(n, r)), numerator.divide(denominator));

    return nCrMap.get(tuple);
}

阶乘编码：

    private static Map<Integer, BigInteger> factorials = new HashMap<Integer, BigInteger>();
    private static BigInteger getFactorial(int n) {
        if(factorials.containsKey(n))
            return factorials.get(n);

        BigInteger fact = BigInteger.ONE;
        for(int i = 2 ; i <= n ; i++)
            fact = fact.multiply(BigInteger.valueOf(i));

        factorials.put(n, fact);

        return fact;
    }

一些测试代码：

public static void main(String[] args) {
    int fail = 0;
    int total = 0;
    for(int n = 2 ; n <= 20 ; n++) {
        for(int k = n-1 ; k <= n*(n-1)/2 ; k++) {
            total++;
            String ans = answer(n,k);
            String ans2 = answer2(n,k);
            if(ans.compareTo(ans2) != 0) {
                fail++;
                System.out.println("N = " + n + " , K = " + k + " , num = " + ans + " ||| " + ans2);
            }
        }
    }
    System.out.println("Approach 1 fails " + ((100*fail)/total) + "% of the test");
}

P.S.我在谷歌Foobar挑战赛中得到了这个挑战。只是想让大家都知道N-1是根据Foobar上的测试用例判断的，而挑战者看不到这些测试用例。
为了阅读这些，这里有一个video of a tiny hamster eating a tiny burrito。

最佳答案

另一种方法。。。
我们知道f(n,n-1) = n^{n-2}是
有标记的有根树[凯利公式]
现在，设f(n, k)为具有n个节点和k个边的连通图的总数，
我们有一个如何添加新边的特征：
1）取f[n，k]中的任意图，可以在
{n\choose 2}-k对不匹配的节点。
2）如果有两个连通图G_1和G_2，则用f[s，t]和
分别为F[n-s，k-t]（即具有s节点的连通图
t边和一个具有n-s节点和k-t边的连通图，
然后你可以通过连接这些来外科学地构造一个新的图
两个子图在一起。
您有s * (n-s)对顶点可供选择，并且可以选择
s point中的{n \choose s}方式。然后你可以对选择
s和t分别来自
每幅图重复计数两次我们把这个结构称为1 to n-1。
然后g(n, k)
现在，没有其他方法可以添加额外的边（不减少到
上面的两个结构），所以加项
g(n,k) = (\sum_s,t {n \choose s} s (n-s) f(s,t) f(n-s, k-t))/2
给出了我们得到的图的多集的一个特征
构建。为什么这是多集？
好吧，让我们看看这两个子类的案例分析
（施工简介）在图中取一个随机图
是这样建造的。归纳假设是
h(n,k+1) = (N - k)f(n,k) + g(n,k)多集内g的副本。
让我们看看归纳的情况
如果在连通图中打断一条边，则它要么保持连通
图或它分成两个连通图。
现在，固定在一个g，如果你打破了任何其他边缘，那么e仍然是
在不同的结构中。如果你打破了，你还没有
另一个独特的结构。
这意味着有可能存在不同的图类
（两个组件中的一个组件）我们可以从中构造相同的
最终图形h(n, k+1)。
因此，k + 1计算每个图的总数h(n, k+1)次，依此类推
edge e=(k+1) - 1=e。
给定一个固定的k + 1和g，这个递归将在h(n,k+1)时间内计算出正确的结果，
如此复杂的智慧，它相当于以前的算法。
这个结构的好处是它很容易产生一个分析
生成函数以便对其进行分析。
在这种情况下，假设有一个复值函数k+1，
然后
f(n, k+1)。
你需要很多复杂的分析机器来解决这个重复的pde。
下面是一个java实现[source]