• Advertisement
Sign in to follow this  

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.

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
But this will only work if size of combination is 2.

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
Thanks to all.

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

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

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


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


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


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


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


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

Share this post


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

  • Advertisement