两个最接近于零的产品之间的差异：非蛮力解决方案？

Question

在science museum in Norway我碰到下面的数学游戏：

我们的目标是将10个数字，从0到9，使得这两个产品之间的差异是最接近零。 （246是当前最低分数）。

回到家里我写了下面的蛮力代码：

import time 
from itertools import permutations 


def form_number(x, y, z, a, b): 
    # not explicitly stated, but presume that leading zeroes are not allowed 
    if x == 0 or a == 0: 
     return 0 
    return ((100 * x) + (10 * y) + z) * ((10 * a) + b) 

def find_nearest_zero(*args): 
    assert len(args) == 10 
    return form_number(*args[:5]) - form_number(*args[5:]) 

if __name__ == '__main__': 
    start = time.time() 
    count = 0 
    for p in permutations(range(10), 10): 
     result = find_nearest_zero(*p) 
     if result == 0: 
      count += 1 
      print '{}{}{} * {}{} = {n}'.format(*p[:5], n=form_number(*p[:5])) 
      print '{}{}{} * {}{} = {n}'.format(*p[5:], n=form_number(*p[5:])) 
      print 
    print 'found {} solutions'.format(count) 
    print time.time() - start 

如果我们不允许前导零，然后打印在约12秒128个可能的解决方案。

但我仍然想知道，有没有一种算法或更好的方式来解决这个非蛮力的方式？

Answer 1

作为一种启发式的，你可以计算12345（约111）的平方根，并从那里去，寻找最接近的数值为123和45，你可以用剩下的号码创建。我没有实现这个，但它可能是一个更聪明的方法。

又如：

的sqrt（36189） - >关于190

剩余数量：24570条

试图找到接近190，您可以用这些号码创建一个数字。如70和245.然而，这应该更难实施。

距离361和245之间的* 89 * 70：14979

Answer 2

如果假定有一个与差0的解决方案，您可以通过黄金的因素做。

如果b - c^ d = 0，则一b和c d的素因子必须是相同的。您可以通过检查所有3位数的素数（仅有143）开始搜索，并查看它们是否具有仅包含分隔数字的倍数。如果是这种情况，你有两个三位数字，只需要检查两位数字。

如果你没有找到一个解决方案，继续与2位的素数，然后寻找有间断的数字2或三分位数的倍数。那么你只需要对剩下的2个数字进行排列，这个数字要少得多。

Answer 3

12秒对我来说太过分了。我的C++强力攻击花了430毫秒，没有任何启发式或深度优化。无论如何，您需要添加一些启发式例如：

乘法结果的位宽大约等于操作数的位宽之和。

所以，你需要测试结果的唯一相同位宽的组合。例如，如果a*b是这样的：

1xx * 9x dec = 1 xxxx xxxx * 1001 xxxx bin -> 17 bit 

因此只测试c*d组合导致过例如17个结果

4xx * 2x dec = 100 xxxx xxxx * 10 xxxx bin -> 17 bit 

，使之更加明确：

dec bin bits 
0 0000 0 
1 0001 1 
2 0010 2 
3 0011 2 
4 0100 3 
5 0101 3 
6 0110 3 
7 0111 3 
8 1000 4 
9 1001 4 

如果a,b,c,d的最高位是a0,b0,c0,d0那么：

bits(a0)+bits(b0) = bits(c0)+bits(d0) 

这将消除很多迭代。它与子集和问题类似。加速从2177280迭代到420480迭代，但也增加了一些开销。

Answer 4

有126种方式将10个数字分成2组5个没有重复的数字。对于每组5位数字，有120种方式（置换）将它们排列成ab*cde的形式，或者如果组包含零并且不允许前导零，则可以使用72种方式。这意味着蛮力算法需要检查126 72 = 1,088,640种可能性。

但是，对于每对5位数的集合，如果按顺序生成排列，以便生成的产品从小到大排序，则可以在120 + 72 = 192步骤中找到最小的产品差异（或更少取决于范围重叠多少）而不是120 × 72 = 8640.最大总数变为24,192而不是1,088,640，这是45倍。
（实际上，只计算了12,574个产品差异，第一个零差异结果在6679步之后找到）。

您可以为每组采用最小产品的排列，计算它们的差异，如果它小于迄今为止发现的最小值，则将其存储。然后，用这个集合的列表中的下一个排列替换产品最小的排列（但保持对另一个集合的排列相同）并计算它们的差异，依此类推，直到你到达其中一个集。

在下面的JavaScript代码示例中，我将该产品用作稀疏数组（如可以按顺序读取的字典）的索引来创建排列及其产品的有序列表（因为我无法立即找到一个简单的方法来按顺序生成它们）。

Array.prototype.remove = function() {  // returns first element of sparse array 
 
    for (var key in this) { 
 
     if (!this.hasOwnProperty(key)) return false; 
 
     var value = this[key]; 
 
     delete this[key]; 
 
     return {prod: key, perm: value}; 
 
    } 
 
} 
 
