Clever Geek Handbook

Algorithm for a list of all possible sets of sets

I am having a hard time finding an algorithm to create a list of all possible sets of sets. By this I mean that given the set SI, I would like to know all the possible sets containing the sets of S. I probably didn't describe this very well, so I'll give an example that I hope makes sense.

If S ={1, 2, 3}

I'm looking for:

{{1, 2, 3}}

{{1, 2}, {3}}

{{1, 3}, {2}}

{{2, 3}, {1}}

{{1}, {2}, {3}}

While tedious, I can generate them manually, but I am having a hard time finding an algorithm that I can put into code.

+3


source to share


3 answers


You can do it recursively, and I'll show you how to find the answer for {1, 2, 3} from {1, 2}.

For a set with n elements, by solving the problem without the nth element as follows:

{{1 , 2}}
{{1}, {2}}

and then consider all the sets you create for n-1 items. and add the nth element to each element of this set once:

from {{1 , 2}}

we have:



{{1 , 2} , {3}}
{{1 , 2 , 3}}

from {{1}, {2}}

we have:

{{1, 3}, {2}}
{{1} ,{2, 3}}
{{1}, {2}, {3}}

As you can see now, we are solving the problem for three elements.

+1


source


you can use a recursive algorithm like the post below and the concept is the same. I've answered this before.



C ++ recursive algorithm for permutation

0


source


I see two independent tasks here:

  • For an ordered set S of N elements, all possible Permutations are created

  • Given the number N, output all sections from N, where one section defines how S is split into subsets. Here's the algorithm.

Then you need each section to apply for each permutation. This will result in all possible Q result sets , but some of them are duplicated, such as {{1, 2}, {3}} and {{2, 1} {3}}. The next step is to get rid of the duplicates. It's a little tricky. The solution is below.

UPDATE

Identifies a Q result set that is unique if it meets the following criteria.

Define Q as an ordered set: {P1, P2, P3, ...}, where Pi is also an ordered set of elements {Xi1, Xi2, ...}. Then Q is unique if:

  • the elements of each set Pi are arranged in ascending order (that is, Xi1 <= Xi2 <= Xi3 ...)
  • the sets Pi are arranged in ascending order of their sizes (i.e. sizeof (P1) <= sizeof (P2) <= sizeof (P3) ...)
  • the sets Pi are arranged in ascending order of their maxima (i.e., maximum_of (P1) <= maximum_of (P2) <= maximum_of (P3) ...), where Pi's maximum is its largest element.

Exampe:

{{1,2}, {3,4}, {6,5} , {7,8}} - not unique

{ {3,4}, {1,2} , {5,6}, {7,8}} - not unique

{{1,3}, {2,4}, {5,6}, {7,8}} - unique

{ {1,2}, {3} , {4}, {5,6}, {7,8}} - not the only one

0


source






More articles:


All Articles