Алгоритм переворачивания N элементов массива, чтобы получить сумму до нуля

Представьте, что у вас есть бухгалтерский отчет, состоящий из нескольких сотен строк со следующей структурой:

ID учетной записи Ценить. 1. -11775,61 2. -11538,40 3. 0,05 4. 26969,32 ... ... 500. 1354,25

Общая сумма в правильном отчете должна быть равна нулю, даже на цент.

Ошибка всегда возникает из-за того, что некоторые строки имеют неправильные знаки, поэтому нам нужно найти их и перевернуть знак.

Задача

Для заданного массива ненулевых сумм задача состоит в том, чтобы найти, в каких строках нужно поменять местами знаки, чтобы сумма стала равной 0. Правильный ответ — это массив значений, которые нужно поменять местами.

Особенности:

  • Сумма должна быть ровно нулевой. Это не алгоритм минимизации. Отсутствует на 0,01 и на 10000000,00 — это одинаково неправильно, но и не лучше.
    • -> это означает, например, что если несоответствие равно 102.04, то правильный ответ должен содержать хотя бы одно число с ненулевым вторым десятичным знаком, чтобы обнулить часть .04.
  • Количество возможных переворотов знаков ограничено. Допустим — правильный ответ — не более 10 бросков.
  • Чаще всего перевороты происходят островками/группами рядов, расположенных рядом друг с другом, а не случайным образом разбросанных. Пример перевернутых индексов строк: [1,2,3,4,400,402]
  • Алгоритм должен остановиться по истечении 1 секунды. Не найдено => мы показываем клиенту «Извините, мы не можем угадать»

Мои попытки

Я решил попросить совета здесь, так как чувствую себя немного потерянным в направлении своего исследования.

Я пробовал решение sort + bruteforce:

  • Сортировать строки по разнице между общим несоответствием и числом
  • Грубая сила с использованием битовой маски, такой как 0001 0010 0011, что означает «Попробуйте перевернуть строку 1», «Попробуйте перевернуть строку 2», «Попробуйте перевернуть строки 1 и 2» и т. д. — потому что, учитывая, что они обычно идут в виде групп/островов, я не Не хочу ни в ширину, ни в глубину.

Это работает во многих случаях, но не работает, когда есть 2 острова или 1 остров и 1-2 ряда выбросов далеко от исходного острова.

Исследовать

В общем, я нашел SSP и много разных алгоритмов, но, очевидно, O(2^(n/2)) на 500 строк — непосильная задача. Я обнаружил, что, учитывая, что это фрагмент JS, который нужно запустить в браузере клиента — чтобы время вычисления составляло менее 1 секунды, алгоритм может попробовать ~ 2 ^ 22 комбинации, прежде чем он должен остановиться.

Я еще не пробовал использовать методы динамического программирования для достижения псевдополиномиального времени здесь.

Ожидания

У меня такое ощущение, что с учетом этих очень специфических ограничений на задачу выше — должно быть что-то попроще.

Правильные ответы всегда 1-2 острова + 1-2 выброса, никогда ничего сложного. 99% случаев — 5-6 подбрасываний решают сумму. Таким образом, «10 бросков» — это наихудший случай, на самом деле в среднем это ~ 5.

Как будто должен быть какой-то конкретный подход, который мне не хватает, который мог бы резко снизить среднюю сложность случая, используя эти ограничения.

Может быть, я ошибаюсь.

Хотя я не знаю, какой алгоритм может быть лучшим, я могу сказать вам, что первый «конкретный» означает, что вы не можете использовать арифметику с плавающей запятой. Хоть есть над чем подумать для реализации.

Some programmer dude 10.02.2023 11:14

О да, вы абсолютно правы. В моем текущем и любом будущем алгоритме я сначала конвертирую все в центы и оперирую целыми числами.

John A 10.02.2023 12:29

Насколько большим может быть остров?

btilly 10.02.2023 16:41

Обычный остров ~3-4 ряда. До, скажем, 10 макс. Иногда встречаются островки «с дырками», напр. [1,2,3,4,500,502,503] — два острова [1,4], [500,503], но 501 не хватает.

John A 10.02.2023 22:14

Мы можем упростить такие задачи, говоря, что это два острова [1,4] и [502,503] с [500] в качестве единственного выброса. Но вообще под «островами» я подразумеваю не то, что они обязательно строго соприкасаются, а то, что ошибки концентрируются вокруг конкретных точек притяжения.

