最接近零的两种产品之间的差异：非蛮力解决方案？ [英] Difference between two products nearest to zero: non brute-force solution?

问题描述

在挪威的

目标是将10位数字从0放置到9，以使差异两个产品之间的距离最接近零。 （246是当前最低的分数。）

回到家，我编写了以下蛮力代码：

 导入时间
从itertools导入排列
 
 
 def form_number（x，y，z，a，b）：
 ＃没有明确说明，但假定如果x == 0或a == 0则不允许前导零
：
返回0 
返回（（（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：]）
 
如果__name__ =='__main__'：
 start = time.time（）
 count = 0 $ b在排列中的排列的b $ b（range（10），10）：
结果= find_nearest_zero（* p）
如果结果== 0：
计数+ = 1 
打印'{} {} {} * {} {} = {n}'。format（* p [：5]，n = form_number（* p [：5]））
 print'{} {} { } * {} {} = {n}'。format（* p [5：]，n = form_number（* p [5：]））
打印
 pr int'找到{}解决方案'.format（count）
打印time.time（）-开始
  

如果我们不允许前导零，那么这将在约12秒内打印出128个可能的解决方案。

但是我不禁要问，是否有一种算法或

解决方案

该方法假定零差是可能的（尽管可以对它进行修改，方法是通过排序（谢谢m69），找到每一个最小值，每组120个排列，并使用二进制搜索，加上（log2 120）到时间复杂度）：散列所有 10的倍数，选择5 * 5！三位数乘以两位数的组合，其中键是排序的五位数的组合。然后，如果一个倒数键（包含其他五个数字的键）指向相等的倍数，则输出匹配的键。总共检查了30,240个组合。

JavaScript代码：

 函数select（ns，r）{var res = [];函数_choose（i，_res）{如果（_res.length == r）{res.push（_res）;返回; } 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 =;对于（var i = 0; i <= 9; i ++）{如果（str.indexOf（i）=== -1）{res + = i; }} return res;} var digitsHash = {};函数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  

In a science museum in Norway I came across the following mathematical game:

The goal is to place the 10 digits from 0 to 9 such that the difference between the two products is nearest to zero. (The 246 is the current lowest score).

Back home I wrote the following brute-force code:

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

If we don't allow leading zeroes, then this prints 128 possible solutions in about 12 seconds.

But I'm left wondering, is there an algorithm or a better way to solve this in a non-brute force way?

解决方案

This one assumes a difference of zero is possible (although it could be adapted to finding the minimum/s by sorting — thank you, m69, for that idea — each group of 120 permutations and using binary search, adding a factor of (log2 120) to the time complexity): hash the multiples for all 10 choose 5 * 5! combinations of three-digit times two-digit numbers, where the key is the sorted five-digit combination. Then if a reciprocal key (one that contains the other five digits) points to an equal multiple, output that match. Altogether 30,240 combinations are checked.

JavaScript code:

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]);
}

这篇关于最接近零的两种产品之间的差异：非蛮力解决方案？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！