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.
Generating all possible combinations
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]));
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);
}
}
}
}
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.
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.
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?).
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?).
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?
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();
}
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)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
