Разница между двумя ближайшими к нулю продуктами: без грубой силы?

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 

Если мы не допускаем ведущие нули, то это печатает 128 возможных решений в течение примерно 12 секунд.

Но я не знаю, есть ли алгоритм или лучший способ решить эту проблему не-грубой силой?

Answer 1

В качестве эвристики вы можете вычислить квадратный корень 12345 (около 111) и продолжить оттуда, ища ближайшие значения до 123 и 45, которые вы можете создать с остальными числами. Я не реализовал это, но это мог бы быть более разумный подход.

Другой пример:

SQRT (36189) -> О 190

Остальные номера: 24570

Попробуйте найти числа, близкие к 190, которые вы можете создать с этими номерами. Например, 70 и 245. Однако этого сложнее реализовать.

Расстояние между 361 * 89 и 245 * 70: 14979

Answer 2

Если предположить, что существует решение с разницей 0, вы можете сделать это с помощью простых множителей.

Если б - с г = 0, то простые множители в б и в д должны быть одинаковыми. Вы можете начать поиск, пройдя все 3-значные простые числа (их всего 143) и посмотрите, есть ли у них несколько, которые содержат только дизъюнктивные цифры. Если это так, у вас есть два трехзначных числа и нужно только проверить 2-значные цифры.

Если вы не нашли решение, продолжите с 2-значными штрихами и найдите 2-х или 3-значные кратные с дизъюнктными цифрами. Тогда вам нужно сделать только перестановки для остальных 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]); 
 
}