John A 10.02.2023 22:18
Структурированный массив Numpy
Структурированный массив Numpy
Однако в реальных проектах я чаще всего имею дело со списками, состоящими из нескольких типов данных. Как мы можем использовать массивы numpy, чтобы...
T - 1Bits: Генерация последовательного массива
T - 1Bits: Генерация последовательного массива
По мере того, как мы пишем все больше кода, мы привыкаем к определенным способам действий. То тут, то там мы находим код, который заставляет нас...
Что такое деструктуризация массива в JavaScript?
Что такое деструктуризация массива в JavaScript?
Деструктуризация позволяет распаковывать значения из массивов и добавлять их в отдельные переменные.
3
5
102
4
Перейти к ответу Данный вопрос помечен как решенный

Ответы 4

Сравнение с суммой подмножества

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

Однако, учитывая общий (ограничения на) вид решения, мы можем найти решение, которое обычно позволяет найти решение за разумное время.

Ограниченное решение

Во-первых, вы должны использовать целые числа, представляющие центы (путем умножения на 100), чтобы нам не приходилось иметь дело с плавающей запятой.

Теперь мы можем вычислить и сохранить каждое значение, которое мы можем получить, используя не более двух значений. Это всего 500^2 комбинаций, что достаточно быстро. Мы храним их в структуре данных, которая позволяет выполнять поиск O(1), например, в хэш-карте, а также храним используемые нами индексы.

Затем мы перебираем все смежные «острова» не более, скажем, размера 10. Их около 10 * 500, что все еще не проблема. Вы можете даже полностью ослабить это ограничение и просто просмотреть все ~500*500/2 островов. Мы вычитаем сумму этих островов из целевого числа, чтобы найти количество, которое нам еще нужно перевернуть, и проверяем хэш-карту, возможно ли получить это значение не более чем с двумя строками. Если это так, нам, наконец, нужно проверить, включены ли последние строки в остров, и в этом случае отклонить решение.

Эта стратегия позволяет эффективно искать все возможные комбинации островка и одного или двух случайных переворотов.

Поскольку нет необходимости делать определенное количество переворотов, мы можем хранить только минимальное количество переворотов, необходимое для создания суммы до i-го элемента,

for each element:
  for each sum stored in the previous round:
    if the number of its flips is less than 10:
      make a new record of sum with flipped value
      if this sum can now be associated with
      less flips, update that
    make a new record of sum with given value
    if this sum can now be associated with
    less flips, update that
    

Не забывайте, что мы хотим найти решение, а не просто знать, что оно существует.

btilly 10.02.2023 17:52

@btilly, конечно, просто добавьте элемент в единый список, который отслеживает, какой именно путь привел к минимальным переворотам для суммы.

גלעד ברקן 10.02.2023 19:11

Я пробовал динамическое программирование. Производительность... не такая, как хотелось бы. Проблема в том, что комбинаторный взрыв возможностей происходит слишком быстро.

Но если у вас всего 2-3 группы флипов, может быть достаточно следующего?

function findFlips (accounts) {
  for (let i = 0; i < accounts.length; i++) {
    accounts[i]['cents'] = Math.round(accounts[i].value * 100);
  }

  let sum = accounts.reduce((a, b) => a+b.cents, 0);
  // -2 is a hack to make the start of the next group be 0.
  const start = {"sum": sum, "flips": 0, "i": -2, "decisions": 0, "prev": null};
  let best = {}
  best[start.sum] = [start];
  let todo = [start];

  let d = new Date;
  let startTime = d.getTime();
  let count = 0;

  while (0 < todo.length) {
    let current = todo.shift();
    if (current.sum == 0) {
      let answer = [];
      while (current.prev != null) {
        answer.unshift(current.i);
        current = current.prev;
      }
      return answer;
    }

    // Did we take too long?
    count++;
    if (0 == count%10000) {
      d = new Date;
      if (999 < d.getTime() - startTime) {
        return null;
      }
    }

    for (let i = current.i+2; i < accounts.length; i++) {
      let next = {
        "sum": current.sum - 2*accounts[i].cents,
        "flips": current.flips + 1,
        "i": i,
        "decisions": current.decisions+1,
        "prev": current};
      let j = i;
      while (j < accounts.length && next.flips < 11 && next.decisions < 5) {
        let existing = (best[next.sum] || [])
        let k = 0;
        while (k < existing.length) {
          if (existing[k].i <= next.i && existing[k].flips <= next.flips) {
            break;
          }
          k++;
        }
        if (k == existing.length) {
          existing.push(next);
          best[next.sum] = existing;
          todo.push(next);
        }
        j++;
        if (j < accounts.length && j < i + 4) {
          let next2 = next;
          next = {
            "sum": next2.sum - 2*accounts[j].cents,
            "flips": next2.flips + 1,
            "i": j,
            "decisions": next2.decisions,
            "prev": next2};
        }
      }
    }
  }
  return null;
}

