fundo

No momento em que escrevemos isso, o problema P vs NP ainda não foi resolvido, mas você deve ter ouvido falar do novo artigo de Norbert Blum reivindicando a prova de que P! = NP, que já é suspeito de estar errado (mas veremos).

O problema discutido neste artigo é o problema da camarilha . Pelo menos é o que li em um artigo de jornal, então me corrija se estiver errado, mas, de qualquer forma, gostaria que você escrevesse um programa que resolva a seguinte variante:

A tarefa

Suponha que tenhamos uma escola grande com muitos alunos. Cada um desses alunos tem alguns amigos nesta escola. Uma camarilha de estudantes é um grupo composto apenas por alunos que são amigos um do outro .

Seu programa receberá pares de alunos amigos como entrada. A partir dessas informações, o programa deve encontrar o tamanho da maior clique . Os alunos são identificados por IDs inteiros .

Se você preferir termos matemáticos, isso significa que você alimenta as bordas de um gráfico não direcionado, identificado por dois nós cada.

Entrada

Sua entrada será uma lista não vazia de pares inteiros positivos, por exemplo [[1,2],[2,5],[1,5]]. Você pode receber esta entrada de qualquer forma sensata, por exemplo, como uma matriz de matrizes, como linhas de texto contendo dois números cada, etc ...

Saída

A saída esperada é um número único n >= 2: o tamanho da maior clique. Com a entrada de exemplo acima, o resultado seria 3, pois todos os alunos ( 1, 2e 5) são amigos um do outro.

Casos de teste

[[1,2]]
=> 2

[[1,2],[3,1],[3,4]]
=> 2

[[1,2],[2,5],[1,5]]
=> 3

[[2,5],[2,3],[4,17],[1,3],[7,13],[5,3],[4,3],[4,1],[1,5],[5,4]]
=> 4 (the largest clique is [1,3,4,5])

[[15,1073],[23,764],[23,1073],[12,47],[47,15],[1073,764]]
=> 3 (the largest clique is [23,764,1073])

[[1296,316],[1650,316],[1296,1650],[1296,52],[1650,711],[711,316],[1650,52],
 [52,711],[1296,711],[52,316],[52,1565],[1565,1296],[1565,316],[1650,1565],
 [1296,138],[1565,138],[1565,711],[138,1650],[711,138],[138,144],[144,1860],
 [1296,1860],[1860,52],[711,1639]]
=> 6 (the largest clique is [52,316,711,1296,1565,1650])

Você pode usar essa implementação de referência (estúpida) (imprime saída extra com -dsinalizador) para verificar os resultados de outros casos de teste.

As regras

1. Seu programa não precisa de um resultado definido com entrada inválida. Então você pode assumir que:
   • você sempre terá pelo menos um par de IDs
   • cada par consiste em dois IDs diferentes
   • nenhum par aparece duas vezes (a troca dos locais dos IDs ainda seria o mesmo par)
2. Seu algoritmo não tem permissão para definir um limite superior no tamanho da entrada. Limitações puramente técnicas e definidas pelo seu idioma / ambiente (como tamanho da pilha, tempo de computação etc.) são obviamente inevitáveis.
3. As brechas padrão são proibidas.
4. Isso é código-golfe , então o código mais curto, medido em bytes, vence.
5. Se o seu algoritmo tiver complexidade de tempo polinomial, você pontua -1imediatamente, independentemente do tamanho do código, mas nesse caso, convém enviar sua solução para outro lugar. ;)

Geléia ,  15 18  16 bytes

+3 bytes para corrigir erros no meu método.
-2 bytes graças a milhas (observando que n × (n-1) ÷ 2 = nC2 )

ẎQL©c2⁼Lȧ®
ŒPÇ€Ṁ

Um link monádico que pega a lista de amizades (arestas) e retorna um número inteiro.

Experimente online! forma o conjunto de potência das bordas da memória, tornando-se ineficiente no espaço e no tempo (sim, isso é O (2 ⁿ ) pessoal)!

Quão?

ẎQL©c2⁼Lȧ® - Link 1, isClique?: list, edges  e.g. [[1,3],[2,3],[3,4],[4,1],[4,2],[2,1]]
Ẏ          - tighten                              [ 1,3 , 2,3 , 3,4 , 4,1 , 4,2 , 2,1 ]
 Q         - de-duplicate (gets unique ids)          [1,3,2,4]
  L        - length (get number of people involved)  4
   ©       - (copy to the register)
    c2     - combinations of 2 (z-choose-2)          6
       L   - length (of edges)                       6
      ⁼    - equal?                                  1
         ® - recall value from register              4
        ȧ  - logical and                             4
           - (Note: the number of edges of a clique of size n is n*(n-1) and we're
           -  guaranteed no repeated edges and that all edges are two distinct ids)

