按照 a*b 的结果对 (a,b) 对进行排序

Question

按照 a*b 的结果对 (a,b) 对进行排序

5

我希望找到满足条件C(m)的最大值m = a*b，其中：

1 <= a <= b <= 1,000,000.

为了实现这一点，我想按照a*b的降序迭代所有a、b对。

例如，对于小于等于5的值，顺序应为：

到目前为止，我想出了一种类似BFS的树形搜索方法，从当前“已访问”的集合中生成候选项，并选择价值最高的候选项，但它很混乱，我不确定它的正确性。我想知道是否有什么技巧我忽略了。

我还对通过任何单调函数f(a,b)进行排序的更一般情况感兴趣（如果存在这样的情况）。

以 C(m) 为例，它可以是“如果m²+m+41是质数，则返回true，否则返回false”，但我真正寻找的是一种通用方法。

- itsadok

2

条件C(m)是什么？（为什么在你的列表中省略了7的倍数?） - Abhishek Bansal

2

@user1990169因为7比5大，这不是“最多5个”吗？只是猜测。 - n. m.

我不明白。您说属性C仅取决于数字m（而不是其分解方式）。那么，您应该在可能的m上测试C。搜索因数分解是浪费时间的，更不用说复杂了。您声称m可以写成小数的乘积，这只是另一个要测试的条件D。 - Colonel Panic

@ColonelPanic 我基本上同意。这就是nmore答案的想法。我希望有一个数学技巧来解决ab的特定情况，而不使用堆。无论如何，如果条件D足够稀疏，使用堆仍然可能更快，例如，如果我使用a^3b^3而不是a*b。 - itsadok

4个回答

2

以下是使用Python中堆的一种不太高效的方法。这可能与您提到的BFS相同，但它相当简洁。(如果有人想出直接的算法，那当然会更好。)

import heapq  # <-this module's API is gross. why no PriorityQueue class?

def pairs_by_reverse_prod(n):
    # put n things in heap, since of course i*j > i*(j-1); only do i <= j
    # first entry is negative of product, since this is a min heap
    to_do = [(-i * n, i, n) for i in xrange(1, n+1)]
    heapq.heapify(to_do)

    while to_do:
        # first elt of heap has the highest product
        _, i, j = to_do[0]
        yield i, j

        # remove it from the heap, replacing if we want to replace
        if j > i:
            heapq.heapreplace(to_do, (-i * (j-1), i, j-1))
        else:
            heapq.heappop(to_do)

- Danica

@Heuster 已经使用基本相同的解决方案（因为我在写这个过程中分心了一会儿），但由于这里有代码，所以我认为我会留下它。 - Danica

1

下面的代码将生成（并打印出）：

[(5, 5), (4, 5), (4, 4), (3, 5), (3, 4), (2, 5), (3, 3), (2, 4), (2, 3), (1, 5), (1, 4), (2, 2), (1, 3), (1, 2), (1, 1)]

这基本上是你想要的，因为如果满足条件，代码可以提前中断。我认为这个问题的重点不在于生成所有可能的(a, b)组合。

算法的关键点在于每次迭代时，我们需要考虑(a - 1, b)和(a, b - 1)。然而，如果a == b，由于a <= b，我们只需要考虑(a - 1, b)。其余的内容涉及到基于它们的乘积m，维护元组队列Q的顺序。

在效率方面，插入到Q时，代码从索引0执行线性搜索。对于较大的a和b值，执行二进制搜索可能会使事情变得更快，也可能不会。

此外，为了进一步优化代码，我们可以在Q中将m与(a,b)一起存储，这样就不必多次计算a * b 。使用以m为键实现Q的1D桶结构也会很有趣。

#!/usr/bin/python

def insert_into_Q((a, b), Q):

    if (a == 0) or (b == 0):
        return

    pos = 0
    for (x, y) in Q:
        if (x == a) and (y == b):
            return
        if x * y < a * b:
            break
        pos = pos + 1
    Q.insert(pos, (a, b))


def main(a, b):

    Q = [(a, b)]
    L = []

    while True:

        if len(Q) == 0:
            break

        (a, b) = Q.pop(0)
        L.append((a, b)) # Replace this with C(a * b) and break if satisfied.

        a1 = a - 1
        b1 = b - 1

        if (a == b):
            insert_into_Q((a1, b), Q)
        else:
            insert_into_Q((a1, b), Q)
            insert_into_Q((a, b1), Q)

    print(L)


