1

それで、私は自分の問題の良い解決策を探していました。

整数のリストのすべての組み合わせを生成（印刷）する必要があります。たとえば、配列に0からn-1までの整数が含まれている場合、n = 5の場合：

int array[] = {0,1,2,3,4};

組み合わせの整数の順序は重要ではありません。つまり、{1,1,3}、{1,3,1}、および{3,1,1}は、すべて1つの3と2つの組み合わせが含まれているため、実際には同じ組み合わせです。

したがって、上記の配列の場合、長さ3のすべての組み合わせ。

0,0,0 -> the 1st combination
0,0,1
0,0,2
0,0,3
0,0,4
0,1,1 -> this combination is 0,1,1, not 0,1,0 because we already have 0,0,1. 
0,1,2
0,1,3
0,1,4
0,2,2 -> this combination is 0,2,2, not 0,2,0 because we already have 0,0,2. 
0,2,3
.
.
0,4,4
1,1,1 -> this combination is 1,1,1, not 1,0,0 because we already have 0,0,1. 
1,1,2
1,1,3
1,1,4
1,2,2 -> this combination is 1,2,2, not 1,2,0 because we already have 0,1,2.
.
.
4,4,4 -> Last combination

今のところ私はこれを行うためのコードを書きましたが、私の問題は次のとおりです：配列内の数値が0からn-1までの整数でない場合、配列がこのようであったかどうかを言いましょう

int array[] = {1,3,6,7};

私のコードはこの場合、この問題を解決するためのアルゴリズムやコードでは機能しません、、

これが私のコードです：

unsigned int next_combination(unsigned int *ar, int n, unsigned int k){
    unsigned int finished = 0;
    unsigned int changed = 0;
    unsigned int i;

    for (i = k - 1; !finished && !changed; i--) {
        if (ar[i] < n - 1) {
            /* Increment this element */
            ar[i]++;
            if (i < k - 1) {
                /* Make the elements after it the same */
                unsigned int j;
                for (j = i + 1; j < k; j++) {
                    ar[j] = ar[j - 1];
                }
            }
            changed = 1;
        }
        finished = i == 0;
    }
    if (!changed) {
        /* Reset to first combination */
        for (i = 0; i < k; i++){
            ar[i] = 0;
        }
    }
    return changed;
}

そしてこれがメインです：

int main(){
    unsigned int numbers[] = {0, 0, 0, 0, 0};
    const unsigned int k = 3;
    unsigned int n = 5;

    do{
        for(int i=0 ; i<k ; ++i)
            cout << numbers[i] << " ";
        cout << endl;
    }while (next_combination(numbers, n, k));

    return 0;
}
4

3 に答える 3

2

このコードでは、「要素プール」配列を最小から最大に並べ替え、重複するエントリがないようにする必要があります。

この関数first_combinationは、結果の配列（ "dist"）を最初の組み合わせに初期化します。この後、next_combinationfalseが返されるまでループで呼び出されます（例のように）。「n」および「k」引数は、配列のサイズを取得するテンプレートパラメータに置き換えられました。そのため、列挙関数には、結果に加えてプール配列が必要です。

#include <iostream>

template<typename T, int N, int K>
void first_combination(const T (&pool)[N], T (&dist)[K]) {
    for(int ki=0; ki<K; ++ki) {
        dist[ki] = pool[0];
    }
}

template<typename T, int N, int K>
bool next_combination(const T (&pool)[N], T (&dist)[K]) {
    int ni = 0;;
    int ki = 0;

    for(;;) {
        const int prev_ni = ni;
        // search the pool for the value in this slot 
        for(ni=0; pool[ni] != dist[ki]; ++ni) {
            if(ni == N) return false; // slot contains a value not found in the pool
        }

        if(++ni < N) break;

        ni = 0;
        dist[ki] = pool[0];
        if(++ki == K) return false;
    }

    int v = pool[ni];

    dist[ki] = v;

    // code below assumes pool[] is sorted
    for(--ki; ki>=0; --ki) {
        if(dist[ki] < v) {
            dist[ki] = v;
        }
        else {
            v = dist[ki];
        }
    }

    return true;
}


template<typename T, int COUNT>
void dumparray( T (&dist)[COUNT]) {
    std::cout << '{';
    for(int i=0; i<COUNT; ++i) {
        if(i) std::cout << ',';
        std::cout << dist[i];
    }
    std::cout << '}' << std::endl;
}

int main(int argc, char* argv[]) {
    const int pool[] = {1,3,6,7};
    int dist[3] = {0};

    first_combination(pool, dist);
    do {
        dumparray(dist);
    } while(next_combination(pool, dist));
    return 0;
}
于 2012-09-21T02:32:15.283 に答える
2

0からまでの数値のすべての組み合わせを生成する作業コードがある場合n-1、これは非常に簡単です。あなたはあなたの数の配列を持っています：

int array[] = {1,3,6,7};

n = 4配列には4つの項目があるので、ここで、を取ります。0から3までのすべての組み合わせを生成し、それらを配列のインデックスとして使用します。これで、インデックスのすべての組み合わせをその配列に使用することにより、配列値のすべての組み合わせが得られます。

于 2012-09-20T22:35:02.430 に答える
0

したがって、組み合わせを生成するためのプログラムが必要です（wikiリンク）。

ここに完全な説明があり、アルゴリズムを使用する準備ができています：http: //compprog.wordpress.com/2007/10/17/generated-combinations-1/

于 2012-09-20T22:34:25.550 に答える