2
$\begingroup$

I'm working on a program (using C++) that has a list of words in a vector: {"one", "two", "three", "four"} for example, and I'd need to get all possible partitions respecting the order and where subsets contain one or at most two words.

For example:

{"one", "two", "three", "four"} {"one two", "three", "four"} {"one two", "three four"} {"one", "two three", "four"} .. etc

Note that both the order of the set is maintained and no repetition is allowed. Note also that {"one two three", "four"} wouldn't be valid as each subset can have 2 elements at most.

As I'm working in C++, I was thinking if it's possible to make an algorithm that could tell me how to generate all possible sets. Avoiding recursion would be preferable, as I presume I could run into some stack overflow issues on some platforms.

For example, something that generated a sequence like

(1,1,1,1), (2,1,1), (2,2), (1,2,1), etc. (basically, stating the size of each subset) would be what I'm looking for.

Any help is greatly appreciated.

  • 0
    @Arturo: you're right, so I edited the post. Tha$n$ks.2011-08-08

3 Answers 3

1

Here's some pseudocode that generates the tuples you want:

push an empty list onto the stack; while (the stack isn't empty) {   pop the top list off the stack;   if (the sum of its entries is n)     add it to the solution set;   else if (the sum of its entries is less than n)     add a 1 to a copy of the list and push it onto the stack;     add a 2 to a copy of the list and push it onto the stack;   } } 
1

You can do it iteratively for a set of $n$ elements.

First suppose there are exactly $j$ twos appearing.

Thus the number of ones is $n-2j$ and your sequence will have $n-j$ elements. Of these $n-j$ elements, you need to pick $j$ spots for the twos. The rest will be ones.

This corresponds to generating all $j$ size subsets of a set of size $n-j$ and can be done iteratively and in a space efficient manner. (See this stackoverflow thread: https://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n/127856#127856)

Vary $j$ from $0$ to $n/2$ and you are done.

Incidentally, the total number that will be generated is a Fibonacci number!

  • 0
    In any event, with $50$ items the difference you pointed out between $\phi^n$ and $2^n$ would indeed be quite noticeable :-). But, @Dan, $\phi^{50}$ is still only on the order of tens of billions, so depending on how fast you need this to run and how much processing you need to do with each of the results, this might still be feasible.2011-08-09
1

You want all sequences $(x_1, \ldots, x_m)$ of 1's and 2's with a given sum $N$. Given $m$ with $N/2 \le m \le N$, there will be $N-m$ 2's and $2m-N$ 1's. These can be generated one by one, in lexicographic order, as follows. Start with $2 \ldots 2 1 \ldots 1$ (all the 2's followed by all the 1's). At each step, find the first occurrence of "2 1", switch it to "1 2", and move all 2's that are left of that position to the front. Thus with $m = 5$ and $N=7$ we have

2 2 1 1 1 (switch the 2 1 to 1 2)

2 1 2 1 1 (switch the first 2 1 to 1 2)

1 2 2 1 1 (switch the 2 1 to 1 2 and move the first 2 to the front)

2 1 1 2 1 (switch the first 2 1 to 1 2)

1 2 1 2 1 (switch the first 2 1 to 1 2)

1 1 2 2 1 (switch the 2 1 to 1 2 and move the first 2 to the front)

2 1 1 1 2 etc.

  • 0
    Thanks for this, it shows a way to approach it in a very intuitive way that I haven't thought of!2011-08-08