Jump to content
  • Advertisement
Sign in to follow this  
udvat

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.

If you intended to correct an error in the post then please contact us.

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?

Thanks in advance.

Share this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!