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

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
Asked:
ch52jb
  • 3
  • 2
1 Solution
 
yzCommented:
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
 
ch52jbAuthor 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
 
yzCommented:
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
Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

 
jasonclarkeCommented:
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
 
yzCommented:
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
 
ch52jbAuthor 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.

Join & Write a Comment

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.

  • 3
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now