-
April 20th, 2001, 01:35 AM
#1
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.
-
April 20th, 2001, 07:49 AM
#2
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
-
April 20th, 2001, 02:28 PM
#3
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
-
April 21st, 2001, 04:06 AM
#4
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
-
September 13th, 2013, 11:33 PM
#5
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
-
May 1st, 2016, 01:52 PM
#6
Re: Generate all combinations of M out N elements
I just wrote this stuff, and it works:
private List<int[]> CombinationGenerator(int M, int N)
{
List<int[]> result = new List<int[]>();
if (M <= N) {
int[] combination = null;
combination = new int[M];
CombinationRecurser(M, N, 1, 1, ref combination, ref result);
}
return result;
}
private void CombinationRecurser(int M, int N, int start, int position, ref int[] combination, ref List<int[]> result)
{
for (i = start; i <= N; i++) {
combination(position - 1) = i - 1;
if (position < M) {
CombinationRecurser(M, N, i + 1, position + 1, ref combination, ref result);
} else {
result.Add(combination.Clone);
}
}
}
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|