возможные комбинации без нулей

Question

Итак, я ищу способ получить возможные комбинации двух целых чисел из массива, скажем, у меня есть

v = [0, 1, 2, 0, 4]

В конце я хотел бы получить концептуальную матрицу, подобную этой: C = v ^ T v, где v ^ T - транспонирование вектора, поэтому вы получите матрицу с несколькими ненулевыми значениями, а записи будут представлять собой комбинации двух целых чисел. , Например, для строки 1:

(0,0) (1,1) (1,2) (0,0) (0,4)

но мне нужно только (1,1) (1,2), и аналогичные рассуждения верны и для других строк в моей концептуальной матричной визуализации. Я могу сделать это с помощью двух вложенных циклов, проверив, содержат ли они 0 или нет. Вопрос в том, существуют ли какие-нибудь алгоритмы для такого рода комбинаторных задач, которые справились бы с этим лучше, чем вложенные циклы?

Answer 1

Нет способа генерировать эту выходную «матрицу» без двухмерного вложенного цикла (или чего-то прямо эквивалентного).Так что, учитывая, что у вас все равно будут циклы, добавить условную проверку тривиально.

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

Answer 2

В зависимости от того, сколько у вас нулей, вы можете использовать разреженную матричную структуру данных , и это может уменьшить проблему с O (n ^ 2) до чего-то немного меньшего (в зависимости от того, сколько у вас нулей) ).

Если вы игнорируете нули в течение секунды, N выбирает 2 комбинации, равные n ^ 2/2-n / 2 комбинациям. Точно так же есть n * (n-1) 2-перестановки n. Поэтому независимо от того, выполняете ли вы комбинации или перестановки, вам все равно нужен алгоритм, который является худшим случаем O (n ^ 2). Обратите внимание, что ваша матрица, возможно, будет симметричной в зависимости от определенных предположений, но этого будет недостаточно, чтобы изменить ее с O (n ^ 2), потому что по существу это будет O ((n / 2) ^ 2), который по-прежнему равен O (n ^ 2).