Solved

List all  possible combinations of x numbers taken y at a time , in C++

Posted on 2008-06-16
4
2,574 Views
Last Modified: 2012-06-21
Is there a function or a library which has a function for this problem : I have x numbers (e.g 5) , and I want to list all possible combinations in of these numbers taken y (e.g 3) at a time. For example, let's say we have these 5 numbers: 1, 3, 5, 6, 7 , I want to print all the possible combinations taken 3 at time, which means 135, 356,567 etc etc.

If there is not such function, can you provide me the basic guidelines to build such a function? thanks a lot.
0
Comment
Question by:Chrysaor
[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
4 Comments
 
LVL 4

Expert Comment

by:albuitra
ID: 21794089
The position of the number is important ?
So is equal 135, 351, 531, 513 or do you count it like a diferent combination ?
0
 
LVL 17

Assisted Solution

by:rstaveley
rstaveley earned 100 total points
ID: 21794149
Combinations not permutations right?

Have you checked out Codeproject et al?

e.g. http://www.codeguru.com/cpp/cpp/algorithms/combinations/article.php/c5117/
0
 
LVL 1

Accepted Solution

by:
Aelyan earned 200 total points
ID: 21794810
The basic idea is to step through all the combinations so you would first choose 3 numbers, then display all permutations of those, then go to the next set.  For your example 1, 3, 5, 6, 7, start with 1, 3, and 5 and then give all combinations of those 135, 153 etc then go to 1, 3, 6 and do the same thing.  

The choosing 3 is pretty simple, you can do it by hard coding the stepping.  Have an array of 3, lets call it y, and make the third one linked to an index which will step through the original list from the position of y[2] + 1 till the end.  The second one is linked to the a position in the original list and it will increment by one once y[3]'s position hits the end of the original list.  And y[1] goes to the next number once y[2] goes through all the numbers(that come after where y[1] is of course).  You will end up having a bunch of loops within loops but this is the most straight foward way to do it.  Making combinations of the 3 should be pretty straightfoward to do, just have 6 outputs where you hardcode the combinations since you have it stored in an array(like cout<<y[1]<<y[2]<<y[2]<<endl; cout<<y[2]<<y[1]<<y[3]; etc)

A, personally, cooler way to do it is to again have an array of 3 and to choose numbers for it just randomly choose 3, then have a map which has previously done numbers, cross check and if its a new number run the combination thing.  Honestly, while the first way is messier and in my opinion less cool, its probaby faster despite having nested loops because the sizes are set but if speed is not an issue I say go for broke with random numbers :)
0
 
LVL 45

Assisted Solution

by:Kent Olsen
Kent Olsen earned 200 total points
ID: 21798530

Combinations are surprisingly easy in C/C++.  While it's really a recursion problem, there is a very easy non-recursive answer.  For problems like 3 of 5 (n of y) it's not necessarily the most efficient, but it's very easy to understand.


1. Define the number of items in the source group.  (in your example 5)
2. Initialize an integer (Counter) to 0.  
3. Add 1 Counter.
4.  If (Counter >> NumberOfSourceItems) break the loop
5.  Count the number of 1 bits in Counter.
6.  If the number of bits != the TargetCount, repeat from 3.  (in your example 3)
7.  Display the values at the corresponding bits.
     (If Counter = 01011 binary, display 124.  You start at the right, print values
     when you encounter a 1, and skip values when you encounter a 0.)
8.  repeat from 3.


If you can't get your head wrapped around the recursive solution, this will work quite well.    :)


Good Luck,
Kent

     
0

Featured Post

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
wordcount challenge 11 147
Least Squares Curve Fitting 4 116
numbers ascending pyramid 101 241
fatal error: vector: No such file or directory   Visual Studio 2015 for Arduino 4 103
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 …
How to remove superseded packages in windows w60 or w61 installation media (.wim) or online system to prevent unnecessary space. w60 means Windows Vista or Windows Server 2008. w61 means Windows 7 or Windows Server 2008 R2. There are various …
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 clear a vector as well as how to detect empty vectors in C++.

726 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