2
$\begingroup$

Given n elements, where the n elements are grouped into arbitrarily sized subsets, what is the Big Theta (tight bounds) of outputting all permutations of items from each subset?

Assume the elements are all unique.

For example:

n=2, `a b` there are two cases.
`(a), (b)` which has one permutation 1: `a, b`
`(a, b)` which has two permutations 1: `a`, 2: `b`

And then for a larger n:

n=3, `a b c` there are three cases.

3 subsets of 1 element: 1^3 permutations
`(a), (b), (c)` which has one combination 1: `a, b, c`

1 subset of 2 elements and 1 subset of 1 element: 2^1*1^1=2 permutations
`(a, b) (c)` which has two combinations 1: `ac`, 2: `bc`

1 subset of 3 elements: 3^1=3 permutations
`(a, b, c)` which has two combinations 1: `a`, 2: `b`, 3: `c`

Basically for a given n its the maximum value of S1*S2*S3... where S# is the size of subset #.

It's easy enough to demonstrate that big lambda is 2^(n/2).

And I think that 3^(n/3) may be a big omega.

I've been mulling this problem over for a little while now, if it's a known problem then I'd love to be pushed towards the right solution, but I've found that it's a bit difficult to search for.

$\endgroup$
3
$\begingroup$

If we denote by $q(n)$ the number of permutations, the first few values are $$\begin{array}{ccccccccc} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ q(n) & 1 & 1 & 3 & 6 & 14 & 25 & 56 & 97 \end{array}$$ This sequence can be found at the online encyclopedia of integer sequences, which is a really helpful site. It has a lot of information about the sequence in question, including the fact that you were right in your guess that $q(n)=\Theta(3^{n/3})$.

[Yes, I'm aware that this doesn't answer all of your question, since this only counts how many permutations there are, and doesn't enumerate them.]

$\endgroup$

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.