Haz el NP: encuentra la camarilla más grande

22

Fondo

En el momento de escribir esto, el problema P vs NP aún no se ha resuelto, pero es posible que haya oído hablar del nuevo artículo de Norbert Blum que afirma que P! = NP, que ya se sospecha que es erróneo (pero ya veremos).

El problema discutido en este documento es el problema de la camarilla . Al menos eso es lo que leo en un artículo de periódico, así que corrígeme si me equivoco, pero en cualquier caso, me gustaría que escribieras un programa que resuelva la siguiente variante:

La tarea

Supongamos que tenemos una escuela grande con muchos estudiantes. Cada uno de estos estudiantes tiene algunos amigos en esta escuela. Una camarilla de estudiantes es un grupo compuesto solo por estudiantes que son amigos entre sí .

Su programa recibirá pares de estudiantes que son amigos como entrada. A partir de esta información, el programa debe encontrar el tamaño de la camarilla más grande . Los estudiantes se identifican por ID enteros .

Si prefiere términos matemáticos, esto significa que está alimentado los bordes de un gráfico no dirigido, identificado por dos nodos cada uno.

Entrada

Su entrada será una lista no vacía de pares enteros positivos, por ejemplo [[1,2],[2,5],[1,5]]. Puede tomar esta entrada en cualquier forma sensata, por ejemplo, como una matriz de matrices, como líneas de texto que contienen dos números cada una, etc.

Salida

El resultado esperado es un número único n >= 2: el tamaño de la camarilla más grande. Con el ejemplo de entrada anterior, el resultado sería 3, ya que todos los estudiantes ( 1, 2y 5) son amigos entre sí.

Casos de prueba

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

Puede usar esta implementación de referencia (estúpida) (imprime una salida adicional con una -dmarca) para verificar los resultados de otros casos de prueba.

Las normas

  1. Su programa no necesita un resultado definido en una entrada no válida. Entonces puedes asumir que:
    • siempre obtendrá al menos un par de ID
    • cada par consta de dos ID diferentes
    • ningún par aparece dos veces (intercambiar los lugares de las ID seguiría siendo el mismo par)
  2. Su algoritmo no puede establecer un límite superior en el tamaño de entrada. Por supuesto, las limitaciones y limitaciones puramente técnicas establecidas por su idioma / entorno (como el tamaño de la pila, el tiempo de cálculo, etc.) son inevitables.
  3. Las lagunas estándar están prohibidas.
  4. Este es el , por lo que gana el código más corto, medido en bytes.
  5. Si su algoritmo tiene una complejidad de tiempo polinomial, obtiene -1una puntuación inmediata independientemente del tamaño de su código, pero en ese caso, es posible que desee enviar su solución a otro lugar. ;)
Felix Palmen
fuente
44
Casi puedo garantizar que habrá alguien que lo haga (o intente), por lo que sería más seguro eliminarlo. Si desea recompensar a las personas por hacerlo, puede ofrecer una recompensa por la respuesta más corta que lo haga en tiempo polinómico.
caird coinheringaahing
44
@cairdcoinheringaahing si alguien lo hace, -1es bien merecido ;)
Felix Palmen
13
@cairdcoinheringaahing Si alguien logró demostrar que P = NP, tener la puntuación más baja automática en un problema de código de golf es la menor de nuestras preocupaciones. Dicho esto, la Regla 5 realmente no contribuye mucho al desafío, por lo que estoy de acuerdo en que debería eliminarse.
Mego
11
@Mego simplemente contribuye con una broma y una pequeña bonificación al 1M ofrecido por CMI.
Felix Palmen
30
Bueno, no lo haré, a favor de las pocas personas que tienen algún sentido del "humor científico". Por favor no comente más sugerencias sobre esto, gracias :)
Felix Palmen

Respuestas:

6

Jalea ,  15 18  16 bytes

+3 bytes para corregir errores en mi método.
-2 bytes gracias a millas (observando que n × (n-1) ÷ 2 = nC2 )

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

Un enlace monádico que toma la lista de amistades (bordes) y devuelve un número entero.

Pruébalo en línea! forma el conjunto de potencia de los bordes en la memoria, por lo que es ineficiente tanto en espacio como en tiempo (sí, eso es O (2 n ) amigos).

¿Cómo?

