Алгоритм нахождения количества комбинаций

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

0

Решение

Из вашего примера 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

Другие решения

Простой псевдокод для вас заключается в следующем:

1- getInputs(std::vector<int> inputs) // отвечает за чтение входных данных от пользователя

2- removeDuplicates(std:vector<int> inputs) // удаляем дубликаты из входов

3- calculateCombination(n = length(inputs)) // если вы ищете комбинацию, вы должны реализовать n!/((n-2)!*2!) или если вы ищете перестановку, вы должны реализовать n!/(n-2)!

0

Вы должны использовать формулу комбинации в нем. И вы должны написать факториальную функцию для этого.

Предположим, например, у вас есть 4 числа, и вы хотите количество комбинаций без повторения, поэтому используйте 4С2

здесь 2 для количества элементов, которые вы хотите использовать в комбинации

4 — это общее количество элементов, которые у вас есть

так что вы можете решить это с помощью 4! / (2! * (4-2)!) ….так что этот расчет даст вам общее количество комбинаций без повторений

Примечание: для уникальной комбинации у вас должны быть уникальные элементы

0
По вопросам рекламы [email protected]