if __name__ == "__main__":
    main(5, 5)

- wookie919

1

注意：这是函数C(m)的测试，其中m ≤ 某个目标。它不能用于OP的一般情况，但是是一个特殊情况。

首先找到满足C的最高数字，然后找到与该高数字匹配的一对。找到初始目标数字几乎不需要时间，因为它是从1到1E12的二进制搜索。找到匹配的一对有点难，但仍不像因数分解那么糟糕。

代码：

public class TargetPractice {

    private static final long MAX = 1000000L;

    private long target;

    public static void main(String[] args) {
        Random r = new Random();
        for (int i = 0; i < 5; i++) {
            TargetPractice tp = new TargetPractice(r.nextInt((int) MAX), r.nextInt((int) MAX));
            System.out.println("Trying to find " + tp.target);
            System.gc();
            long start = System.currentTimeMillis();
            long foundTarget = tp.findTarget();
            long end = System.currentTimeMillis();
            System.out.println("Found " + foundTarget);
            System.out.println("Elapsed time " + (end - start) + "\n");
        }
    }

    public TargetPractice(long a, long b) {
        target = a * b + 1;
    }

    private long binSearch() {
        double delta = MAX * MAX / 2;
        double target = delta;

        while (delta != 0) {
            if (hit((long) target)) {
                target = target + delta / 2;
            } else {
                target = target - delta / 2;
            }
            delta = delta / 2;
        }

        long longTarget = (long) target;
        for (int i = 10; i >= -10; i--) {
            if (hit(longTarget + i)) {
                return longTarget + i;
            }
        }
        return -1;
    }

    private long findTarget() {
        long target = binSearch();
        long b = MAX;
        while (target / b * b != target || target / b > MAX) {
            b--;
            if (b == 0 || target / b > MAX) {
                b = MAX;
                target--;
            }
        }
        System.out.println("Found the pair " + (target/b) + ", " + b);
        return target;
    }

    public boolean hit(long n) { 
        return n <= target;
    }
}

它打印：

尝试查找210990777760
找到一对255976、824260
找到210990777760
经过5秒

尝试查找 414698196925
找到一对428076、968749
找到 414698196924
经过27秒

尝试查找75280777586
找到一对78673、956882
找到 75280777586
经过1秒

尝试查找75327435877
找到一对82236、915991
找到 75327435876
经过19秒

尝试查找187413015763
找到一对243306、770277
找到187413015762
经过23秒

- nmore

这很不错，但请注意，找到满足C的最大数字仍然可能需要尝试一万亿次。而且我们找到的数字没有保证是合法的 - 它可能是质数或具有高于1M的因子，因此我们必须继续搜索。我同意，在实践中，对于f（a，b）= a * b，这可能更快。 - itsadok

好的，我更新了代码并添加了一个小检查。现在这个解决方案永远不会尝试一万亿次了。此外，如果存在合法的数字，它也会找到。 - nmore

1

抱歉，我不是很明白你所做的。我的观点是C（m）可以是任何值，因此对于任何大于2的数字可能会返回“false”，因此您必须在找到目标之前检查从一万亿到2的所有数字。你不能用二分搜索来做这件事。 - itsadok

啊，我明白你的意思了，我以为C是连续的...我会编辑帖子的。 - nmore

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Vincent van der Weele · Accepted Answer

假设C(m)是如此神奇，以至于您无法使用任何更好的技术直接找到解决方案，因此您确实需要按降序遍历所有a*b，这是我会做的事情：

初始化一个最大堆，其中包含所有对(a, b)，使得a=b。这意味着堆包含(0, 0), (1, 1), ... , (1.000.000, 1.000.000)。堆应基于a*b值。

现在不断执行以下步骤：

从堆中获取最大对(a, b)。
验证(a, b)是否满足C(a*b)。如果是，则完成。
否则，将(a, b-1)添加到堆中（前提是b>0，否则不执行任何操作）。

这是一种非常简单的O(n log n)时间和O(n)空间算法，前提是您快速找到答案（在几次迭代中）。当然，这取决于C。

如果遇到空间问题，您当然可以通过将问题分解为若干子问题来轻松降低空间复杂度，例如：

仅将(500.000, 500.000), (500.001, 500.001), ... , (1.000.000, 1.000.000)添加到堆中，并找到最佳对(a, b)。
对于(0, 0), (1, 1), ... (499.999, 499.999)执行相同操作。
取两个解决方案中的最佳方案。