ŒPÇ€Ṁ - Link: list of lists, edges
ŒP    - power-set (all possible sets of edges (as lists))
  Ç€  - call last link (1) as a monad for €ach
    Ṁ - maximum

Mathematica, 34 bytes

Tr[1^#&@@FindClique[#<->#2&@@@#]]&  

Basicamente, o FindClique faz o trabalho e "encontra uma maior clique no gráfico g".
Todo o resto é converter a lista de entrada em gráfico

Entrada

[{{2, 5}, {2, 3}, {4, 17}, {1, 3}, {7, 13}, {5, 3}, {4, 3}, {4, 1}, {1, 5}, {5, 4}}]

Saída

4

Entrada

[{{1296, 316}, {1650, 316}, {1296, 1650}, {1296, 52}, {1650, 711}, {711, 316}, {1650, 52}, {52, 711}, {1296, 711}, {52, 316}, {52, 1565}, {1565, 1296}, {1565, 316}, {1650, 1565}, {1296, 138}, {1565, 138}, {1565 , 711}, {138, 1650}, {711, 138}, {138, 144}, {144, 1860}, {1296, 1860}, {1860, 52}, {711, 1639}}]

Saída

6

thanx @Kelly Lowder por -10 bytes

Gelatina , 20 bytes

ŒPẎ€µQL’=ċЀ`ẠµÐfṪQL

Experimente online!

Claro que isso não merece o milhão: p

Isso teria superado o Pyth, se não fosse o µ(...)µe os 2 bytes Ðf.

J , 36 bytes

[:>./](#(]*[=2!])#@~.@,)@#~2#:@i.@^#

Experimente online!

É executado no tempo O (2 ⁿ ) em que n é o número de pares.

Uma solução mais rápida para 65 bytes é

3 :'$>{._2{~.@((+.&(e.&y)&<|.)@(-.,-.~)&>/#&,/:~@~.@,&.>/)~^:a:y'

Experimente online!

Explicação

[:>./](#(]*[=2!])#@~.@,)@#~2#:@i.@^#  Input: list of pairs
                                   #  Length
                           2      ^   2^n
                               i.@    Range [0, 2^n)
                            #:@       Binary
                         #~           Copy
      (                )@             For each
                      ,                 Flatten
                   ~.@                  Unique
                 #@                     Length
        (       )                       Dyad with RHS at previous and LHS as next
               ]                          Get RHS
             2!                           Binomial coefficient, choose 2
            =                             Equals
           [                              Get LHS
          *                               Times
         ]                                Get RHS
       #                                Length
[:>./                                 Reduce using maximum

Pitão, 19 bytes

l{ef.AqLtl{T/LTTsMy

Experimente aqui.

Python 2 , 180 bytes

G=input()
m=0
L=len
for i in range(2**L(G)):
 u=[];p=sum([G[j]for j in range(L(G))if 2**j&i],u)
 for j in p:u+=[j][j in u:]
 m=max(m,L(u)*all(p.count(j)==L(u)-1for j in u))
print m

Experimente online!

-2 graças a shooqie .
-1 graças ao Sr. Xcoder .
-3 graças a recursiva .

Pitão, 28 bytes

l{sSef<T.{SMQm.{ft{T.Cd2yS{s

Experimente online

Explicação

l{sSef<T.{SMQm.{ft{T.Cd2yS{s
                         S{sQ  Get the distinct nodes in the (implicit) input.
                        y      Take every subset.
             m      .Cd2       Get the pairs...
                ft{T           ... without the [x, x] pairs...
              .{               ... as sets.
     f<T                        Choose the ones...
        .{  Q                   ... which are subsets of the input...
          SM                    ... with edges in sorted order.
    e                           Take the last element (largest clique).
l{sS                            Get the number of distinct nodes.

Python 3 , 162 159 bytes

lambda x,f=lambda x:{i for s in x for i in s}:len(f(x))if all([(y,z)in x or(z,y)in x for y in f(x)for z in f(x)if y<z])else max(c(x.difference({y}))for y in x)

Experimente online!

A função c assume vértices na forma de um conjunto de tuplas classificadas ({(x, y), ...} onde x é menor que y). Uma função chamada "entrada" está no cabeçalho do TIO para testar com dados na lista de formato de lista não classificada . Se clique, retorna comprimento. Se não for clique, retorna o tamanho máximo de clique dos vértices, menos um vértice para cada vértice nos vértices. Excede o tempo no último caso de teste no TIO

Atualize: "ou (z, y) em x" parte adicionada para remover a dependência da classificação "f = lambda x: {i por s em x por i em s}" em vez de itertools.chain agrupado em conjunto.

- menos 3 bytes graças a @ Jonathan Allen

05AB1E , 19 bytes

怘ʒDÙg<s{γ€gQP}θÙg

Experimente online!

Gelatina , 28 bytes

œ^e³;U¤
Œcç/Ðfœ|Ṣ¥/€QµÐĿ-ịḢL

Experimente online!

Solução mais rápida capaz de resolver o último caso de teste em um segundo no TIO.

Java + Goiaba 23.0, 35 + 294 = 329 bytes

import com.google.common.collect.*;
a->{int l=0,o=1,c,z=a.size();for(;o>0&l<z;){o=0;c:for(Iterable<int[]>s:Sets.combinations(a,l*(l+1)/2)){Multiset<Integer>m=TreeMultiset.create();for(int[]x:s){m.add(x[0]);m.add(x[1]);}c=m.elementSet().size();for(int e:m.elementSet())if (m.count(e)!=c-1)continue c;l+=o=1;break;}}return z<3?2:l;}

Esse algoritmo não está representado graficamente, mas está gerando todas as combinações de pares, de um tamanho específico. Alimento todas as combinações de pares em um multiset e verifico se todas elas têm o tamanho esperado (o número de entradas exclusivas - 1). Se o fizerem, encontrei uma camarilha e vou procurar uma maior.

Na biblioteca do Guava, eu uso o novo combinationsmétodo e o tipo de coleção de ferramentas Multiset.

Ungolfed

import com.google.common.collect.*;
import java.util.function.*;

public class Main {

  public static void main(String[] args) {
    ToIntFunction<java.util.Set<int[]>> f
        = a -> {
          int l = 0, o = 1, c, z = a.size();
          for (; o > 0 & l < z;) {
            o = 0;
            c:
            for (Iterable<int[]> s : Sets.combinations(a, l * (l + 1) / 2)) {
              Multiset<Integer> m = TreeMultiset.create();
              for (int[] x : s) {
                m.add(x[0]);
                m.add(x[1]);
              }
              c = m.elementSet().size();
              for (int e : m.elementSet()) {
                if (m.count(e) != c - 1) {
                  continue c;
                }
              }
              l += o = 1;
              break;
            }
          }
          return z < 3 ? 2 : l;
        };
    int[][][] tests = {
      {{1, 2}},
      {{1, 2}, {3, 1}, {3, 4}},
      {{1, 2}, {2, 5}, {1, 5}},
      {{2, 5}, {2, 3}, {4, 17}, {1, 3}, {7, 13}, {5, 3}, {4, 3}, {4, 1}, {1, 5}, {5, 4}},
      {{15, 1073}, {23, 764}, {23, 1073}, {12, 47}, {47, 15}, {1073, 764}},
      {{1296, 316}, {1650, 316}, {1296, 1650}, {1296, 52}, {1650, 711}, {711, 316}, {1650, 52}, {52, 711}, {1296, 711}, {52, 316}, {52, 1565}, {1565, 1296}, {1565, 316}, {1650, 1565}, {1296, 138}, {1565, 138}, {1565, 711}, {138, 1650}, {711, 138}, {138, 144}, {144, 1860}, {1296, 1860}, {1860, 52}, {711, 1639}}
    };
    for (int[][] test : tests) {
      java.util.Set<int[]> s = new java.util.HashSet<int[]>();
      for (int[] t : test) {
        s.add(t);
      }
      System.out.println(f.applyAsInt(s));
    }
  }
}

Python 2 , 102 bytes

def f(g):
 x=g
 while x:y=x;x=map(set,{tuple(u|v)for u in x for v in x if u^v in g})
 return len(y[0])

Experimente online!

Código da máquina 6502 (C64), 774703 bytes

(Eu só tinha que fazer isso, meu C64 pode fazer tudo ... hehe)

hexdump:

00 C0 A9 00 A2 08 9D 08 00 CA 10 FA A2 04 9D FB 00 CA 10 FA 20 54 C0 B0 20 AD 
C9 C2 AE CA C2 20 92 C1 B0 31 8D 31 C0 AD CB C2 AE CC C2 20 92 C1 B0 23 A2 FF 
20 FE C1 90 DB 20 6A C2 20 C1 C1 B0 05 20 6A C2 50 F6 A5 FB 8D D3 C2 20 43 C1 
A9 CD A0 C2 20 1E AB 60 A2 00 86 CC 8E 61 C0 20 E4 FF F0 FB A2 FF C9 0D F0 10 
E0 0B 10 0C 9D BD C2 20 D2 FF E8 8E 61 C0 D0 E5 C6 CC A9 20 20 D2 FF A9 0D 20 
D2 FF A9 00 9D BD C2 AA BD BD C2 F0 5C C9 30 30 0E C9 3A 10 0A 9D CD C2 E8 E0 
06 F0 4C D0 E9 C9 20 D0 46 A9 00 9D CD C2 E8 8E BC C0 20 EB C0 AD D3 C2 8D C9 
C2 AD D4 C2 8D CA C2 A2 FF A0 00 BD BD C2 F0 0F C9 30 30 21 C9 3A 10 1D 99 CD 
C2 C8 E8 D0 EC A9 00 99 CD C2 20 EB C0 AD D3 C2 8D CB C2 AD D4 C2 8D CC C2 18 
60 38 60 A2 FF E8 BD CD C2 D0 FA A0 06 88 CA 30 0A BD CD C2 29 0F 99 CD C2 10 
F2 A9 00 99 CD C2 88 10 F8 A9 00 8D D3 C2 8D D4 C2 A2 10 A0 7B 18 B9 53 C2 90 
02 09 10 4A 99 53 C2 C8 10 F2 6E D4 C2 6E D3 C2 CA D0 01 60 A0 04 B9 CE C2 C9 
08 30 05 E9 03 99 CE C2 88 10 F1 30 D2 A2 06 A9 00 9D CC C2 CA D0 FA A2 08 A0 
04 B9 CE C2 C9 05 30 05 69 02 99 CE C2 88 10 F1 A0 04 0E D3 C2 B9 CE C2 2A C9 
10 29 0F 99 CE C2 88 10 F2 CA D0 D9 C8 B9 CD C2 F0 FA 09 30 9D CD C2 E8 C8 C0 
06 F0 05 B9 CD C2 90 F0 A9 00 9D CD C2 60 85 0A A4 09 C0 00 F0 11 88 B9 D5 C2 
C5 0A D0 F4 8A D9 D5 C3 D0 EE 98 18 60 A4 09 E6 09 D0 01 60 A5 0A 99 D5 C2 8A 
99 D5 C3 98 99 D5 C4 18 60 A6 0B E4 09 30 01 60 BD D5 C5 C5 0B 30 09 A9 00 9D 
D5 C5 E6 0B D0 E9 A8 FE D5 C5 8A 29 01 D0 02 A0 00 BD D5 C4 59 D5 C4 9D D5 C4 
59 D5 C4 99 D5 C4 5D D5 C4 9D D5 C4 A9 00 85 0B 18 60 A8 A5 0C D0 08 A9 20 C5 
0D F0 21 A5 0C 8D 1E C2 8D 21 C2 A5 0D 09 60 8D 1F C2 49 E0 8D 22 C2 8C FF FF 
8E FF FF E6 0C D0 02 E6 0D 18 60 86 0E 84 0F A5 0D 09 60 8D 54 C2 49 E0 8D 5F 
C2 A6 0C CA E0 FF D0 10 AC 54 C2 88 C0 60 10 02 18 60 8C 54 C2 CE 5F C2 BD 00 
FF C5 0E F0 04 C5 0F D0 E0 BD 00 FF C5 0E F0 04 C5 0F D0 D5 38 60 A2 00 86 FC 
86 FD 86 FE BD D5 C4 A8 A6 FE E4 FC 10 11 BD D5 C7 AA 20 2B C2 90 14 E6 FE A6 
FE E4 FC D0 EF A6 FD BD D5 C4 A6 FC E6 FC 9D D5 C7 E6 FD A6 FD E4 09 D0 16 A6 
FB E4 FC 10 0F A2 00 BD D5 C7 9D D5 C6 E8 E4 FC D0 F5 86 FB 60 A0 00 84 FE F0 
B5

Demonstração online

Uso: Comece com sys49152e insira os pares um por linha, como por exemplo

15 1073
23 764
23 1073
12 47
47 15
1073 764

O backsapce não é tratado durante a entrada (mas se você usar vice, basta copiar e colar sua entrada no emulador). Digite uma linha vazia para iniciar o cálculo.

Isso é muito grande para postar uma lista de desmontagem explicativa aqui, mas você pode procurar a fonte de montagem no estilo ca65 . O algoritmo é muito ineficiente, gera todas as permutações possíveis dos nós e, com cada um deles, cria avidamente um clique, checando todas as bordas. Isso permite uma eficiência de espaço de O (n) (meio importante em uma máquina com essa pequena RAM), mas tem uma eficiência de tempo de execução horrível (*) . Os limites teóricos são de até 256 nós e até 8192 arestas.

• -71 bytes: rotina otimizada para verificação de bordas e uso de zeropage

Há uma versão maior ( 883 805 bytes) com melhores recursos:

• feedback visual durante o cálculo (cada permutação dos nós altera a cor da borda)
• usa comutação bancária para armazenar as bordas na RAM "escondidas" pelas ROMs para economizar espaço
• gera o tamanho e os nós da camarilha máxima encontrada

Demonstração online

Procurar fonte

(*) O último caso de teste leva algo entre 12 e 20 horas (eu estava dormindo quando finalmente terminou). Os outros casos de teste terminam na pior das hipóteses em alguns minutos.