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.

Improve this question
$\endgroup$
3
  • $\begingroup$ These aren't so much permutations as partitions. $\endgroup$ – Arturo Magidin Aug 8 '11 at 18:51
  • $\begingroup$ The natural way to do this sort of thing would be with recursion, but you can always use your own stack instead to remember what you still need to work through. $\endgroup$ – joriki Aug 8 '11 at 18:54
  • $\begingroup$ @Arturo: you're right, so I edited the post. Thanks. $\endgroup$ – Dan Aug 8 '11 at 18:55
1
$\begingroup$

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;
  }
}
Improve this answer
$\endgroup$
1
$\begingroup$

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!

Improve this answer
$\endgroup$
10
  • $\begingroup$ If you're not too worried about efficiency, an easy way to generate all subsets of a given size is to loop with a counter and interpret its bits as selecting elements; count the bits and use them whenever as many bits are set as you want to select elements. $\endgroup$ – joriki Aug 8 '11 at 19:07
  • $\begingroup$ @joriki: An easier way would be to pick up already written optimal code, which I presume already exists :-) $\endgroup$ – Aryabhata Aug 8 '11 at 19:10
  • $\begingroup$ I wrote that comment after following your link and finding lots of complicated stuff that I couldn't immediately understand. Certainly if efficiency is important it would be worth the effort to integrate such code, but if not, in my experience its an order of magnitude easier to write a bit counting function and a loop over a bit counter than to try to unearth other people's code and get it to work in your own context. Since the OP is dealing with strings, there's a fair chance that time is not of the essence here (CPU time, not developer's time). $\endgroup$ – joriki Aug 8 '11 at 19:17
  • $\begingroup$ @joriki: It depends on OP's scenario of course. Actually just generating $n-j$ bits with exactly $j$ ones is not that hard. You start with $000\dots 1111$ and keep shifting them about (I think that is one of the approaches in Knuth's book). The approach you suggest will be $\Theta(2^n)$, while the optimal is $\Theta(\varphi^n)$ ($\varphi$ being the golden ratio) and perhaps might prove to be of a significant difference... (Consider $n=40$ for instance). $\endgroup$ – Aryabhata Aug 8 '11 at 19:22
  • $\begingroup$ I'm not arguing against it being inefficient CPU-wise; my comment started off with "if you're not too worried about efficiency". I was just trying to save him the effort of digging into that code in case there's no need for it, which is more likely than not if he's generating lists of words. $\endgroup$ – joriki Aug 8 '11 at 19:31
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for this, it shows a way to approach it in a very intuitive way that I haven't thought of! $\endgroup$ – Dan Aug 8 '11 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.