let accounts = [
  {'accountId': 1, 'value': 24.12},
  {'accountId': 2, 'value': 128.16},
  {'accountId': 3, 'value': -545.43},
  {'accountId': 4, 'value': 191.92},
  {'accountId': 5, 'value': 238.01},
  {'accountId': 6, 'value': -500.36},
  {'accountId': 7, 'value': -81.22},
  {'accountId': 8, 'value': 132.50},
  {'accountId': 9, 'value': 246.80},
  {'accountId': 10, 'value': 93.80},
  {'accountId': 11, 'value': 389.00},
  {'accountId': 12, 'value': -331.00},
  {'accountId': 13, 'value': -332.00},
  {'accountId': 14, 'value': 321.00},
  {'accountId': 15, 'value': 321.06},
  {'accountId': 16, 'value': -336.04},
  {'accountId': 17, 'value': -491.02},
  {'accountId': 18, 'value': -119.06},
  {'accountId': 19, 'value': 245.69},
  {'accountId': 20, 'value': 404.07},
];

console.info(findFlips(accounts));
// Do some flips.
[2, 3, 11, 18].forEach((i) => accounts[i].value = - accounts[i].value);

console.info(findFlips(accounts));

accounts[2].value += 0.03;
console.info(findFlips(accounts));
Ответ принят как подходящий

Я думаю, что подход с растровым изображением хорош, в том смысле, что в ограниченной области вы бы посмотрели все комбинации включения-выключения для перелистывания.

Чтобы поддерживать два таких острова, сохраните эффект каждой конфигурации острова в карте с ключом этой разницы сумм и, связанный с этим ключом, сохраните крайний левый индекс этого острова вместе с флип-битмап.

Конечно, если какой-либо из этих островов решит проблему, верните это решение.

Если нет, то повторите эти острова и определите, с какой суммой вам нужно их объединить, чтобы получить нулевую сумму. Найдите на карте эту недостающую сумму (которая должна быть ключом на этой карте). Если найдено, вы объединяете два местоположения и возвращаете этот результат.

Следует проявлять некоторую осторожность, чтобы не объединять два перекрывающихся острова, поскольку вы всегда найдете эквивалентную комбинацию, где острова не пересекаются.


Чтобы продемонстрировать эту идею, я создал функцию, которая создает случайный массив из 500 значений в диапазоне (-100 000,...,100 000) и применяет максимальное количество подбрасываний не более чем к 2 островам. Я определил «остров» как набор флипов, где два крайних индекса отстоят друг от друга не более чем на 12. Так, например, остров может состоять из 12 последовательных бросков, или может быть 2 бросков с индексами 3 и 15, или любым промежуточным вариантом.

Приведенная ниже демонстрация будет продолжать создавать новые данные и вычислять для них решение. Если решение не может быть найдено в течение 1 секунды (чего никогда не случалось на моем ПК), или решение не может быть найдено не более чем с двумя островками, вывод «не найден». В противном случае это массив с индексами, где должны применяться флипы.

Каждый раз решение проверяется путем фактического суммирования сумм с учетом переворотов и утверждения, что эта сумма равна нулю.

Вот фрагмент, который продолжает запускать случайные тесты:

const randint = (end) => Math.floor(Math.random() * end);

