• Status: Solved
• Priority: Medium
• Security: Public
• Views: 295

All possible list combinations

I have a list of objects, and I need to assemble all possible combinations of these objects and test them (e.g. any 1, any 2, any 3 etc...).  Are there any algorithms for creating all possible combinations?  The list is of varying size and I need to be able to test each combination as soon as it has been generated and if it passes the test, stop the program.

Many thanks

Jim
0
ch52jb
• 3
• 2
1 Solution

Commented:
This is a basic recursion arithmetic. You can set all object a flag with 0 or 1, 0 mean not selected, 1 means selected, and make a n-level recursion, in every level, set the flag of this object to 0, go recursion, and to 1, go recursion again, then you reach the last object, you can get a list combined with 0 and 1, when you finished this recursion process, you can get all the posibility of combinations.
0

Author Commented:
Thanks yz, but I'm not quite up to speed on recursive algorithms.  Any chance you could explain in a bit more detail with a bit of pseudo code to show me the process.

Cheers

Jim
0

Commented:
this program shows a sample way to calculate the full combinations of 10 objects, but as we all know, the recursive algorithms is inefficient, I hope this code can help you.

#include <stdio.h>
#include <stdlib.h>

#define OBJECT_NUMBER 10

char objects[OBJECT_NUMBER] = {0};

void step(int n)
{
if (OBJECT_NUMBER == n)
{
for (int i=0;i<OBJECT_NUMBER;i++)
printf("%d", objects[i]);
printf("\n");
return;
}

objects[n] = 0;
step(n+1);

objects[n] = 1;
step(n+1);
}

void main()
{
step(0);
}
0

Commented:
STL provides some algorithms for working out permutations of objects in a container:

#include <vector>
#include <algorithm>
using namespace std;

vector<Object> container;

// insert the elements...
....
do {
// Process permutation
} while (next_permutation(container.begin(), container.end());

0

Commented:
Thank jasonclarke, I only know little about algorithm, no STL.

and to ch52jb, the previous program is to get all the combinations, if u want get particular number of objects, u can try this program , it returns all the combinations with 3 object of 10.

#include <stdio.h>
#include <stdlib.h>

#define OBJECT_NUMBER 10
#define REQUIRE 3

char result[REQUIRE];

void step(int n)
{
if (REQUIRE == n)
{
for (int i=0;i<REQUIRE;i++)
printf("%d", result[i]);
printf("\n");
return;
}
for (int j=0; j<OBJECT_NUMBER; j++)
{
result[n]=j;
step(n+1);
}
}

void main()
{
step(0);
}\
0

Author Commented:
Thanks yz, I've managed to implement it very successfully.  Many thanks.

Jim
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.