将 python 代码转换为 java 以计算简单连通图数的未知问题

Question

此代码的目标：具有 N 个标记顶点和 K 个未标记边的简单连通图的数量。

注意：这可能被认为是代码审查问题，但经过反复尝试，我认为 python 和 java 代码具有相同的功能。我不确定代码是否有问题，或者与语言的复杂性有关，或者是我忽略了某些东西的错误。

这是为了 Google Foobar 挑战。我是用上面的方法完成的。我已经发布了所有源代码的链接，测试了所有可能的情况。

第一种方法完全有效。唯一的问题 - 它进行 O(NK) 次递归调用并且 K 在 N 中平均为二次方。[Full source]

一位朋友想出了一个算法，用自下而上的方法来做同样的事情。主要功能：

def answerHelper(n,k):
    totalGraphs = 0

    for s in range(1,n):
        graphs = 0
        for t in range(0,k+1):
            graphs += answer(s, t) * answer(n - s, k - t)

        graphs = choose(n, s)*s*(n - s) * graphs
        totalGraphs+= graphs

    return totalGraphs/2

F = {}
def answer(n, k):
    if (n, k) in F:
        return F[n, k]

    N = n * (n - 1)/2

    if k is n - 1:
        return int(n ** (n-2))
    if k < n or k > N:
        return 0
    if k == N:
        return 1

    result = ((N - k + 1) * answer(n, k - 1) + answerHelper(n, k - 1)) / k
    F[n, k] = result
    return result

与原始工作Java代码相比，python在4个案例中失败 [diffchecker]. I presume this is because of some sort of overflow(?). [Full python source]

我正在尝试将此 python 代码转换为 Java。这是我想出的。

static Map<List<Integer>, String> resultMap = new HashMap<List<Integer>, String>();
public static String answer(int N, int K) {
    /* 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-1 or K > N(N-1)/2 */
    if(K < N-1 || K > maxEdges)
        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(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();

    // number of edges left from maxEdges if I take away K-1 edges
    BigInteger numWays = BigInteger.valueOf(maxEdges - K + 1);

    // number of graphs possible for each of the numWays edges for a graph that has 1 less edge
    BigInteger numGraphsWithOneLessEdge = new BigInteger( answer(N,  K-1) );

    // number of all possible subgraphs with K-1 edges
    BigInteger subGraphs = answerHelper(N, K-1);

    // numWays*numGraphsWithOneLessEdge + subGraphs
    BigInteger result = subGraphs.add(numWays.multiply(numGraphsWithOneLessEdge));

    // this contains repeats for each of the K edges
    result = result.divide(BigInteger.valueOf(K));

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

private static BigInteger answerHelper(int N, int K) {

    BigInteger totalGraphs = BigInteger.ZERO;

    for(int n = 1 ; n < N ; n++) {
        BigInteger graphs = BigInteger.ZERO;
        for(int k = 0 ; k <= K ; k++) {
            // number of graphs with n nodes and k edges
            BigInteger num = new BigInteger( answer(n, k) );

            // number of graphs with N-n nodes and K-k edges
            BigInteger num2 = new BigInteger( answer(N-n, K-k) );

            graphs = graphs.add( num.multiply(num2) );
        }

        // number of ways to choose n nodes from N nodes
        BigInteger choose = choose(N, n);

        // this is repeated for each of the n chosen nodes
        // and the N-n unchosen nodes
        choose = choose.multiply(BigInteger.valueOf(n)).multiply(BigInteger.valueOf(N-n));

        totalGraphs = totalGraphs.add( choose.multiply(graphs) );

    }

    // now, consider the case where N = 20
    // when n = 2, we compute for N-n = 18
    // when n = 18, we do the same thing again
    // hence, contents of totalGraphs is 2 times
    // of what it should be
    return totalGraphs.divide(BigInteger.valueOf(2));
}

[Full source]

这段代码，我打算发挥与 Python 相同的功能，但在多个情况下都无法正常工作 java 代码 [diffchecker]

如能得到指导，将不胜感激

Answer 1

问题出在 Java 代码中，而不是 Python 代码中（我怀疑是溢出；一些细致的调试证明并非如此。它不是最简单的比较 20 奇数位的数字）。

错误代码：

/* 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();

对于 N>=17，(long)Math.pow(N, N-2) 不准确。发生这种情况是因为 double 值越大，连续值之间的差距就越大。 double 不能表示其范围内的每个整数值，这就是问题所在。它返回最接近精确结果的双精度值。此外，对于 double 值，尾数为 52 位，大致等于 16(?) 位小数。因此溢出（不是一个词）。因此，返回的值小于应有的值。必须用以下代码块替换它。

if(K == N-1) {
    if(N < 2)
        return BigInteger.valueOf((long)Math.pow(N, N-2)).toString();

    // multiply N to itself N-2 times
    BigInteger val = BigInteger.ONE;

    int count = 0;

    while(count++ != N-2)
        val = val.multiply( BigInteger.valueOf( (long)N ) );

    return val.toString();
}

将 python 代码转换为 java 以计算简单连通图数的未知问题

Unknown issue converting python code to java to calculate number of simple connected graphs

python

java

algorithm

graph

graph-algorithm