Solved

All possible list combinations

Posted on 2000-05-11
6
285 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
[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
  • Learn & ask questions
  • 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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
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

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

717 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