# Generating all possible combinations

This topic is 2352 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

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 9
• 9
• 9
• 14
• 12
• ### Forum Statistics

• Total Topics
633288
• Total Posts
3011221
• ### Who's Online (See full list)

There are no registered users currently online

×