Ẏ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
Jonathan Allan
fuente
Wow, explicación cuando tengas tiempo por favor
Sr. Xcoder
@EriktheOutgolfer Estoy de acuerdo. Probablemente pueda agregar código para recuperar ...
Jonathan Allan
Continuemos esta discusión en el chat .
Erik the Outgolfer
16 bytes
millas
@miles - bueno, acabo de pasar un tiempo tratando de obtener un 15 de eso, ¡siento que debería ser posible!
Jonathan Allan
13

Mathematica, 34 bytes

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

Básicamente, FindClique hace el trabajo y "encuentra una camarilla más grande en el gráfico g".
Todo lo demás está convirtiendo input-list en graph

Entrada

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

Salida

4 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}}]

Salida

6 6

Gracias @ Kelly Lowder para -10 bytes

J42161217
fuente
23
Por supuesto, Mathematica tiene algo incorporado para esto.
Erik the Outgolfer
1
Afeitarse 10 Bytes conTr[1^#&@@FindClique[#<->#2&@@@#]]&
Kelly Lowder
12
FindCliqueಠ ___ ಠ
Sr. Xcoder
6

Jalea , 20 bytes

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

Pruébalo en línea!

Por supuesto, esto no merece el millón: p

Esto hubiera vencido a Pyth, si no fuera por el µ(...)µy 2 bytes Ðf.

Erik el Outgolfer
fuente
Asombroso. Mejor me rindo ahora.
Mark Thomas
@FelixPalmen fuerza bruta: p
Erik the Outgolfer
@EriktheOutgolfer No quise decir el tiempo de ejecución del código;)
Felix Palmen
@FelixPalmen Quiero decir, el enfoque de la fuerza bruta no necesita pensar mucho: p
Erik the Outgolfer
Da un error de memoria con el caso de prueba más grande :( Por supuesto, todavía es válido, esta es una "limitación técnica", pero solo por curiosidad, ¿hay alguna manera de aumentar los recursos disponibles con gelatina?
Felix Palmen
3

J , 36 bytes

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

Pruébalo en línea!

Se ejecuta en el tiempo O (2 n ) donde n es el número de pares.

Una solución más rápida para 65 bytes es

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

Pruébalo en línea!

Explicación

[:>./](#(]*[=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
millas
fuente
2

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

Pruébalo en línea!

-2 gracias a shooqie .
-1 gracias al Sr. Xcoder .
-3 gracias a recursivo .

Erik el Outgolfer
fuente
Puede guardar dos bytes asignándolos lena una variable
shooqie
183 bytes . (x not in y)significa 0**(x in y).
Sr. Xcoder
@ Mr.Xcoder ¡Sabía que había una forma de acortarlo! ¡Gracias!
Erik the Outgolfer
Nunca lo había usado antes, solo un truco que se me cruzó por la mente hace un par de días pero que aún no podía encontrar.
Sr. Xcoder
@ Mr.Xcoder No importa, si funciona, ¿por qué no? : D BTW también puede reemplazar 0**con -~-.
Erik the Outgolfer
1

Pyth, 28 bytes

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

Pruébalo en línea

Explicación

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.

fuente
1

Python 3 , 162159 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)

Pruébalo en línea!

La función c toma vértices en forma de un conjunto de tuplas ordenadas ({(x, y), ...} donde x es menor que y). Una función llamada "entrada" está en el encabezado TIO para probar con datos en una lista de formato de listas sin clasificar . Si camarilla, devuelve longitud. Si no es camarilla, devuelve el tamaño máximo de camarilla de los vértices, menos un vértice por cada vértice en los vértices. Supera el tiempo en el último caso de prueba en TIO

Actualización: se agregó la porción "o (z, y) en x" para eliminar la dependencia de la clasificación "f = lambda x: {i para s en x para i en s}" en lugar de itertools.chain envuelto en el conjunto.

-minus 3 bytes gracias a @Jonathan Allen

Conner Johnston
fuente
Aparte: no necesita nombrar c, por lo que puede eliminarlo c=(debe colocarlo c=\al final del encabezado y colocarlo lambdaen la parte superior del bloque de código para TIO)
Jonathan Allan
También puede deshacerse des y reemplazar s(...)con {*...}lo que permite la eliminación de algunos espacios también.
Jonathan Allan
1
@JonathanAllan gracias, arreglo arreglado
Conner Johnston
1

Jalea , 28 bytes

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

Pruébalo en línea!

Solución más rápida que puede resolver el último caso de prueba en un segundo en TIO.

millas
fuente
¿Y qué complejidad tiene esto? Si es algo más bajo que O (2ⁿ), entonces merece $ 1,000,000.
Erik the Outgolfer
1
@EriktheOutgolfer, está equivocado, hay algoritmos que tienen un tiempo de ejecución O (1.1888ⁿ) .
rus9384
Además de eso, por un valor de un millón, nsolo puede aparecer en las bases :)
Felix Palmen
@FelixPalmen, o no puede. De todos modos, para millones, se debe probar una de dos declaraciones.
rus9384
1
Creo que esto es O (1.414 ^ n). Puede ver un peor rendimiento cuando la entrada es un gráfico completo.
millas
1

