0

4 つの数字があるとします0,1,1,3。2 つの数の一意の組み合わせの数を見つけたいです。これのアルゴリズムとコードを書くのを手伝ってください。これは数学の問題であることはわかっていますが、それでもコードを書かなければなりません。私を助けてください。

4

3 に答える 3

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 のベクトルであると仮定した実装を提供します。<ただし、 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
}

デモ

于 2016-03-02T07:47:01.677 に答える
0

その中で組み合わせ式を使用する必要があります。そして、階乗関数を書く必要があります。

たとえば、4つの数字があり、繰り返しのない組み合わせの数が必要な場合は、4C2を使用するとします

ここで 2 は、組み合わせて使用​​する要素の数です

4はあなたが持っている要素の総数です

これは4を使用して解決できます。/(2!*(4-2)!) ....したがって、この計算により、繰り返しのない組み合わせの総数が得られます

注：ユニークな組み合わせには、ユニークな要素が必要です

于 2016-03-02T07:33:14.343 に答える
0

簡単な疑似コードは、次のようにすることです。

1- getInputs(std::vector<int> inputs)// ユーザーからの入力を読み取る責任がある

2- removeDuplicates(std:vector<int> inputs)//入力から重複を削除する

3- calculateCombination(n = length(inputs))//組み合わせを探している場合は実装するn!/((n-2)!*2!)か、順列を探している場合は実装する必要がありますn!/(n-2)!

于 2016-03-02T07:46:36.950 に答える