Сумма всех возможных пар элементов в массиве

Я пытался решить проблему, где задан массив целых чисел, мне нужно найти сумму всех возможных пар элементов в заданном массиве. Например, массив равен 1,2,3,4 , тогда он должен давать 1 + 2 + 1 + 3 + 1 + 4 + 2 + 3 + 2 + 4 + 3 + 4 = 30Сумма всех возможных пар элементов в массиве

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

источник

2015-02-18 Rohit Vyavahare

Я не знаю, как этот вопрос связан с программированием, попробуйте math.stackexchange.com – Chiel

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

Для решения, которое не является O (n^2), должны быть дополнительные ограничения (т. Е. Элементы в массиве являются смежными целыми числами и т. Д.)? –

Поскольку каждый элемент массива происходит ровно n-1 пар, сумма всех их вверх и умножить на n-1, что означает, что это O(n).

Это фактически обобщает на случай, когда вам нужна сумма сумм всех k-элементов мультимножеств. В этом случае каждый элемент массива отображается точно в (n-1) choose (k-1) мультисетах, поэтому добавьте их все и умножьте на это. Вычисление биномиального коэффициента может стать немного значительным в какой-то момент, но, безусловно, будет означать перечисление всех мультисетей k-элементов и их добавление.

источник

2015-02-18 23:42:12

@G. Бах благодарит вас за ответ. Это именно то, что я искал. –

-1

Если вы ничего не знаете о значениях в массиве, я не вижу никакого способа сделать это, а не O (n^2).

Количество комбинаций N элементов, взятых 2 одновременно является:

N   C 
10   45 
100  4950 
1000 499500

Как вы можете видеть, количество комбинаций составляет приблизительно (N^2)/2, так что я не вижу, как вы можете сделать лучше, чем без дополнительной информации.

источник

2015-02-18 23:42:17

-1

В C++ существует функция, называемая next_permutation(), которая генерирует следующую «комбинацию» элементов в массиве. Таким образом, вы можете сделать что-то вроде этого:

int A=[1,2,3,4,5]; 
while(next_permutation(A,A+5)) //NOTE: A is pointer to first element of array A 
{ 
    // do something 
}

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

источник

2015-02-18 23:43:15 Dominik

Сумма всех возможных пар элементов в массиве

ответ

Смежные вопросы