DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

1. Registered User
Join Date
Nov 2007
Posts
2

## Combination

Hi!
I'm new to C++ but I have a challenge to write a program to find the different mathematical combinations of p and t objects respectively from a total of n objects i.e. nCp and nCt.The program should display the various combinations.
A further aspect is to find the intersection between nCp and nCt i.e.each set of nCp that contains each of the possible combinations of nCt without considering the order of appearance.

Let me try to be clearer,pls:

say n=7,p=5 and t=3

1. I want a program to find 7C5 and 7C3
2. I want a display of the possible combinations in each case i.e
for 7C5; (12345),(12346),(12347),(13456)etc and
for 7C3; (123),(124),(125),(126)etc
3. Finally, the intersection e.g.
(123) intersects (12345),(12346),...
(124) intersects (12345),(12346)...
(125) intersects (12345)
and so on.

2. Registered User
Join Date
Nov 2007
Location
Pittsburgh, PA/Shanghai, China
Posts
45
number 1. use the mathetical formula
number 2. use recursive backtracking to display the possible combination

Code:
```private static void choose(String sWord, int iSubSize, char[] cHoose, int iStartIndex)
{
if(iSubSize <= 0)
{
for(int i = 0; i < cHoose.length; i++)
System.out.print(cHoose[i]);
System.out.println();
// iCount is a global variable that keeps track of the # combinations
iCount++;
return;
}
for(int i = iStartIndex; i < sWord.length() - iSubSize + 1; i++)
{
cHoose[cHoose.length - iSubSize] = sWord.charAt(i);
choose(sWord, iSubSize - 1, cHoose, i + 1);
}
}```
code is written in Java, but could be easily modified to your need

number 3. I don't understand this fully, could you be more spefic plz?

hope that helps

3. Registered User
Join Date
Nov 2007
Posts
2

## Thanks

Thanks for your help.I've been looking at the solution you proferred but as I stated earlier,I'm new to programming and Java too.

On the 3rd part,let me state a further example:
Say n=4,p=3 and t=2
1. 4C3=4 and 4C2=6

2. The elements i.e possible combinations of 4C3 are (123),(124),(134) and (234).The elements of 4C2 are (12),(13),(14),(23),(24) and (34)

3.For the intersection between 4C3 and 4C2,I want the set of elements of 4C3 that contains each possible combination of 4C2 irrespective of the order. e.g. the set of elements of 4C3 that contains :
(12) is (123) and (124)
(13) is (123) and (134)
(14) is (124) and (134)
(23) is (123) and (234)
(24) is (124) and (234)
(34) is (134) and (234)
Here is an algorithm someone suggested but he said it's going to be hardwork:

subset = true
for each element in smaller array
if current element is not in larger array then
subset = false
end for

return subset