Solved

All possible list combinations

Posted on 2000-05-11
6
274 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
Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

 
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

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
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 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…

744 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

13 Experts available now in Live!

Get 1:1 Help Now