Hintergrund

Zum Zeitpunkt des Schreibens dieses Dokuments ist das P vs NP-Problem noch ungelöst, aber Sie haben vielleicht von Norbert Blums neuem Aufsatz gehört , der den Beweis erbringt, dass P! = NP ist, was bereits als fehlerhaft vermutet wird (aber wir werden sehen).

Das in diesem Artikel diskutierte Problem ist das Cliquenproblem . Zumindest habe ich das in einem Zeitungsartikel gelesen, also korrigieren Sie mich, wenn ich falsch liege, aber auf jeden Fall möchten Sie, dass Sie ein Programm schreiben, das die folgende Variante löst:

Die Aufgabe

Angenommen, wir haben eine große Schule mit vielen Schülern. Jeder dieser Schüler hat einige Freunde an dieser Schule. Eine Clique von Studenten ist eine Gruppe , die nur aus Studenten besteht , die Freunde mit sind jedes andere Mitglied .

Ihr Programm erhält befreundete Schülerpaare als Input. Aus diesen Informationen muss das Programm die Größe der größten Clique ermitteln . Die Schüler werden durch ganzzahlige IDs identifiziert .

Wenn Sie mathematische Begriffe bevorzugen, bedeutet dies, dass Sie die Kanten eines ungerichteten Graphen erhalten, der durch jeweils zwei Knoten gekennzeichnet ist.

Eingang

Ihre Eingabe ist eine nicht leere Liste positiver ganzzahliger Paare, z [[1,2],[2,5],[1,5]]. Sie können diese Eingabe in jeder sinnvollen Form vornehmen, z. B. als Array von Arrays, als Textzeilen mit jeweils zwei Zahlen usw.

Ausgabe

Die erwartete Ausgabe ist eine einzelne Zahl n >= 2: die Größe der größten Clique. Mit dem Beispiel Eingang oben, wäre das Ergebnis 3, da alle Schüler ( 1, 2und 5) miteinander befreundet sind.

Testfälle

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

Sie können diese (blöde) Referenzimplementierung verwenden (zusätzliche Ausgabe mit -dFlag ausgeben ), um die Ergebnisse anderer Testfälle zu überprüfen.

Die Regeln

1. Ihr Programm benötigt kein definiertes Ergebnis bei ungültiger Eingabe. Sie können also davon ausgehen, dass:
   • Sie erhalten immer mindestens ein Paar IDs
   • Jedes Paar besteht aus zwei verschiedenen IDs
   • kein Paar erscheint zweimal (das Vertauschen der Stellen der IDs wäre immer noch dasselbe Paar)
2. Ihr Algorithmus darf keine Obergrenze für die Eingabegröße festlegen. Rein technische Einschränkungen und Einschränkungen, die durch Ihre Sprache / Umgebung (wie Stapelgröße, Rechenzeit usw.) festgelegt werden, sind natürlich unvermeidlich.
3. Standardlücken sind verboten.
4. Das ist Code-Golf , also gewinnt der kürzeste Code, gemessen in Bytes.
5. Wenn Ihr Algorithmus eine polynomielle Zeitkomplexität aufweist, erzielen Sie -1unabhängig von Ihrer Codegröße sofort eine Punktzahl. In diesem Fall möchten Sie Ihre Lösung möglicherweise an einer anderen Stelle einreichen. ;)

Jelly ,  15 18  16 Bytes

+3 Bytes, um Fehler in meiner Methode zu beheben.
-2 Bytes dank Meilen ( n × (n-1) ÷ 2 = nC2 )

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

Ein monadischer Link, der die Liste der Freundschaften (Kanten) aufnimmt und eine Ganzzahl zurückgibt.

Probieren Sie es online!bildet die Potenz der Kanten im Speicher und ist daher sowohl räumlich als auch zeitlich ineffizient (yep, das sind O (2 ⁿ ) Leute)!

Wie?

Ẏ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&@@@#]]&  

Grundsätzlich erledigt FindClique die Aufgabe und "findet eine größte Clique in der Grafik g."
Alles andere wandelt die Eingabeliste in eine Grafik um

Eingang

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

Ausgabe

4

Eingang

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

Ausgabe

6

Danke @Kelly Lowder für -10 Bytes

Gelee , 20 Bytes

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

Probieren Sie es online!

Das verdient natürlich nicht die Million: p

