1
$\begingroup$

I have a problem where I have a set of subsets and I want to create the shortest list where I can find all subsets in it. Each subset must be a block of that list.

The input is a set of set of elements. The elements can be duplicate between different sets, but are unique within one set.

The output is a list where the order of the elements matter. This list can have duplicate elements. The wanted property of that list is that we need to find all input sets within the list somewhere. By "block" I mean that the elements of a set must be contiguous within the list. However, the order of the set elements within that block doesn't matter in the output

My question is "How to find that list?"

What could be a good algorithm to create that list?

Example:

Given the sets

A = { 1, 3, 5 }

B = { 2, 4, 5 }

C = { 4, 5 }

D = { 1, 4 }

then, one possible output list is [ 2, 4, 5, 3, 1, 4 ].

We can find in order

  • B : [ (2, 4, 5), 3, 1, 4 ]

  • C : [ 2, (4, 5), 3, 1, 4 ]

  • A : [ 2, 4, (5, 3, 1), 4 ]

  • D : [ 2, 4, 5, 3, (1, 4) ]

It seems to me that that kind of problem looks classic. Without doing all the work, someone could point out a similar problem that I can refer to, or giving just a head start.

$\endgroup$
  • $\begingroup$ Related problem. $\endgroup$ – Raphael May 19 '16 at 17:14
  • $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael May 19 '16 at 17:14
  • $\begingroup$ It is very similar to the shortest common supersequence problem. However, the elements within a set (or sequence) are unique (that means that the longest common sequence of two sets/sequence is simply their intersection). Furthermore, I can have more than just two sets as input. $\endgroup$ – user51424 May 19 '16 at 19:36

Your Answer

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

Browse other questions tagged or ask your own question.