# Generating all possible combinations

This topic is 2086 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi,

I want to generate all possible combination from a set of n numbers and
want to exclude the combinations with hold two consecutive numbers.

For example,

S={1,2,3}

I just want to generate
1;
2;
3;
1,3;

Is there any smart way of doing this other than generating all combinations first and
removing the unwanted ones?

##### Share on other sites
hm what about something like this?

 std::vector<Combination> combinations; for (uint i=0; i < elements_max; ++i) for(unint j=i+2; j < elements_max; ++j) combinations.push_back(Combination(element, element[j])); 

##### Share on other sites
But this will only work if size of combination is 2.

##### Share on other sites
Off the top of my head, I'd try something like this (pseudo-code):
 void combinations(int first, int last, CombinationContainer & c) { for (int i = first; i < last; ++i) { c.add(i); if ((i + 2) < last) { CombinationContainer temp; combinations(i + 2, last, temp); foreach (Combination cc in temp) { c.add(cc | i); } } } } 

##### Share on other sites
Writing your own iteration function for this isn't too bad. The problem is the size of the data generated is factorially big.

The code behind it isn't too complex. A few seconds on Google found several good articles on it, including this one at CodeProject. I noticed a few other good implementation in the search; that one just provides both recursive and non-recursive ways to solve it, and an iterator object so you don't need to store them all. Edited by frob

##### Share on other sites
Actually, the set of data only grows as fast as the Fibonacci sequence, which is not nearly as fast as factorial.

Use a recursive function that gets a partially filled combination and a mark of how much of the combination has been filled already, it tries out all possible next terms and calls itself again for each possibility.

If you have trouble getting something to work, I'll be happy to write a quick test for you (is C++ OK?).

##### Share on other sites
Thanks to all.

@Alvaro : yes, c++ is ok. Thanks in advance.

##### Share on other sites
If the input set is S = {1, 3, 5}, do we get more combinations, or are 1 and 3 considered consecutive because they appear next to each other in the set description?

##### Share on other sites
Assuming the answer to my previous question is that we do get more combinations for S = {1, 3, 5}, this C++11 code does the job:
#include <iostream> #include <vector> class CombinationsGenerator { std::vector<int> S; std::vector<int> combination; void generate_recursive() { for (int i : combination) std::cout << S << ' '; std::cout << '\n'; int first; if (combination.empty()) first = 0; else { int last = *combination.rbegin(); first = last + (S[last+1] == S[last] + 1 ? 2 : 1); } for (int i = first, end = S.size(); i < end; ++i) { combination.push_back(i); generate_recursive(); combination.pop_back(); } } public: // Input: S is a sorted vector CombinationsGenerator(std::vector<int> const &S) : S(S) { } void generate() { combination.clear(); generate_recursive(); } }; int main() { std::vector<int> S = {1, 2, 3, 5}; CombinationsGenerator(S).generate(); } 

##### Share on other sites
A simple solution in Python 3.
 #No memoization, space and stack depth proportional to n (by sharing the same sequence of numbers instead of making altered copies) #The "numbers" sequence is assumed to contain distinct values sorted in increasing order #slightly funny order def nonconsecutive(numbers, first_index): if first_index == len(numbers) - 1: yield (numbers[first_index],) elif first_index < len(numbers) - 1: r = (numbers[first_index],) next_index = first_index + 1 if numbers[next_index] == numbers[first_index] + 1: #skip consecutive number for c in nonconsecutive(numbers, next_index + 1): yield r + c for c in nonconsecutive(numbers, next_index): yield c else: #recycle results twice at the expense of lexicographical ordering for c in nonconsecutive(numbers, next_index): yield r + c yield c yield r else: #past the end of the numbers sequence pass #the original example n = 3 for c in nonconsecutive(list(range(1, n + 1)), 0): print(c)  Edited by LorenzoGatti

##### Share on other sites

If the input set is S = {1, 3, 5}, do we get more combinations, or are 1 and 3 considered consecutive because they appear next to each other in the set description?

No, 1,3 are not considered as consecutive.

##### Share on other sites

void generate_recursive() {
------> for (int i : combination)
std::cout << S << ' ';
std::cout << '\n';

I am getting error while compiling your code .

##### Share on other sites
Posting the error would be nice. But I am sure the problem is you are not using a C++11-compatible compiler, so I'll just change the code to be C++89 compatible for you:

#include <iostream> #include <vector> class CombinationsGenerator { std::vector<int> S; std::vector<int> combination; void generate_recursive() { for (int i = 0, e = combination.size(); i < e; ++i) std::cout << S[combination] << ' '; std::cout << '\n'; int first; if (combination.empty()) first = 0; else { int last = *combination.rbegin(); first = last + (S[last+1] == S[last] + 1 ? 2 : 1); } for (int i = first, end = S.size(); i < end; ++i) { combination.push_back(i); generate_recursive(); combination.pop_back(); } } public: // Input: S is a sorted vector CombinationsGenerator(std::vector<int> const &S) : S(S) { } void generate() { combination.clear(); generate_recursive(); } }; int main() { int S_i[] = {1, 2, 3, 5}; CombinationsGenerator(std::vector<int>(S_i, S_i+4)).generate(); } 

##### Share on other sites
Hi,

The problem is solved. Thanks to all.

##### Share on other sites
How did you solve it? Did you just copy one of the programs posted here?

##### Share on other sites

How did you solve it? Did you just copy one of the programs posted here?

No, I wrote a code myself. If you want, I can give it to you.

##### Share on other sites
Oh my, an entire thread of code samples for a problem that's already solved by the C++ standard library

[source lang="cpp"]
#include &lt;vector&gt;
#include &lt;algorithm&gt;
#include &lt;iostream&gt;
#include &lt;string&gt;

int main() {
using namespace std;

std::string wordOrNumber;

cout &lt;&lt; "Enter a word or a number: ";
cin &gt;&gt; wordOrNumber;

cout &lt;&lt; "Listing all permutations: " &lt;&lt; endl;

do {
cout &lt;&lt; wordOrNumber &lt;&lt; endl;
} while(next_permutation(wordOrNumber.begin(), wordOrNumber.end()));
}
[/source]

Example:
 Enter a word or a number: 123 Listing all permutations: 123 132 213 231 312 321  Edited by Cygon

##### Share on other sites

For example,

S={1,2,3}

I just want to generate
1;
2;
3;
1,3;

Example:
 Enter a word or a number: 123 Listing all permutations: 123 132 213 231 312 321 

Right... exactly what he wanted.

He asked for a way to select all combinations of elements of a set with the additional constraints that consecutive valued elements are not allowed in the selected set. He didn't ask for all permutations of a sequence. Edited by Brother Bob