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.
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=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
S# is the size of subset
It's easy enough to demonstrate that big lambda is
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.