Алгоритм нахождения количества комбинаций
Допустим, у меня есть четыре числа 0,1,1,3, Я хочу найти номер уникальной комбинации двух чисел. Пожалуйста, помогите мне написать алгоритм и код этого.
Я знаю, что это больше математический вопрос, но все же я должен написать код.
Пожалуйста, помогите мне.
Решение
Из вашего примера 0,1,1,3Я предполагаю, что вы хотите разрешить дублирование в своих входных данных, что затрудняет поиск количества уникальных комбинаций.
Поскольку вы хотите выбирать только уникальные пары, это намного проще, чем выбирать уникальные наборы n (по крайней мере, когда допускаются дубликаты).
Идея состоит в том, чтобы сначала удалить все дубликаты, сохраняя при этом, сколько входных данных имеют повторяющиеся значения.
Твой ответ потом будет
n C 2 + m где n это количество различных элементов и m количество элементов с дубликатами
за 0,1,1,3, n = 3 а также m = 1 Итак, вы получаете 3 C 2 + 1 = 3 + 1 = 4
(0, 1), (0, 3), (1, 1), (1, 3)
Приведенный ниже код дает реализацию, предполагая, что ваши входные данные являются вектором целых чисел.
Но вы можете изменить int на любой тип, который имеет < определены.
unsigned long long unique_pairs(const std::vector<int>& elements){
std::map<int, int> counts;
for (int i = 0; i < elements.size(); ++i){
++counts[elements[i]];
}
unsigned long long n = counts.size(); // # of different elements
unsigned long long m(0); // # of repeated elements
for (std::map<int, int>::iterator it = counts.begin(); it != counts.end(); ++it){
if (it->second != 1){
++m;
}
}
return n * (n - 1) / 2 + m; // n C 2 + m
}
Другие решения
Простой псевдокод для вас заключается в следующем:
1- getInputs(std::vector<int> inputs) // отвечает за чтение входных данных от пользователя
2- removeDuplicates(std:vector<int> inputs) // удаляем дубликаты из входов
3- calculateCombination(n = length(inputs)) // если вы ищете комбинацию, вы должны реализовать n!/((n-2)!*2!) или если вы ищете перестановку, вы должны реализовать n!/(n-2)!
Вы должны использовать формулу комбинации в нем. И вы должны написать факториальную функцию для этого.
Предположим, например, у вас есть 4 числа, и вы хотите количество комбинаций без повторения, поэтому используйте 4С2
здесь 2 для количества элементов, которые вы хотите использовать в комбинации
4 — это общее количество элементов, которые у вас есть
так что вы можете решить это с помощью 4! / (2! * (4-2)!) ….так что этот расчет даст вам общее количество комбинаций без повторений
Примечание: для уникальной комбинации у вас должны быть уникальные элементы