Order sets of numbers for maximum distance

Question

You have (up to 100) distinct sets of (2-4) numbers. The order of the sets or numbers in the sets does not matter. The highest number relates to the number of sets and goes up to 30. Like:

{1 2 3 4} {1 2 3 5} {1 2 3} {1 2 4 5} {6 2 4} {6 7 8 9} {6 7 9} {7 8 9} {2 4 8 9}

The goal is, to arrange these sets in a particular order, where two successive sets do not contain a common number. That is

{1 2 3 4} {2 4 8 9}

is bad (because of the 2). And

{1 2 3 4} {6 7 8 9}

is good.

Of course, especially in the given example, this is not possible for the whole set of sets. But the number of sets which violate the rules should approximately be minimized.

I assume, some brute-force + scoring algorithm is not feasible with the relatively large number of sets. Do you have any other ideas or hints for a deterministic algorithm to solve this problem?

Do you think, a shuffle + score algorithm could find decent solutions (in some restricted time frame, like 5 seconds, standard computer)?

Answer 1

You can create a graph out of your sets, where vertices are the sets and there are edges between them if they can be successive in the list (i.e. have no common element).

On this you can run any algorithm that finds a Hamiltonian path, which is an NP-hard problem.

Answer 2

Yes, I think that possible if algorithm is properly designed. Here is the example of solving similar problem for 60 "sets" in 2.7*10^5 operations. That number seems adequate for an average modern computer.