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

Question

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

Answer 1

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

демонстрация

Answer 2

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

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

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

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

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

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

Answer 3

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

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

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

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