Итерация по парам чисел в возрастающем порядке

Ответ 1

Эта проблема отличается только поверхностно от сортировки X + Y, основного раздражителя для вычислительных геометров на протяжении многих лет. (См. Joseph O & rsquo; Rourke & rsquo; s (open) Проблема 41.) Подводя итог этой ссылке для исполнителей, самый быстрый из известных алгоритмов, когда экспоненты могут быть добавлено и сравнивается только O (mn log (mn)), и это очевидно. Если показатели являются ограниченными целыми числами, то применяется подход Peter & rsquo; s Fourier. Многие умные люди долго думали об этой проблеме, поэтому я бы не ожидал лучшего алгоритма в ближайшее время.

Ответ 2

Интересно, насколько ожидаются ваши многочлены?

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

Это позволяет вам умножать полиномы в O (nlogn), где n - степень многочлена.

Это не подходит для разреженного многочлена, такого как (1 + x ^ 1000000) * (1 + x ^ 1000000), поскольку n будет около 1000000, тогда как для текущего алгоритма потребуется всего несколько циклов.

Хорошее объяснение этого подхода Фурье можно найти в этих примечаниях к лекции.

Ответ 3

Насколько я понимаю, вы даже не можете надеяться на решение со сложностью O(N*M) из-за следующей логики.

Скажем, что массивы (a1, a2, a3, a4) и (b1, b2, b3, b4, b5)

Возможные пары должны быть следующими:

a1b1 a1b2 a1b3 a1b4 a1b5
     a2b1 a2b2 a2b3 a2b4 a2b5
          a3b1 a3b2 a3b3 a3b4 a3b5
               a4b1 a4b2 a4b3 a4b4 a4b5

Теперь для каждой строки пары слева всегда должны быть подняты перед парами справа.

• Итак, первый кандидат a1b1.
• Затем один раз a1b1 выбирается, следующие кандидаты a1b2 и a2b1.
• Скажите a1b2. Тогда кандидаты a1b3 и a2b1.
• Теперь скажите a2b1. Тогда кандидаты a1b3, a2b2 и a3b1.

Следовательно, мы видим, что по мере продвижения вперед число кандидатов в позицию увеличивается линейно.

Следовательно, в худшем случае вам придется выполнять сравнения порядка N*M*M.

An O(N*Mlog(M*N)). (where N = a.size() and M = b.size())

for ( int i = 0; i < a.size(); i++ )
  for ( int j = 0; j < b.size(); j++ )
    sumVector.push_back( a[i] + b[j] );

sort( sumVector ); // using merge sort or quicksort.

Ответ 4

Я надеюсь, что это возможно сохранить только постоянное количество состояний и только итерации по каждому списку один раз.

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

1) Сформировать все пары из A и B. 2) Убедитесь, что они находятся в порядке возрастания суммы.

Опустите вторую часть, чтобы сделать ее проще. Самый простой способ реализовать это:

foreach a in A:
  foreach b in B:
    emit (a, b)

Надеюсь, вы согласитесь, что не может быть более эффективного способа сделать это. Но здесь мы уже итерации по длине B (A) раз.

Итак, минимальная временная сложность для этого - O (A * B), но вы хотите O (A + B).

Ответ 5

Очень просто использовать алгоритм для поиска пары чисел в отсортированном массиве, которые суммируются с определенной константой K, как описано в этом вопросе.

Резюме

Окончательное решение будет иметь временную сложность O((M+N)*(M+N)), которая в 4 раза хуже, чем нижняя граница M*N (просто выводя все пары). Таким образом, постоянный коэффициент равен всего 4.

Изменить. К сожалению, это не O((M+N)*(M+N)), как я думал, по-видимому, это O(K*(M+N)), где K - самая высокая сумма в двух массивах. Я не уверен, можно ли улучшить этот алгоритм, но похоже, что это решение будет аналогично методу быстрого преобразования Фурье, описанному Питером де Ривазом.

Сумма в алгоритме отсортированного массива

В этом алгоритме мы устанавливаем нижний указатель на 0 и более высокий указатель на конец массива. Тогда, если сумма в этих двух положениях больше, чем K, мы уменьшаем более высокий указатель. Если он ниже, мы увеличиваем нижний указатель. Это работает, потому что на любой итерации arr[low] - это самый нижний элемент, с которого может быть получен ответ. Точно так же arr[high] является наивысшим. Поэтому, если мы берем наименьший и самый высокий элементы, а сумма больше, чем K, мы знаем, что любая другая комбинация с arr[high] будет больше, чем K. Поэтому arr[high] не может быть частью какого-либо решения. Поэтому мы можем удалить его из нашего массива (это достигается путем уменьшения указателя high).