function NorwegianMath() { 
 
    var div = [1,1,1,1,1,0,0,0,0,0];   // which numbers 0-9 go in set 0 or 1 
 
    var result, min = 99999; 
 
    while (div[0]) {     // keep zero in group 1 to avoid duplicates 
 
     var set = [[],[0]]; 
 
     for (var i = 1; i < 10; i++) set[div[i]].push(i); // distribute over sets 
 
     var dict = [[],[]]; 
 
     for (var i = 0; i < 2; i++) { 
 
      permute(set[i], dict[i]);   // generate permutations for each set 
 
     } 
 
     var x = dict[0].remove(), y = dict[1].remove();  // start with smallest 
 
     while (x && y) { 
 
      var diff = Math.abs(x.prod - y.prod); 
 
      if (diff < min) { 
 
       result = {x: x.perm, y: y.perm, d: diff};  // store new minimum 
 
       /* if (diff == 0) return result */  // possible early exit here 
 
       min = diff; 
 
      } 
 
      if (x.prod < y.prod) x = dict[0].remove(); 
 
      else y = dict[1].remove(); // replace smallest premutation with next 
 
     } 
 
     revLexi(div);      // get next distribution into 2 sets of 5 
 
    } 
 
    return result; 
 

 
    function permute(s, dict) {// there are better permutation algorithms out there 
 
     for (var a = 0; a < 5; a++) { 
 
      if (s[a] == 0) continue; 
 
      for (var b = 0; b < 5; b++) { 
 
       if (a == b) continue; 
 
       for (var c = 0; c < 5; c++) { 
 
        if (a == c || b == c || s[c] == 0) continue; 
 
        for (var d = 0; d < 5; d++) { 
 
         if (a == d || b == d || c == d) continue; 
 
         for (var e = 0; e < 5; e++) { 
 
          if (a == e || b == e || c == e || d == e) continue; 
 
          var p = (s[a]*10 + s[b]) * (s[c]*100 + s[d]*10 + s[e]); 
 
          dict[p] = "" + s[a] + s[b] + "*" + s[c] + s[d] + s[e]; 
 
         } 
 
        } 
 
       } 
 
      } 
 
     } 
 
    } 
 
    function revLexi(seq) {  // next binary sequence (reverse lexicographical) 
 
     var max = true, pos = seq.length, set = 1; 
 
     while (pos-- && (max || !seq[pos])) if (seq[pos]) ++set; else max = false; 
 
     if (pos < 0) return false; 
 
     seq[pos] = 0; 
 
     while (++pos < seq.length) seq[pos] = set-- > 0 ? 1 : 0; 
 
     return true; 
 
    } 
 
} 
 
var result = NorwegianMath(); 
 
document.write("|" + result.x + " - " + result.y + "| = " + result.d);

Answer 5

这一个假设的零差是可能的（虽然它可以适用于通过排序找到最小/秒 - 谢谢，M69，对于想法 - 每组的120置换和使用二分查找，在时间复杂度上增加一个因子(log2 120)）：散列三位数两位数字的所有10 choose 5 * 5!组合的倍数，其中密钥是排序的五位数组合。然后，如果一个相互键（包含其他五位数的键）指向一个相等的倍数，则匹配的输出。总共检查了30,240个组合。

JavaScript代码：

function choose(ns,r){ 
 
    var res = []; 
 
    
 
    function _choose(i,_res){ 
 
    if (_res.length == r){ 
 
     res.push(_res); 
 
     return; 
 
     
 
    } else if (_res.length + ns.length - i == r){ 
 
     _res = _res.concat(ns.slice(i)); 
 
     res.push(_res); 
 
     return 
 
    } 
 
    
 
    var temp = _res.slice(); 
 
    temp.push(ns[i]); 
 
    
 
    _choose(i + 1,temp); 
 
    _choose(i + 1,_res); 
 
    } 
 
    
 
    _choose(0,[]); 
 
    return res; 
 
} 
 

 
function missingDigits(str){ 
 
    var res = ""; 
 

 
    for (var i=0; i<=9; i++){ 
 
    if (str.indexOf(i) === -1){ 
 
     res += i; 
 
    } 
 
    } 
 
    
 
    return res; 
 
} 
 

 
var digitsHash = {}; 
 
    
 
function permute(digits){ 
 
    var stack = [[String(digits[0])]]; 
 
    
 
    for (var i=1; i<5; i++){ 
 
    var d = digits[i], 
 
     perms = stack.shift(), 
 
     _perms = []; 
 
    
 
    for (var j=0; j<perms.length; j++){ 
 
     var temp = perms[j]; 
 
    
 
     for (var k=0; k<=perms[0].length; k++){ 
 
     if (d == 0 && (k == 0 || k == 3)){ 
 
      continue; 
 
     } 
 
     var _temp = temp; 
 
     _temp = temp.split(""); 
 
     _temp.splice(k,0,d); 
 
     _temp = _temp.join("") 
 
     _perms.push(_temp); 
 
     } 
 
    } 
 
    
 
    stack.push(_perms); 
 
    } 
 
    
 
    var reciprocalKey = missingDigits(stack[0][0]), 
 
     key = stack[0][0].split(""); 
 

 
    key.sort(); 
 
    key = key.join(""); 
 

 
    digitsHash[key] = {}; 
 
    
 
    for (var i=0; i<stack[0].length; i++){ 
 
    var mult = Number(stack[0][i].substr(0,3)) * Number(stack[0][i].substr(3,2)); 
 
    
 
    digitsHash[key][mult] = stack[0][i]; 
 
    
 
    if (digitsHash[reciprocalKey] && digitsHash[reciprocalKey][mult]){ 
 
     console.log(stack[0][i].substr(0,3) + " * " + stack[0][i].substr(3,2) 
 
     + ", " + digitsHash[reciprocalKey][mult].substr(0,3) + " * " 
 
     + digitsHash[reciprocalKey][mult].substr(3,2)); 
 
    } 
 
    } 
 
} 
 

 
var fives = choose([1,2,3,4,5,6,7,8,9,0],5); 
 

 
for (var i=0; i<fives.length; i++){ 
 
    permute(fives[i]); 
 
}