function randomInput(size, maxFlips, maxIslands) {
    let amounts = [];
    let sum = 0;
    while (size-- > 1) {
        let amount = (Math.floor(Math.random() * 2e7) - 1e7) / 100;
        amounts.push(amount);
        sum += amount;
    }
    // Make sum zero
    while (Math.abs(sum) >= 100000) {
        let i = randint(amounts.length);
        if (amounts[i] * sum > 0) {
            sum -= amounts[i] * 2;
            amounts[i] = -amounts[i];
        }
    }
    amounts.push(-Math.round(sum * 100) / 100);

    // Prepare islands
    let islands = Array(maxIslands).fill(0);
    // Determine size of each island (could remain 0)
    while (maxFlips-- > 0) {
        islands[randint(maxIslands)]++;
    }
    // Apply the flips (could occasionally overlap, making the problem simpler)
    for (let count of islands) {
        let i = randint(amounts.length - count + 1);
        while (count-- > 0) {
            // 80% probability that amount is flipped; so we may get holes in islands
            if (randint(100) < 80) {
                amounts[i + count] = -amounts[i + count]; // Flip!
            }
        }
    }
    return amounts;
}

function solve(amounts) {
    let deadline = performance.now() + 900;
    const map = new Map;
    
    function memo(sum, loc) {
        if (map.has(sum)) map.get(sum).push(loc);
        else map.set(sum, [loc]);
    }

    function recur(i, j, bits, width, sum) {
        if (width == 0) return memo(sum, [i, bits]);
        recur(i, j + 1, bits * 2, width - 1, sum);
        recur(i, j + 1, bits * 2 + 1, width - 1, sum + amounts[j]*2);
    }
    
    function expand([i, bits]) {
        return Array.from(bits.toString(2), (bit, j) => +bit ? i + j : -1)
                    .filter(i => i >= 0);        
    }

    // Convert to cents
    amounts = amounts.map(val => Math.round(val * 100));
    
    let sum = amounts.reduce((a, b) => a + b);
    if (sum == 0) return []; // No flips
    
    const WIDTH = 12;
    // Collect islands with at least one flip (at i)
    for (let i = 0; i < amounts.length; i++) {
        recur(i, i + 1, 1, WIDTH - 1, amounts[i]*2);
    }
    // Solution with one island?
    if (map.has(sum)) return expand(map.get(sum)[0]);
    // Look for solutions with two islands...
    for (let [sum1, islands] of map) {
        if (map.has(sum - sum1)) {
            for (let [i, bits1] of map.get(sum - sum1)) {
                for (let [j, bits2] of islands) {
                    if (i >= j + WIDTH) return expand([j, bits2]).concat(expand([i, bits1]));
                    else if (j >= i + WIDTH) return expand([i, bits1]).concat(expand([j, bits2]));
                }
            }
        }
        if (performance.now() >= deadline) break;
    }
    return "not found";
}

function verify(amounts, flips) {
    let sum = Math.round(amounts.reduce((acc, val, i) => acc + Math.round(100*val) * (flips.includes(i) ? -1 : 1), 0));
    if (sum != 0) {
        console.info("amounts", JSON.stringify(amounts));
        console.info("flips", JSON.stringify(flips));
        throw "Wrong solution detected! sum = " + sum;
    }
}

// I/O handling
const input = document.querySelector("textarea");
const [output, time] = document.querySelectorAll("span");
const pause = document.querySelector("input");
let pausing = false;

setInterval(function repeat() {
    if (pausing) return;
    const amounts = randomInput(500, 12, 2);
    const start = performance.now();
    const flips = solve(amounts);
    time.textContent = Math.ceil(performance.now() - start);
    verify(amounts, flips);
    
    input.value = amounts;
    output.textContent = flips;
}, 1000);

pause.onchange = () => pausing = pause.checked;
textarea { width: 100%; height: 6em }
500 amounts: <textarea readonly></textarea><br>
Flips found: <span></span><br>
Time elapsed: <span></span> ms<br>
<input type = "checkbox">Pausing

Обратите внимание, что новый тест выполняется каждую секунду. Это не то время, которое требуется для получения результата. Время, необходимое для обработки, отображается в выходных данных.

Во-вторых, решений часто много. Этот алгоритм не ищет решение, требующее наименьшего количества переворотов, хотя он отдает предпочтение решениям с одним островком. Но поскольку часто бывает много решений, решение часто будет включать самый первый индекс, так как этот индекс включен в первые островки, которые сначала объединяются со всеми остальными островками.

Это оказалось лучшим решением для моего случая, и у него очень приличная частота предположений на реальных примерах, которые у нас есть.

John A 11.02.2023 21:36

Другие вопросы по теме