Suponha que você tenha um conjunto de conjuntos de números inteiros. É possível que alguns dos conjuntos se sobreponham (isto é, compartilhando elementos). Você pode se livrar das sobreposições excluindo elementos dos conjuntos, mas alguns deles podem acabar vazios; isso seria uma vergonha. Podemos tornar todos os conjuntos disjuntos sem esvaziar nenhum deles?

Observe que, nessa situação, nunca há motivo para deixar vários elementos em um conjunto; portanto, esse problema sempre pode ser resolvido reduzindo-se cada conjunto a apenas um elemento. Essa é a versão do problema que estamos resolvendo aqui.

A tarefa

Escreva um programa ou função, da seguinte maneira:

Entrada : uma lista de conjuntos de números inteiros.

Saída : uma lista de números inteiros, do mesmo tamanho que a entrada, para a qual:

• Todos os números inteiros na saída são distintos; e
• Cada número inteiro na saída é um elemento do conjunto correspondente da entrada.

Esclarecimentos

• Você pode representar um conjunto como uma lista, se desejar (ou o que for apropriado para o seu idioma), desconsiderando a ordem dos elementos.
• Você não precisa lidar com o caso em que não existe solução (ou seja, sempre haverá pelo menos uma solução).
• Pode haver mais de uma solução. Seu algoritmo sempre deve produzir uma solução válida, mas pode ser não determinístico (ou seja, tudo bem se ele escolher uma solução válida diferente toda vez que for executado).
• O número de números inteiros distintos que aparecem na entrada, n , será igual ao número de conjuntos na entrada e, por simplicidade, serão os números inteiros de 1 a n, inclusive (já que seus valores reais não importam). Depende de você se você deseja explorar esse fato ou não.

Casos de teste

[{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]

Condição de vitória

Um programa requer uma complexidade de tempo ideal para vencer, ou seja, se um algoritmo com uma complexidade de tempo melhor for encontrado, desqualifica todas as entradas mais lentas. (Você pode supor que os componentes internos do seu idioma sejam executados o mais rápido possível, por exemplo, você pode assumir que um componente ordenado seja executado no tempo O (n log n). Da mesma forma, suponha que todos os números inteiros de tamanho comparável a n possam ser adicionados, multiplicados, etc. em tempo constante.)

Como é provável que seja fácil obter uma complexidade de tempo ideal na maioria dos idiomas, o vencedor será, portanto, o programa mais curto entre aqueles com complexidade de tempo vencedora, medidos em bytes.

Geléia , 8 bytes

Œp⁼Q$ÐfḢ

Experimente online!

Explicação

Œ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

Extremamente ineficiente. Assintótico de ϴ(n^(n+1))acordo com Misha Lavrov; Eu acho que está certo.

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

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

Experimente online!

Constrói um gráfico bipartido cujos vértices de um lado são os conjuntos (indexados por -1,-2,...,-n) e cujos vértices do outro lado são os elementos 1,2,...,n, com uma aresta de -iaté jquando jcontida no i-ésimo conjunto. Encontra uma correspondência perfeita neste gráfico usando um built-in. Em seguida, lista os elementos correspondentes -1,-2,...,-nnessa ordem na correspondência perfeita.

O Mathematica FindIndependentEdgeSeté o gargalo aqui; tudo o mais exige operações O (n ² ). O Mathematica provavelmente usa o algoritmo húngaro e, portanto, assumirei que ele é executado em ϴ (n ³ ) , embora seja possível que o Mathematica tenha uma implementação ingênua com complexidade O (n ⁴ ).

Haskell , 48 bytes

-1 byte graças a nimi.

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

Experimente online!

Mathematica 39 Bytes

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

Na questão da complexidade, acho que é muito dependente do tamanho de cada sub-lista, bem como uma medida de quão disjuntos são os sublistas.

Então, acho que esse algoritmo é O (n Log n + n ^ 2 Log m), em que m é aproximadamente o comprimento médio de cada sub-lista.

Algo assim teria complexidade O (a ^ n) onde a> 1 é uma medida da sobreposição em sublistas:

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

Difícil dizer qual é realmente mais rápido sem conhecer as propriedades de possíveis entradas.

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

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

Experimente online! Explicação:

ā               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

Casca , 5 bytes

►oLuΠ

Experimente online!

Explicação

Acabei de ver o que é complexidade: como costuma acontecer na solução das linguagens de golfe, elas não são muito eficientes - essa possui complexidade 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

Pitão , 9 bytes (ϴ (n ^{n + 1} ))

Como isso funciona exatamente como a solução Jelly, provavelmente tem a mesma complexidade.

h{I#.nM*F

Experimente aqui!

Quão?

h {I # .nM * F | Programa completo.

       * F Dobre o produto cartesiano.
    .nM | Achate cada um.
   # | Mantenha aqueles:
 {I que são invariantes sobre a remoção de elementos duplicados.
h Pegue o primeiro elemento.

JavaScript (ES6), 74 73 bytes

1 byte salvo, graças a @Neil.

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

Iera repetidamente pela matriz, procurando uma solução.

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

Casos de teste:

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]

Python3, 93 84 bytes

-9 bytes graças a caird coinheringaahing

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

Experimente online!