Применив это к вашей проблеме

Применяя это для вашей проблемы, идея состоит в том, что мы перебираем возможную сумму, от 0 до A[len(A)-1]+B[len(B)-1]. И для каждой возможной суммы мы запускаем приведенный выше алгоритм. Для вашей проблемы мы устанавливаем нижний указатель на массив A и более высокий указатель на массив B.

Для исходного алгоритма он сломается, как только найдет пару, которая суммируется с константой. Для вашей проблемы вы увеличите ptr_A и уменьшите ptr_B каждый на 1. Это работает, потому что ваш массив строго увеличивается. Итак, если мы найдем A[ptr_A]+B[ptr_B]==K, то A[ptr_A]+B[low_B]<K для всех low_B<ptr_B и A[high_A]+B[ptr_B]>K для всех high_A>ptr_A.

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

В качестве бонуса этот алгоритм будет сортировать результат на основе возрастающего значения в списке A (вы можете сортировать на основе увеличения значения в списке B путем замены указателей), и что нам не нужен случайный доступ к массиву.

Код в Python

Реализация в Python:

def pair_sum(A,B):
    result = []
    max_sum = A[-1]+B[-1]
    for cur_sum in range(max_sum+1): # Iterate over all possible sum
        ptr_A = 0        # Lower pointer
        ptr_B = len(B)-1 # Higher pointer
        while True:
            if A[ptr_A]+B[ptr_B]>cur_sum:
                ptr_B -= 1
            elif A[ptr_A]+B[ptr_B]<cur_sum:
                ptr_A += 1
            else:
                result.append((A[ptr_A],B[ptr_B]))
                ptr_A += 1
                ptr_B -= 1
            if ptr_A==len(A):
                break
            if ptr_B==-1:
                break
    return result

def main():
    print pair_sum([0,1,2],[1,4])
    print pair_sum([0,1],[0,1])
    print pair_sum([0,1,3],[1,2])

if __name__=='__main__':
    main()

напечатает:

[(0, 1), (1, 1), (2, 1), (0, 4), (1, 4), (2, 4)]
[(0, 0), (0, 1), (1, 0), (1, 1)]
[(0, 1), (0, 2), (1, 1), (1, 2), (3, 1), (3, 2)]

по желанию.

Ответ 6

Итак, возьмите два "пугающих массива" sA и sB, которые содержат только цифры, отличные от нулевой степени/коэффициенты, как описано в исходном сообщении.
Пример:

A   =  x^5 + 3*x^2 + 4
sA  = [ 5, 1, 2, 3, 0, 4 ]

B = 2*x^6 + 5*x^3 + 8*x
sB = [ 6, 2, 3, 5, 1, 8]

Я предлагаю сделать операцию так, как мы это сделаем вручную, поэтому они занимают время в m * n, где m, n - количество ненулевых коэффициентов, а не в p * q, где p и q - степени A, B.
Поскольку вы сказали, что m и n малы, m * n не имеет большого значения.
Чтобы сохранить коэффициенты при вычислении, используйте либо разреженный массив (может быть, дорогостоящий), либо хеш-таблицу. индекс или ключ - это степень, а значение - соответствующий коэффициент.
Вот пример реализации в javascript, используя хеш-таблицу:

http://jsbin.com/ITIgokiJ/2/edit?js,console

один пример:

A     =   "x^5+3x^2+4"
B     =   "2x^6+5x^3+8x^1"
A * B =   "2x^11+11x^8+16x^6+15x^5+44x^3+32x^1"

код:

