Solved

All possible list combinations

Posted on 2000-05-11
6
275 Views
Last Modified: 2010-05-18
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
Comment
Question by:ch52jb
  • 3
  • 2
6 Comments
 
LVL 1

Expert Comment

by:yz
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

by:ch52jb
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

by:
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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 9

Expert Comment

by:jasonclarke
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

by:yz
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

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

Jim
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
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 be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

911 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now