N個の元素の中からM個の元素を選んで、何種類の組み合わせがあります

//////////////////////////////////////////////////////////////////////////
//
//    :   N        M  ,         
//
//////////////////////////////////////////////////////////////////////////

//
//          aux[1..M]      input[1..N]          
//    input[i]    ,         aux[*] = i
//

//
//       :
//      ,   N        M  ,       M  ,           M - 1  。
//
//    aux[m]       : (  input           ) ~ input[m]。
//    input[m]            , aux[0..m-1]       input      。
//
//    m              ,          M
void combination1(char input[], const int N, int aux[], int m, const int M, int & counter)
{
    for (int i = N; i >= m; i--)    //     
    {
        if (m >= 1)
        {
            aux[m - 1] = i - 1;     //    input[i-1]
        }

        if (m > 1)                  //     ,   input[0..i-1]        m-1    
        {
            combination1(input, i - 1, aux, m - 1, M, counter);
        }
        else                        //     
        {
            counter++;

            cout << "{ ";           //    aux[j]      ,    input[aux[j]]
            for (int j = 0; j )
            {
                cout << input[aux[j]] << " ";
            }
            cout << "}" << endl;
        }
    }
}

void combination1(char input[], const int N, const int M)
{
    int * aux = new int[M];
    memset(aux, 0, sizeof(int) * M);

    int counter = 0;

    combination1(input, N, aux, M, M, counter);

    cout << "total : " << counter << endl;
}

//
//       :
//      :   N       M ,       1  ,    M - 1             。
//
// [begin*************X******N-1]
//              [0....m******M-1]
// N - 1 - X = M - 1 - m
// X = N - M + m
// aux[m]     : [input[begin], input[X]]
//
//     m           ,      0
void combination2(char input[], const int begin, const int N, int aux[], int m, const int M, int & counter)
{
    for (int i = begin; i <= N - M + m; i++)    //     
    {
        if (m < M)
        {
            aux[m] = i;                         //     m    
        }

        if (m < M - 1)                          //     ,      input[i+1..N]         
        {
            combination2(input, i + 1, N, aux, m + 1, M, counter);
        }
        else
        {
            counter++;

            cout << "[ ";
            for (int j = 0; j )
            {
                cout << input[aux[j]] << " ";
            }
            cout << "]" << endl;
        }
    }
}

void combination2(char input[], int N, int M)
{
    int * aux = new int[M];
    memset(aux, 0, sizeof(int) * M);

    int counter = 0;

    combination2(input, 0, N, aux, 0, M, counter);

    cout << "total : " << counter << endl;
}

//
//    
// flag     input   
// flag[i]      input[i]      
// n        input        
// m           
void back_tracking(char input[], bool flag[], const int N, const int M, int n, int m, int & counter)
{
    if (m == M)                 //     M  
    {
        counter++;

        cout << "< ";
        for (int j = 0; j )
        {
            if (flag[j])
            {
                cout << input[j] << " ";
            }
        }
        cout << ">" << endl;
    }
    else if (m >= M || n >= N )     // n >= N     input     ,      M    
    {
        return;
    }
    else
    {
        flag[n] = 1;                //     input[n]
        back_tracking(input, flag, N, M, n + 1, m + 1, counter);

        flag[n] = 0;                //      input[n]
        back_tracking(input, flag, N, M, n + 1, m, counter);
    }
}

void back_tracking(char input[], int N, int M)
{
    bool * flag = new bool[N];
    memset(flag, 0, sizeof(bool) * N);

    int counter = 0;

    back_tracking(input, flag, N, M, 0, 0, counter);

    cout << "total : " << counter << endl;
}

void select_M_from_N()
{
    char input[] = "abcdef";
    //
    //    
    combination1(input, strlen(input), 3);

    //
    //    
    combination2(input, strlen(input), 3);

    //
    //    
    back_tracking(input, strlen(input), 3);
}

 
転載先:https://www.cnblogs.com/happylong/p/4504341.html