Make sets disjoint without emptying them

Question

Suppose you have a set of sets of integers. It's possible that some of the sets will overlap (i.e. sharing elements). You could get rid of the overlaps by deleting elements from the sets, but then some of them might end up empty; that would be a shame. Can we make all the sets disjoint without emptying any of them?

Note that in this situation, there's never any reason to leave multiple elements in a set, so this problem can always be solved by reducing each set to just one element. That's the version of the problem we're solving here.

The task

Write a program or function, as follows:

Input: A list of sets of integers.

Output: A list of integers, of the same length as the input, for which:

• All integers in the output are distinct; and
• Each integer in the output is an element of the corresponding set of the input.

Clarifications

• You can represent a set as a list if you wish (or whatever's appropriate for your language), disregarding the order of elements.
• You don't have to handle the case where no solution exists (i.e. there will always be at least one solution).
• There might be more than one solution. Your algorithm must always produce a valid solution, but is allowed to be nondeterministic (i.e. it's OK if it picks a different valid solution each time it runs).
• The number of distinct integers appearing in the input, n, will be equal to the number of sets in the input, and for simplicity, will be the integers from 1 to n inclusive (as their actual values don't matter). It's up to you whether you wish to exploit this fact or not.

Testcases

[{1,2},{1,3},{1,4},{3,4}] -> [2,3,1,4] or [2,1,4,3]
[{1,3},{1,2,4},{2,3},{3},{2,3,4,5}] -> [1,4,2,3,5]
[{1,3,4},{2,3,5},{1,2},{4,5},{4,5}] -> [1,3,2,4,5] or [3,2,1,4,5] or [1,3,2,5,4] or [3,2,1,5,4]

Victory condition

A program requires an optimal time complexity to win, i.e. if an algorithm with a better time complexity is found, it disqualifies all slower entries. (You can assume that your language's builtins run as fast as possible, e.g. you can assume that a sorting builtin runs in time O(n log n). Likewise, assume that all integers of comparable size to n can be added, multiplied, etc. in constant time.)

Because an optimal time complexity is likely fairly easy to obtain in most languages, the winner will therefore be the shortest program among those with the winning time complexity, measured in bytes.

Answer 1

Jelly, 8 bytes

Œp⁼Q$ÐfḢ

Try it online!

Explanation

Œp⁼Q$ÐfḢ  Main Link
Œp        Cartesian Product of the elements; all possible lists
     Ðf   Filter; keep elements that are
  ⁼Q$     Equal to themselves uniquified
      Ḣ   Take the first one

Extremely inefficient. Asymptotic to ϴ(n^(n+1)) according to Misha Lavrov; I think it's right.

Answer 2

Haskell, 48 bytes

-1 byte thanks to nimi.

import Data.List
head.filter((==)<*>nub).mapM id

Try it online!

Answer 3

Wolfram Language (Mathematica), 87 bytes and ϴ(n³)

-Range[n=Length@#]/.Rule@@@FindIndependentEdgeSet[Join@@Table[-i->j,{i,n},{j,#[[i]]}]]&

Try it online!

Builds a bipartite graph whose vertices on one side are the sets (indexed by -1,-2,...,-n) and whose vertices on the other side are the elements 1,2,...,n, with an edge from -i to j when j is contained in the i-th set. Finds a perfect matching in this graph using a built-in. Then lists out the elements corresponding to -1,-2,...,-n in that order in the perfect matching.

Mathematica's FindIndependentEdgeSet is the bottleneck here; everything else takes O(n²) operations to do. Mathematica probably uses the Hungarian algorithm, and so I'll assume that it runs in ϴ(n³) time, though it's possible that Mathematica has a naive implementation with O(n⁴) complexity.

Answer 4

Mathematica 39 Bytes

Last@Union[DeleteDuplicates/@Tuples@#]&

On the issue of complexity, I think it is very dependent upon the length of each sublist, as well as a measure of how disjoint the sublists are.

So, I think this algorithm is O(n Log n + n^2 Log m) where m is roughly the average length of each sublist.

Something like this would have complexity O(a^n) where a>1 is a measure of the overlap in sublists:

(For[x={1,1},!DuplicateFreeQ@x,x=RandomChoice/@#];x)&

Hard to say which is really faster without knowing the properties of possible inputs.

Answer 5

05AB1E, 13 bytes, O(n!*n)

āœʒ‚øε`QO}P}н

Try it online! Explanation:

ā               Make a range 1..n
 œ              Generate all permutations
  ʒ        }    Filter
   ‚ø           Zip with input
     ε   }      Loop over sets
      `QO       Check each element for membership
          P     All sets must match
            н   Take the first result

Answer 6

Husk, 5 bytes

►oLuΠ

Try it online!

Explanation

Just saw the thing about complexity: As so often it is the case with golfing languages' solution they are not very efficient - this one has complexity O(n·nⁿ).

►(Lu)Π  -- input as a list of lists, for example: [[1,2],[1,3],[1,4],[3,4]]
     Π  -- cartesian product: [[1,1,1,3],...,[2,3,4,4]]
►(  )   -- maximum by the following function (eg. on [1,1,1,3]):
   u    --   deduplicate: [1,3]
  L     --   length: 2

Answer 7

Pyth, 9 bytes (ϴ(nⁿ⁺¹))

Since this works exactly like the Jelly solution, it most likely has the same complexity.

h{I#.nM*F

Try it here!

How?

h{I#.nM*F | Full program.

       *F | Fold Cartesian product.
    .nM   | Flatten each.
   #      | Keep those:
 {I         That are invariant over duplicate elements removal.
h         | Take the first element.

Answer 8

JavaScript (ES6), 74 73 bytes

1 byte saved, thanks to @Neil.

f=([a,...A],s=[],S)=>a?a.map(c=>s.includes(c)||(S=S||f(A,[...s,c])))&&S:s

Recursively iterates through the array looking for a solution.

Ungolfed:

f=(
   [a, ...A],                        //a is the first array, A is the rest
   s = [],                           //s is the current trial solution
   S                                 //S holds the solution (if one exists) at this branch
  )=>
     a ? a.map(                      //if we're not done, iterate through a
           c => s.includes(c) ||     //  if this element already exists, short-circuit
                (S = S ||            //  else if S has a solution, keep it
                 f(A, [...s, c])     //  else look for a solution down this branch
                )
         ) && S                      //return S

Test Cases:

f=([a,...A],s=[],S)=>a?a.map(c=>s.includes(c)||(S=S||f(A,[...s,c])))&&S:s

console.log(f([[1,2],[1,3],[1,4],[3,4]])) // [2,3,1,4] or [2,1,4,3]
console.log(f([[1,3],[1,2,4],[2,3],[3],[2,3,4,5]])) // [1,4,2,3,5]
console.log(f([[1,3,4],[2,3,5],[1,2],[4,5],[4,5]])) // [1,3,2,4,5] or [3,2,1,4,5] or [1,3,2,5,4] or [3,2,1,5,4],4]

Answer 9

Python3, 93 84 bytes

-9 bytes thanks to caird coinheringaahing

lambda I:next(filter(lambda x:len(x)==len({*x}),product(*I)))
from itertools import*

Try it online!