C#解决从不同数字组中选择2个数字的多种方法

Question

我要解决的问题是这样的。

我得到了 N，告诉我数字的范围是 0, 1, ...，N-2，N-1。

我也得到了配对，告诉我这些数字对在同一个“组”中。

例如:

N=6，0和1配对，1和4 是成对的，2 和3 是成对的，我知道剩下的数字是自己的组。

然后我知道分组是 {0, 1, 4}, {2, 3}, {5}。

从这些组中的不同组中选择两个数字的方法数是 11，这就是我要解决的数字。这些选择是:

{0,2}， {0,3}， {0,5}， {1,2}， {1,3}， {1,5}， {4,2}, {4,3}, {4,5}, {2,5}， {3,5}

谁能帮我找出逻辑错误的地方？因为我没有通过较大的测试用例并通过了较小的测试用例。

我的代码:

    static int Combinations(int N, int K)
    {
        decimal result = 1;
        for (int i = 1; i <= K; i++)
        {
            result *= N - (K - i);
            result /= i;
        }
        return (int)result;
    }

    /// <summary>
    /// Given a set of n numbers 0, 1, ..., n-1 and a list of pairs
    /// of the numbers from the set where each pair (i,j) means that
    /// number i and j are in the same group, find the number of ways
    /// to choose 2 numbers that are not in the same group.
    /// </summary>
    static int PoliticallyCorrectPairs(int n, Tuple<int, int>[] pairs)
    {
        // Create a map that from each number to a number representing
        // the group that it is in. For example, if n = 5 and 
        // pairs = { (0, 1), (2, 3), (0, 4) }, then the map will look 
        // like 
        // 0 -> 1
        // 1 -> 1
        // 2 -> 2
        // 3 -> 2
        // 4 -> 1
        // indicating that 0,1,4 belong to one group and 2,3 to the other.
        int[] gmap = new int[n];
        int k = 1;
        foreach(Tuple<int, int> pair in pairs)
        {
            int i = pair.Item1,
                j = pair.Item2;

            // If both i and j are already in groups, combine those into a
            // single group if it isn't already.
            if (gmap[i] != 0 && gmap[j] != 0)
            {

                if(gmap[i] != gmap[j])
                {
                    for(int m = 0; m < n; ++m)
                        if(gmap[m] == gmap[j])
                            gmap[m] = gmap[i];
                }
            }
            else if(gmap[j] != 0) // j is in a group and i isn't
                gmap[i] = gmap[j]; // add i to j's group
            else if(gmap[i] != 0) // i is in a group and j isn't
                gmap[j] = gmap[i]; // add j to i's group
            else 
                gmap[i] = gmap[j] = k++; // Put both in same new group.
        }
        // Those not assigned to a group each end up in a group alone.
        for(int i = 0; i < gmap.Length; ++i)
            if(gmap[i] == 0)
                gmap[i] = k++;

        // Get the group sizes as an array.
        int[] gcnts = gmap.GroupBy(x => x).Select(g => g.Count()).ToArray();

        // Total number of ways to choose pairs of numbers. 
        int totalCombinations = Combinations(n, 2);

        // Number of pairs from previous count that are in the same group.
        int impossibleCombinations = gmap.GroupBy(x => x)
            .Select(g => g.Count())
            .Where(count => count > 1)
            .Sum(count => Combinations(count, 2));

        return totalCombinations - impossibleCombinations;
    }

比如我路过

    [TestMethod]
    public void Sample1()
    {
        int N = 5;
        Tuple<int, int>[] pairs = new Tuple<int, int>[]
        {
            Tuple.Create(0, 1),
            Tuple.Create(2, 3),
            Tuple.Create(0, 4)
        };
        Assert.AreEqual(6, PoliticallyCorrectPairs(N, pairs));
    }

但是失败了

    [TestMethod]
    public void TestCase2()
    {
        int N = 100;
        Tuple<int, int>[] pairs =
@"0 11
2 4
2 95
3 48
4 85
4 95
5 67
5 83
5 42
6 76
9 31
9 22
9 55
10 61
10 38
11 96
11 41
12 60
12 69
14 80
14 99
14 46
15 42
15 75
16 87
16 71
18 99
18 44
19 26
19 59
19 60
20 89
21 69
22 96
22 60
23 88
24 73
27 29
30 32
31 62
32 71
33 43
33 47
35 51
35 75
37 89
37 95
38 83
39 53
41 84
42 76
44 85
45 47
46 65
47 49
47 94
50 55
51 99
53 99
56 78
66 99
71 78
73 98
76 88
78 97
80 90
83 95
85 92
88 99
88 94"
        .Split('\n')
        .Select(line =>
        {
            int[] twofer = line.Split(' ').Select(s => int.Parse(s)).ToArray();
            return Tuple.Create(twofer[0], twofer[1]);
        })
        .ToArray();
        Assert.AreEqual(3984, PoliticallyCorrectPairs(N, pairs));
    }

知道我哪里出错了吗？

Answer 1

问题出在组合部分:

if(gmap[i] != gmap[j])
{
    for(int m = 0; m < n; ++m)
        if(gmap[m] == gmap[j]) // here
            gmap[m] = gmap[i];
}

当 m 命中 j 时，gmap[j] 被替换为 gmap[i]，因此其余元素根据 gmap[i] 检查。

简单地将替换值放入局部变量:

if(gmap[i] != gmap[j])
{
    int g = gmap[j];
    for(int m = 0; m < n; ++m)
        if(gmap[m] == g)
            gmap[m] = gmap[i];
}