java - 如何找到数字中的所有方 block (Java)？

Question

我似乎有心理障碍，无法解决以下问题。基本上，我想找到给定数字中所有可能的正方形，即 N = S*S*A，其中给定数字中的 N，S*S 是正方形，A 是其他数字。我需要找到所有可能的这种组合。
到目前为止，我已经将数字 N 分解为素数序列，并构建了一个 Map，其中键是序列中唯一的素数，值是该素数出现的次数。
例如，对于某些数字可能有这样的序列:
2 2 2 3 3 5 5 5 5 7 7 7 7 7,
因此，正方形应该是 4, 9, 25, 49, 36, 100, 196, 225, 441, 1225。对于这样的序列，我将有以下 map :
2 3
3 2
5 4
7 5
接下来，我将奇数值减一:
2 2
3 2
5 4
7 4
主要问题是如何从这张 map 中获取上面写的方 block 。我的想法是运行 2 个循环(不知道效率如何):

for(Map.Entry<BigInteger, Integer> entry : frequency.entrySet()) {
    for(Map.Entry<BigInteger, Integer> ientry : frequency.entrySet()) {
    }
}

很明显如何将 map 中的所有键对相乘，但我无法想出必须施加的条件来考虑多重性。
预先非常感谢您!
附注有没有不用嵌套循环的好方法？

Answer 1

我认为嵌套循环不会对你有帮助；你正在进入递归领域。 :-)

您所问的问题本质上可以归结为这一点。您有一个数字列表，以及这些数字的频率。您想要想出所有独特的方法来选择每个数字的一​​定数量的副本。例如，给定

2 2
3 4
5 2

你想要

2⁰ 3⁰ 5⁰

2⁰ 3⁰ 5²

2⁰ 3² 5⁰

2⁰ 3² 5²

2⁰ 3⁴ 5⁰

2⁰ 3⁴ 5²

2² 3⁰ 5⁰

2² 3⁰ 5²

2² 3² 5⁰

2² 3² 5²

2² 3⁴ 5⁰

2² 3⁴ 5²

如果我们只写指数，那么我们有

0 0 0
0 0 2
0 2 0
0 2 2
0 4 0
0 4 2
2 0 0
2 0 2
2 2 0
2 2 2
2 4 0
2 4 2

所以问题是如何生成它。幸运的是，有一个非常漂亮的递归公式来生成这些数字。事情是这样的。我们想要编写一个函数 AllSquares，它接受素数对及其重数的列表，然后返回可以由这些完全平方素数形成的所有可能的乘积。我们将通过归纳法来完成此操作。

作为我们的基本情况，如果您向 AllSquares 提供空列表，则只有一个平方积，即 1，即空列表元素的空积。

对于归纳步​​骤，假设我们有一个非空列表，其第一个元素是(素数，重数)，其余元素是“其余”。假设我们递归地计算通过对列表的其余元素调用 AllSquares 形成的列表“组合”。然后，对于 i = 0, 2, 4, ...，重数，如果您将列表中的元素乘以 baseⁱ，您最终会得到一个新的完美平方列表。如果将所有这些值相结合，您最终将得到所有可以从这些数字中形成的完美平方。最酷的部分是，即使重数是奇数，它也能工作，因为您只会考虑偶数指数。

下面是一些实现该算法的简单 Java 代码。它根本没有效率，但它表达了要点:

private static List<Integer> allSquares(List<BaseMultiplicity> elems) {
    /* Base case: If the list is empty, there's only one square. */
    if (elems.isEmpty()) {
        return Collections.singletonList(1);
    }

    /* Recursive case: Compute the answer for the rest of the list. */
    List<BaseMultiplicity> rest = new LinkedList<BaseMultiplicity>(elems);
    rest.remove(0);
    List<Integer> recResult = allSquares(rest);

    /* Now, for each even power of this number, add appropriately-scaled
     * copies of the recursive solution to the result.
     */
    List<Integer> result = new ArrayList<Integer>();
    for (int i = 0, base = 1; i < elems.get(0).multiplicity; 
         i += 2, base *= elems.get(0).prime)
        for (Integer elem: recResult)
            result.add(elem * base * base);
    
    return result;
}

希望这有帮助!