combinations - 从可能的对数中获取原始数组的大小

Question

我有这个功能

public int numberOfPossiblePairs(int n)
{
        int k=2;
        if (k>n-k) { k=n-k;}  
        int b=1;
        for (int i=1, m=n; i<=k; i++, m--)
            b=b*m/i;
        return b;
} 

它得到了你可以从给定数量的项目中制作的对数，例如，如果你有一个包含 1000 个项目的数组，你可以制作 499,500 对。但我真正需要的是相反的。换句话说，一个函数将 499500 作为参数，并返回 1000 作为可以产生那么多对的唯一项目的原始数量。（如果它还可以处理不完美的数字，例如 499501，这将是一个奖励，其中没有多少独特的项目可以产生那么多独特的配对，但它仍然会返回 1000 作为最接近的数字，因为它产生了 499500 配对。）

我意识到我可以增量循环 numberOfPossiblePairs() 直到我看到我正在寻找的数字，但似乎应该有一种算法方式来做到这一点，而不是像那样强制它。

标签： combinations

Answer 1

你的问题归结为一点代数，可以及时解决O(1)。我们首先注意到您的函数没有给出对的排列数，而是给出对的组合数。无论如何，可以轻松更改以下逻辑以适应排列。

我们首先编写组合数选择k的公式。

设置n = 1000和r = 2给出：

1000! / (2!(998)!) = 1000 * 999 / 2 = 499500

就像那样numberOfPossiblePairs(1000)。

继续我们的练习，对于我们的示例，我们有r = 2，因此：

total = n! / ((n - 2)! * 2!)

我们现在简化：

total = (n * (n - 1)) / 2

total * 2 = n^2 - n

n^2 - n - 2 * total = 0

现在我们可以应用二次公式来求解n。

这里我们有x = n、a = 1、b = -1和c = -2 * total，它们给出：

n = (-(-1) +/- sqrt(1^2 - 4 * 1 * (-2 * total))) / 2

因为我们只对正数感兴趣，所以我们排除了负解。在代码中，我们有类似的东西（注意，看起来 OP 正在使用 Java，我不是这里的专家......以下是C++）：

int originalNumber(int total) {
    int result;
    result = (1 + std::sqrt(1 - 4 * 1 * (-2 * total))) / 2;
    return result;
}

至于如果结果不是整数则返回最接近的值的额外问题，我们可以在强制转换为整数之前简单地将结果四舍五入：

int originalNumber(int total) {
    int result;
    double temp;
    temp = (1 + std::sqrt(1 - 4 * 1 * (-2 * total))) / 2;
    result = (int) std::round(temp);
    return result;
}

现在，当500050传递 like 值时，实际结果是1000.55，上面会返回1001，而第一个解决方案会返回1000。