Solved

All possible list combinations

Posted on 2000-05-11
6
278 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
PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

 
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

Windows Server 2016: All you need to know

Learn about Hyper-V features that increase functionality and usability of Microsoft Windows Server 2016. Also, throughout this eBook, you’ll find some basic PowerShell examples that will help you leverage the scripts in your environments!

Question has a verified solution.

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

Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
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 viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

778 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