function productEncodedPolynoms( sA, sB) {
   var aIndex = 0 ;
   var bIndex = 0 ;
   var resIndex = 0 ;
   var resHash = {} ;
   // for loop within sA, moving 2 items at a time
   for (aIndex = 0; aIndex < sA.length ; aIndex+=2) {
       // for loop within sB, moving 2 items at a time
       for (bIndex = 0; bIndex < sB.length ; bIndex+=2 ) {
           resIndex = sA[aIndex]+sB[bIndex] ;
           // create key/value pair if none created
           if (resHash[resIndex]===undefined)  resHash[resIndex]=0;
           // add this product to right coefficient
           resHash[resIndex] += sA[aIndex+1]*sB[bIndex+1];
       }
   } 
   // now unpack the hash into an encoded sparse array
   // get hash keys
   var coeff = Object.keys(resHash);
   // sort keys in reverse order
   coeff.sort(reverseSort);
   encodedResult = [];
   for (var i=0; i<coeff.length; i++ ) {
     if (resHash[coeff[i]]) {
       encodedResult.push(+coeff[i]);          // (+ converts to int)
       encodedResult.push(+resHash[coeff[i]]);
     }
   }
   return encodedResult;
}

пример:

sA = [ 5, 1, 2, 3, 0, 4 ] ;

sB = [ 6, 2, 3, 5, 1, 8] ;

sAB = productEncodedPolynoms ( sA, sB );

утилита для печати результата:

function printEncodedArray(sA) {
  res='';
  for (var i=0; i<sA.length; i+=2) {
    if (sA[i+1]) {
        if (sA[i+1] != 1 || sA[i]==0) res+=sA[i+1];
        if (sA[i]!=0) res+='x^'+sA[i];
        if (i!=sA.length-2) res+='+';
    }
  }
  return res;
}

// utilities
function reverseSort(a,b) { return b-a ; }

Ответ 7

Почему бы вам просто не создать несортированный 2-й массив, а затем использовать quicksort?

ED: Похоже, если вы сформировали окончательный массив предельно разумно (используя сравнительный алгоритм во время начальной итерации и генерации массива), вы могли бы позже использовать более конкретный алгоритм сортировки (например, smoothsort) и в конечном итоге достичь производительности, приближающейся к O ( 2 (m * n)) с худшим случаем O (m * n + (m * n) log (m * n))

ED2: Я абсолютно уверен, что вы можете написать алгоритм для этого в O (m * n). То, что вы хотите сделать, это генерировать массив чисто. У меня нет времени писать псевдокод, но если бы вы были 1. Настройте минимальный-итератор, максимальный итератор и текущий-итератор для каждого из массивов, а также сумму current-max-sum для них. 2. Создать первую пару 3. Итерируйте одну переменную, сравните ее с другой возможной третьей парой (сохраните ее во временной переменной) и либо сохраните ее на выходе, либо сохраните другой массив на выходе и запустите снова.

То, как я представляю, это два ряда блоков с тремя цветами: красный для полностью законченного, синий для "самого высокого до сих пор" и незавершенный. Вы работаете над одной из строк блоков за раз, генерируя следующее значение для массива результатов, всегда сравнивая комбинаторную линию базовой линии с текущей стороной, которая ниже текущей суммы обработки. Каждый раз, когда сумма меньше, вы устанавливаете новый самый низкий результат в результат, который вы только что вычислили, добавляете предыдущий результат к вашему (уже отсортированному) выходному массиву и начинаете сбрасывать с использованием предыдущего минимума (и его строки) в качестве базовой линии, Никогда не возвращайтесь в красные блоки и не прокручивайте, какая сторона синей, каждый раз, когда вы находите новый противоположный уровень.

Вы никогда не должны рассчитывать один результат дважды и выходить с отсортированным массивом.

Это, по сути, пузырьковый вид с плавающей точкой. Вы знаете, что вычисленное значение выше вашей текущей суммы, и пока вы не обработаете нижние регистры в массиве. Когда он больше не выше, вы переключаете верхнее значение вверх и возвращаетесь к точке, в которой вы выполняете итерацию через массив, чьи члены в настоящее время меньше. EX:

A: (1 5 10)

B: (1 6 9)

(1, 1) → (1, 6) выше (1, 5), поэтому добавьте (1, 5), сделав (1, 6) наивысшим

(5, 6) выше, чем (1, 6), так что добавьте (1, 6), сделайте (5, 6) самым высоким шагом до (1, 9)

(1, 9) ниже, чем (5, 6), поэтому [добавьте (1, 9) и закончите на A]

Текущий массив: (1, 1), (1, 5), (1, 6), (1,9)

(1, 10), равный (5,6), так что добавьте оба, увеличив законченный на B, начните с (5,9)

(5, 9) выше, чем (10, 1), поэтому добавьте (10, 1) максимум (5, 9) вверх до (10, 6)

(10, 6) выше, чем (5, 9), поэтому....

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