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

Ответ 1

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

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

Если вы не нашли решение, продолжайте с 2-значными штрихами и посмотрите на 2-х или 3-значные кратные с дизъюнктными цифрами. Тогда вам нужно сделать только перестановки для остальных 2 чисел, что намного меньше.

Ответ 2

Это предполагает, что возможна разность нуля (хотя она может быть адаптирована к нахождению минимума /s путем сортировки - спасибо, 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]);
}

Ответ 3

12 секунд слишком много для моего вкуса. Моя атака грубой силы С++ заняла ~ 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, но также добавляет некоторые накладные расходы.

Ответ 4

Существует 126 способов разделить 10 цифр на 2 набора из 5 без дубликатов. Для каждого набора из 5 цифр существует 120 способов (перестановок), чтобы упорядочить их в форме ab*cde или 72 способах, если группа содержит нуль, а начальный ноль не разрешен. Это означает, что алгоритм грубой силы должен проверять 126 & times; 120 и раз; 72 = 1 088 640 возможностей.

Однако для каждой пары наборов из 5 цифр, если вы создаете перестановки в порядке, чтобы результирующие продукты упорядочивались от малого к большому, вы можете найти наименьшую разницу продуктов в 120 + 72 = 192 шага ( или меньше, в зависимости от того, насколько диапазоны перекрываются) вместо 120 & times; 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);

Ответ 5

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

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

sqrt (36189) → Около 190

Оставшиеся числа: 24570

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

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