Generate all combinations of M out N elements
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5

Thread: Generate all combinations of M out N elements

  1. #1
    Join Date
    Mar 2001
    Posts
    7

    Generate all combinations of M out N elements

    Hi Everybody,

    I require your help for finding a solution of a mathematical problem in C language. The brief details of the problem is as follows:

    I have a global array of n elements of type integer having some values. I want to write a function, which takes two int as a parameter one will be the size of the array i.e. n and second parameter will be used to generate the combination (m) say if second parameter is 3 the function has to fetch 3 elements of the array store it in some temp array or pointer and pass it on to some function after that again fetch 3 elements so on till the maximum limit is not reached which can be find out by nCm.
    To be more clear consider the following example:
    The Array is of 7 elements having elements data starting from 1 to 7. If m is 3 then no of temporary combinations will be nCm=35, which are as follows:
    123 134 145 156 167
    124 135 146 157
    125 136 147
    126 137
    127

    234 245 256 267
    235 246 257
    236 247
    237

    345 356 367
    346 357
    347

    456 467
    457

    567

    The same sequence is applied for any value of m be it 2,3,4,5 etc. It will be kind if anybody help me or send me the algorithm or program to perform this task.

    Please note that the size of m is not known at design time it will be passed at a runtime.

    Thanking You,

    -Tejash.



  2. #2
    Join Date
    Apr 1999
    Posts
    27,427

    Re: Generate all combinations of M out N elements

    I'll take your challenge and come up with the following algorithm (this could be homework, so I won't give an example in code):

    You want to display the combination of n items taken m at a time

    1) For n total items, set up a set of n bits. The bits are numbered from 0 to n-1, so you have the following (assuming that n=7)

    "0000000"

    The 0th bit is the rightmost bit, and bit n-1 is the leftmost bit. Call this array of bits "bit".

    2) Set up each element in your set in an array of n items. For example,
    7 6 5 4 3 2 1.

    Call this array "elements". So elements[0]=1, elements[n-1] = 7, etc.

    3) Set bits 0 to m-1 to "1". So for example the bit array will now be "0000111" (assuming m=3).

    4) For J = 0 to n Do
    if bit[ J ] = 1 then output elements[ J ]
    End For J
    Output Carriage return (go to next line in output)

    5) Get the next permutation of the "bit" array. If there is another permutation, go to step 4.

    6) Quit

    The idea of the algorithm is to generate all of the bit patterns with exactly 3 "on" bits. For each generation of the bit patterns, you output
    the element corresponding to the "on" bits.

    Now, how do you do permutations easily? No problem with C++ and the algorithm function called "next_permutation()". This program can be done in no time using this nice function.

    If this must be 'C', then maybe you did a permutation progam/function previously. Since you are doing combinations, it makes sense that you might have done a permutation program. This is what code reuse is about.

    If it is a 'C' program, you'll have to create your own little permutation function. Again, www.google.com searches, and a lot of textbooks have permuataion algorithms.

    Regards,

    Paul McKenzie



  3. #3
    Join Date
    Apr 1999
    Posts
    27,427

    Re: Generate all combinations of M out N elements

    Tejash, I have a class that generates combinations on any type (it took about 15 minutes to code the whole thing) but again, this looks like a homework problem, and it uses C++, not 'C'.

    Regards,

    Paul McKenzie


  4. #4
    Join Date
    Apr 1999
    Posts
    27,427

    Re: Generate all combinations of M out N elements

    Tejash, here is the class that gets the combinations. I will probably submit this to CodeGuru on a future date:

    #include <vector>
    #include <iostream>
    #include <algorithm>
    //...
    using namespace std;
    //...
    // Microsoft doesn't include min() template so I had to define it
    template<class T>
    const T& min(const T& x, const T& y) { return x < y?x:y; }

    // Class to generate combinations given a vector<T>
    // The total elements is the size of the passed in vector,
    // The number of items to choose is nItems.
    template <class T>
    class CombinationGenerator
    {
    public:
    CombinationGenerator(const vector<T>& ElVector, // Original items
    int nItems=-1) : // Number of items to choose
    m_Elements(ElVector), m_bNext(true)

    {
    int nSize = ElVector.size();
    if ( nSize > 0 )
    {
    // If no argument given, choose all items
    if ( nItems <= 0 )
    m_nItems = nSize;
    else
    m_nItems = min(nItems, nSize);

    // Bit vector that controls permutations
    m_Bits.resize( nSize, 0 );

    // Initialize nItem bits in vector to "1"
    int i, j;
    for (i = 0, j = nSize - 1;
    i < m_nItems;
    i++, j-- )
    {
    m_Bits[j] = 1;
    }
    }
    else
    m_bNext = false; // size is 0, so no combinations are possible
    }

    // Get a combination and output results in the passed in vector Output
    bool NextCombination(vector<T>& Output)
    {
    // Erase all elements in output vector
    Output.erase(Output.begin(), Output.end());

    // If no more combinations, quit
    if ( !m_bNext )
    return false;

    if ( m_bNext )
    {
    // copy only elements that have a "1" in the
    // Bit vector
    for ( int j = 0; j < m_Elements.size(); j++ )
    {
    if (m_Bits[j] == 1 )
    Output.push_back(m_Elements[j]);
    }
    // Get next permutation of bits
    m_bNext = next_permutation(m_Bits.begin(), m_Bits.end());
    }
    // Combination was generated
    return true;
    }

    private:
    vector<T> m_Elements;
    vector<int> m_Bits;
    int m_nItems;
    bool m_bNext;
    };
    //...
    //... Test program
    int main()
    {
    vector<int> elements;
    vector<int> results;

    // Initialize a vector to 1, 2, 3, 4,5, 6, 7
    for (int i = 1; i <= 7; i++ )
    elements.push_back(i);

    int nItems;
    cout << "Enter number of items to choose (must be <= 7) :";
    cin >> nItems;

    // Here is a Combination Generator instrance that handles integers
    // This is C(7, nItems) (7 items taken nItems at a time)
    CombinationGenerator<int> CG(elements, nItems);

    // Call NextCombination until there are no more combinations
    int nTries = 0;
    while (CG.NextCombination(results))
    {
    // Output our results
    int nSize = results.size();
    for ( int j = 0; j < nSize; j++ )
    cout << results[j] << " ";
    cout << endl;
    nTries++;
    }
    cout << "Number of combinations is " << nTries << endl;
    }



    So CombinationGenerator<> is a templated class. All you need to do is create an instance of "CombinationGeneraor<your_data_type>(Vector_of_your_data, nItems);" and keep calling "NextCombination" in a while() loop. Calling NextCombination() fills an array of the next combination, and returns true if a combination was found, or false if no more combinations exist.

    Note that the main() program prints the number of combinations, just to prove to yourself (and myself) that this class actually works.

    I hope this helps.

    Regards,

    Paul McKenzie


  5. #5
    Join Date
    Sep 2013
    Posts
    1

    Smile Re: Generate all combinations of M out N elements

    If you get the code then give it to me as well.please
    my email is: ashish.adorable09@gmail.com

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center