Java + Guava 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;}

Este algoritmo no es un gráfico, sino que genera todas las combinaciones de pares, de un tamaño específico. Alimento todas las combinaciones de pares en un conjunto múltiple y verifico que todas tengan el tamaño esperado (el número de entradas únicas: 1). Si lo hacen, encontré una camarilla y busco una más grande.

De la biblioteca de guayaba, uso el nuevo combinations método y el tipo de colección de herramientas Multiset.

Sin golf

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));
    }
  }
}
Olivier Grégoire
fuente
Me sorprendería mucho , ver Encontrar cliques máximos en gráficos arbitrarios , pero me llevará un tiempo analizar este código, no estoy muy familiarizado con Java :)
Felix Palmen
@FelixPalmen Me gustó este desafío, así que mi respuesta se mantendrá sin importar qué, pero estoy totalmente de acuerdo con eliminar el "-1" si no es una complejidad polinómica. Entonces probablemente debería revisar algunos libros: P
Olivier Grégoire
"La combinación de tamaño xes polinomial " <- ¿estás seguro? Supongo que ese es el método utilizado . El valor de retorno es AbstractSetcon un iterador, y el siguiente forciclo llamará a este iterador x!veces si no me equivoco ...
Felix Palmen
Corrección: siempre y cuando x < n(con nel tamaño completo del conjunto de entrada) n!/(x!(n-x)!), todavía no sea polinomial :)
Felix Palmen
@FelixPalmen Probablemente tengas razón. Además, ¿estás diciendo que si hago un combinationsmétodo que es X^n(que es completamente posible), puedo obtenerlo? Mientras tanto, elimino mi reclamo de "-1".
Olivier Grégoire
0

Código de máquina 6502 (C64), 774 703 bytes

(Acabo de tener que hacer esto, mi C64 puede hacer todo ... jeje)

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

Demostración en línea

Uso: Comience con sys49152, luego ingrese los pares uno por línea como p. Ej.

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

Backsapce no se maneja durante la entrada (pero si la usa vice, simplemente copie y pegue su entrada en el emulador). Ingrese una línea vacía para comenzar el cálculo.

Esto es demasiado grande para publicar una lista explicativa de desensamblaje aquí, pero puede explorar la fuente de ensamblaje de estilo ca65 . El algoritmo es muy ineficiente, genera todas las permutaciones posibles de los nodos y con cada uno de estos crea una camarilla con avidez al verificar todos los bordes. Esto permite una eficiencia de espacio de O (n) (algo importante en una máquina con esta pequeña RAM), pero tiene una eficiencia de tiempo de ejecución horrible (*) . Los límites teóricos son de hasta 256 nodos y hasta 8192 aristas.

  • -71 bytes: rutina optimizada para verificar los bordes y el uso de cero páginas

Hay una versión más grande ( 883 805 bytes) con mejores características:

  • retroalimentación visual durante el cálculo (cada permutación de los nodos cambia el color del borde)
  • utiliza el cambio de banco para almacenar los bordes en la RAM "ocultos" por las ROM para ahorrar espacio
  • genera el tamaño y los nodos de la camarilla máxima encontrada

Demostración en línea

Examinar fuente


(*) El último caso de prueba toma entre 12 y 20 horas (estaba durmiendo cuando finalmente terminó). Los otros casos de prueba terminan en el peor en unos minutos.

Captura de pantalla del último caso de prueba

Felix Palmen
fuente