Комбинированный алгоритм из множества множеств

Question

Я пытаюсь написать алгоритм, который говорит мне, сколько пар я мог бы генерировать с элементами, поступающими из нескольких наборов значений. Например, у меня есть следующие наборы: {1,2,3} {4,5} {6}

Из этих наборов я могу сгенерировать 11 пар: {1,4}, {1,5}, {1,6}, {2,4}, {2,5}, {2,6}, {3,4}, {3,5}, {3,6}, {4,6}, {5 , 6}

Я написал следующий алгоритм:

int result=0; 

for(int k=0;k<numberOfSets;k++){ //map is a list where I store all my sets 
    int size1 = map.get(k); 

    for(int l=k+1;l<numberOfSets;l++){ 
     int size2 = map.get(l); 
     result += size1*size2; 
    } 
} 

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

Большое спасибо заранее

Answer 1

Сначала вообще, если порядок в паре имеет значение, то, начиная с int l=k+1 во внутреннем цикле, является ошибочным. Например. вам не хватает {4,1}, если вы считаете, что с {1,4}, тогда правильный результат, в противном случае это не так.

Во-вторых, чтобы усложнить вопрос дальше, вы не говорите, должны ли пары быть уникальными или нет. Например. {1,2} , {2,3}, {4} будет генерировать {2,4} дважды - если вам нужно считать его уникальным, результат вашего кода неверен (и вам нужно сохранить Set<Pair<int,int>> для удаления дубликатов и вам нужно будет сканировать эти наборы и фактически генерировать пары).

Хорошая новость: в то время как вы не можете сделать лучше, чем O (N 2 ) только для подсчета пары, даже если у вас есть тысячи наборов, миллионы интегрального умножения/добавления достаточно быстро на теперешних компьютерах - например Eigen deals quite well with O(N^3) operations для плавающие умножения (см. операции умножения матрицы).

Answer 2

Предполагая, что вы заботитесь только о количестве пар, и подсчет дубликатов, то есть более эффективный алгоритм:

Мы будем отслеживать текущее количество наборов, а число элементов, которые мы столкнулись так далеко.

1. Перейти по списку от конца к началу
2. Для каждого нового набора, число новых пар, мы можем сделать это размер множества * размером встречающихся элементов. Добавьте это к текущему числу наборов.
3. Добавьте размер нового набора в число элементов, с которыми мы столкнулись до сих пор.

Код:

int numberOfPairs=0; 
int elementsEncountered=0; 

for(int k = numberOfSets - 1 ; k >= 0 ; k--) { 
    int sizeOfCurrentSet = map.get(k); 
    int numberOfNewPairs = sizeOfCurrentSet * elementsEncountered; 
    numberOfPairs += numberOfNewPairs; 
    elementsEncountered += sizeOfCurrentSet; 
} 

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