Алгоритм для поиска числа комбинаций

Question

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

Answer 1

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

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

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

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

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

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

Answer 2

простой псевдо-код для вас, чтобы сделать то, как это:

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

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

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

Answer 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 
} 

Demo