Solved

# All possible list combinations

Posted on 2000-05-11
282 Views
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
Question by:ch52jb
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 3
• 2

LVL 1

Expert Comment

ID: 2799994
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 Comment

ID: 2800027
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

LVL 1

Accepted Solution

yz earned 150 total points
ID: 2800186
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

LVL 9

Expert Comment

ID: 2800266
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

LVL 1

Expert Comment

ID: 2800476
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 Comment

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

Jim
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

### Suggested Solutions

This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
###### Suggested Courses
Course of the Month8 days, 11 hours left to enroll