Dies hätte Pyth geschlagen, wenn nicht µ(...)µund 2-Byte Ðf.

J , 36 Bytes

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

Probieren Sie es online!

Läuft in Zeit O (2 ⁿ ), wobei n die Anzahl der Paare ist.

Eine schnellere Lösung für 65 Bytes ist

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

Probieren Sie es online!

Erläuterung

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

Pyth, 19 Bytes

l{ef.AqLtl{T/LTTsMy

Probieren Sie es hier aus.

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

Probieren Sie es online!

-2 dank shooqie .
-1 Danke an Herrn Xcoder .
-3 dank rekursiv .

Pyth, 28 Bytes

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

Probieren Sie es online aus

Erläuterung

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)

Probieren Sie es online!

Die Funktion c nimmt Eckpunkte in Form einer Menge sortierter Tupel ({(x, y), ...}, wobei x kleiner als y ist). Eine Funktion mit dem Namen "entry" befindet sich im TIO-Header, um Daten im Format "Liste unsortierter Listen" zu testen . Wenn clique, wird length zurückgegeben. Wenn nicht clique, wird die maximale Cliquegröße der Scheitelpunkte abzüglich eines Scheitelpunkts für jeden Scheitelpunkt in den Scheitelpunkten zurückgegeben. Zeitüberschreitung beim letzten Testfall in TIO

Update: "oder (z, y) in x" Teil hinzugefügt, um die Abhängigkeit von der Sortierbarkeit zu beseitigen "f = lambda x: {i für s in x für i in s}" anstelle von itertools.chain in set.

-Minus 3 Bytes dank @ Jonathan Allen

05AB1E , 19 Bytes

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

Probieren Sie es online!

Gelee , 28 Bytes

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

Probieren Sie es online!

Schnellere Lösung, mit der der letzte Testfall in Sekundenschnelle mit TIO gelöst werden kann.

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;}

Dieser Algorithmus zeichnet nicht grafisch, sondern generiert alle Kombinationen von Paaren einer bestimmten Größe. Ich füttere alle Paarkombinationen zu einem Multiset und überprüfe, ob sie alle die erwartete Größe haben (die Anzahl der eindeutigen Einträge - 1). Wenn ja, habe ich eine Clique gefunden und suche eine größere.

Aus der Guava-Bibliothek verwende ich die neue combinationsMethode und den Tool-Collection-TypMultiset .

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

Probieren Sie es online!

6502 Maschinencode (C64), 774 703 Bytes

(Ich gerade hatte , dies zu tun, mein C64 kann alles ... 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

Online-Demo

Verwendung: Beginnen Sie mit sys49152, und geben Sie dann die Paare einzeln pro Zeile ein, wie z

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

Backsapce ist nicht bei der Eingabe behandelt (aber wenn Sie verwendenvice , kopieren einfach Ihre Eingabe in den Emulator). Geben Sie eine leere Zeile ein, um die Berechnung zu starten.

Dies ist zu groß, um hier eine erklärende Auflistung der Demontage zu veröffentlichen, Sie können jedoch die Assembly-Quelle im Stil von ca65 durchsuchen . Der Algorithmus ist sehr ineffizient, er generiert jede mögliche Permutation der Knoten und bildet mit jedem von diesen gierig eine Clique, indem er alle Kanten überprüft. Dies ermöglicht einen Raumwirkungsgrad von O (n) (wichtig auf einer Maschine mit diesem kleinen RAM), hat aber eine schreckliche Laufzeiteffizienz (*) . Die theoretischen Grenzen liegen bei bis zu 256 Knoten und bis zu 8192 Kanten.

• -71 Bytes: Optimierte Routine zum Überprüfen von Kanten und der Verwendung von Nullen

Es gibt eine größere Version ( 883 805 Byte) mit besseren Funktionen:

• visuelles Feedback während der Berechnung (jede Permutation der Knoten ändert die Rahmenfarbe)
• Verwendet Bank Switching, um die Ränder im RAM zu speichern, der von den ROMs "verborgen" ist, um Platz zu sparen
• gibt die Größe und die Knoten der maximal gefundenen Clique aus

Online-Demo

Quelle durchsuchen

(*) Der letzte Testfall dauert zwischen 12 und 20 Stunden (ich habe geschlafen, als er endlich fertig war). Die anderen Testfälle enden schlimmstenfalls innerhalb weniger Minuten.