MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Generate permutations of a group of words respecting order [closed]

Hello, 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 permutations 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.

-
This question is more appropriate for math.stackexchange. You might observe that the number of desired arrangements d(n) satisfies a recurrence similar to that of the Fibonacci sequence. You might also find iterative solutions that are derived from a tail recursion solution to the problem. Gerhard "Ask Me About System Design" Paseman, 2011.08.08 – Gerhard Paseman Aug 8 2011 at 18:17
Thank you, will do. – Dan Aug 8 2011 at 18:46
One way to solve this would be to have: (1) a good way of ordering the Fibonacci(n+1) solutions for a set of n; (2) a routine that, given the kth word for n, spits out the (k+1)st. It turns out that one ordering that works, if you re-encode your tuples correctly, is lexicographic order. In "Matters Computational" (jjj.de/fxt/fxtbook.pdf) pp. 75-76, Jorg Arndt gives C code for this, which involves some low-level bit-hacking. (I can't read C so I can't explain exactly how it works.) – Michael Lugo Aug 8 2011 at 21:52