Edit Question - KnowledgeHub

Title Body

Problem: Given a number n, is there an efficient algorithm to obtain a list of 2-combinations from the set {1...n}, sorted by the value of the product of the combination? I need this in order to determine the largest product of two *-digit numbers that satisfies a certain condition. If the list is unsorted, I must first determine all combinations that satisfy the condition, then iterate through those to find the combination with the largest product, which is inefficient. As an example, given n = 3, the combinations possible are: Combination: Product: 3, 3 9 3, 2 6 3, 1 3 2, 2 4 2, 1 2 1, 1 1 Sorted by the value of the product in descending order, this is: Combination: Product: 3, 3 9 2, 3 6 2, 2 4 1, 3 3 1, 2 2 1, 1 1 Extra background: I just solved a Project Euler question regarding finding the largest palindromic number that is a product of two 3 digit numbers. My approach was to iterate downward from 999 (the largest 3 digit number) with two factors and find the product of each combination, additionally checking whether the number was palindromic: def maxpal(): for i in reversed(range(100,1000)): # Since we only want unique combinations, we only # need to iterate up to i for j in reversed(range(100,i)): if str(i*j) == str(i*j)[::-1]: yield i*j print max(maxpal()) Note that the first list in the example iterates over factors in exactly the same order as this code. My initial assumption was that since I was iterating downwards, the first palindrome I found would be the largest one. This is clearly not the case, since j iterates all the way to 100 before i</co

Tags (comma-separated) Cancel