tło

W chwili pisania tego, P vs problemu NP jest nadal nierozwiązane, ale może słyszeliście o nowej papieru Norberta Bluma dowód twierdząc, że P! = NP, która jest już podejrzewa się błędne (ale zobaczymy).

Problemem omawianym w tym artykule jest problem kliki . Przynajmniej tak czytam w artykule w gazecie, więc popraw mnie, jeśli się mylę, ale w każdym razie chciałbym, abyś napisał program, który rozwiązuje następujący wariant:

Zadanie

Załóżmy, że mamy dużą szkołę z dużą liczbą uczniów. Każdy z tych uczniów ma w tej szkole przyjaciół. Klika studentów to grupa składająca się wyłącznie ze studentów, którzy są przyjaciółmi z każdego innego członka .

Twój program otrzyma pary studentów, którzy są przyjaciółmi jako wkład. Na podstawie tych informacji program musi znaleźć rozmiar największej kliki . Studenci są identyfikowani za pomocą liczb całkowitych .

Jeśli wolisz terminy matematyczne, oznacza to, że zasilasz krawędzie niekierowanego wykresu, identyfikowanego przez dwa węzły każdy.

Wkład

Twoje dane wejściowe będą niepustą listą dodatnich par liczb całkowitych, np [[1,2],[2,5],[1,5]]. Możesz wprowadzić te dane w dowolnej rozsądnej formie, np. Jako tablicę tablic, jako wiersze tekstu zawierające dwie liczby, itd.

Wydajność

Oczekiwany wynik to jedna liczba n >= 2: wielkość największej kliki. Z powyższego przykładu wejścia, wynik będzie 3, jak wszyscy uczniowie ( 1, 2i 5) są przyjaciółmi z siebie.

Przypadki testowe

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

Możesz użyć tej (głupiej) implementacji referencyjnej (drukuje dodatkowe wyjście z -dflagą) do weryfikacji wyników innych przypadków testowych.

Zasady

1. Twój program nie potrzebuje określonego wyniku przy nieprawidłowym wprowadzaniu danych. Możesz więc założyć, że:
   • zawsze otrzymasz przynajmniej jedną parę identyfikatorów
   • każda para składa się z dwóch różnych identyfikatorów
   • żadna para nie pojawia się dwa razy (zamiana miejsc identyfikatorów nadal byłaby tą samą parą)
2. Twój algorytm nie może ustawić górnej granicy rozmiaru wejściowego. Ograniczenia czysto techniczne i ograniczenia określone przez Twój język / środowisko (takie jak rozmiar stosu, czas obliczeń itp.) Są oczywiście nieuniknione.
3. Standardowe luki są zabronione.
4. To jest golf golfowy , więc wygrywa najkrótszy kod, mierzony w bajtach.
5. Jeśli algorytm ma złożoność czasową wielomianową, wynik jest -1natychmiastowy niezależnie od rozmiaru kodu, ale w takim przypadku możesz przesłać swoje rozwiązanie gdzie indziej. ;)

Galaretka ,  15 18  16 bajtów

+3 bajty, aby naprawić błędy w mojej metodzie.
-2 bajty dzięki milom (zauważając, że n × (n-1) ÷ 2 = nC2 )

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

Monadyczny link pobierający listę przyjaźni (krawędzie) i zwracający liczbę całkowitą.

Wypróbuj online! tworzy zestaw mocy krawędzi w pamięci, więc jest nieefektywny zarówno w przestrzeni, jak i czasie (tak, to O (2 ⁿ ) ludzie)!

W jaki sposób?

Ẏ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 bajty

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

Zasadniczo FindClique wykonuje zadanie i „znajduje największą klikę na wykresie g”.
Wszystkie pozostałe rzeczy konwertują listę wejść na wykres

Wkład

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

Wydajność

4

Wkład

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

Wydajność

6

thanx @ Kelly Lowder dla -10 bajtów

Galaretka , 20 bajtów

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

Wypróbuj online!

Oczywiście nie zasługuje to na milion: str

To by pokonało Pytha, gdyby nie µ(...)µ2-bajtowe Ðf.

J , 36 bajtów

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

Wypróbuj online!

Działa w czasie O (2 ⁿ ), gdzie n jest liczbą par.

Szybszym rozwiązaniem dla 65 bajtów jest

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

Wypróbuj online!

Wyjaśnienie

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

l{ef.AqLtl{T/LTTsMy

Wypróbuj tutaj.

Python 2 , 180 bajtów

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

Wypróbuj online!

-2 dzięki shooqie .
-1 dzięki Mr. Xcoder .
-3 dzięki rekursywnemu .

Pyth, 28 bajtów

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

Wypróbuj online

Wyjaśnienie

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 bajtów

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)

Wypróbuj online!

Funkcja c przyjmuje wierzchołki w postaci zestawu posortowanych krotek ({(x, y), ...}, gdzie x jest mniejsze niż y). Funkcja o nazwie „pozycja” znajduje się w nagłówku TIO, aby przetestować dane w formacie listy nieposortowanych list . Jeśli klika, zwraca długość. Jeśli nie jest klika, zwraca maksymalny rozmiar kliki wierzchołków, minus jeden wierzchołek dla każdego wierzchołka w wierzchołkach. Przekracza czas w ostatnim przypadku testowym w TIO

Aktualizacja: dodano porcję „lub (z, y) w x”, aby usunąć zależność od sortowania „f = lambda x: {i dla s w x dla i w s}” zamiast itertools.chain opakowane w zestawie.

-minus 3 bajty dzięki @Jonathan Allen

05AB1E , 19 bajtów

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

Wypróbuj online!

Galaretka , 28 bajtów

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

Wypróbuj online!

Szybsze rozwiązanie, które jest w stanie rozwiązać ostatni przypadek testowy w ciągu sekundy w TIO.

Java + Guava 23,0, 35 + 294 = 329 bajtów

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

Algorytm ten nie grafuje, ale generuje wszystkie kombinacje par o określonym rozmiarze. Podaję wszystkie kombinacje par do multiset i sprawdzam, czy wszystkie mają oczekiwany rozmiar (liczba unikalnych wpisów - 1). Jeśli tak, to znalazłem klikę i szukam większej.

Z biblioteki Guava korzystam z nowej combinationsmetody i typu zbioru narzędziMultiset .

Nie golfił

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 bajty

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

Wypróbuj online!

Kod maszynowy 6502 (C64), 774 703 bajty

(Po prostu musiałem to zrobić, mój C64 może zrobić wszystko ... hehe)

zrzut heksowy:

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

Demo online

Sposób użycia: Zacznij od sys49152, a następnie wprowadź pary po jednym w wierszu, np

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

Backsapce nie jest obsługiwane podczas wprowadzania (ale jeśli używasz vice, po prostu skopiuj i wklej dane wejściowe do emulatora). Wpisz pusty wiersz, aby rozpocząć obliczenia.

Jest on zbyt duży, aby opublikować tutaj objaśniającą listę deasemblacji, ale można przeglądać źródło zestawu w stylu ca65 . Algorytm jest bardzo nieefektywny, generuje każdą możliwą permutację węzłów i przy każdym z nich zachłannie buduje klikę, sprawdzając wszystkie krawędzie. Pozwala to na wykorzystanie przestrzeni w O (N) (rodzaj ważne w przypadku maszyny z tą małą RAM), ale ma straszną wydajności wykonania (*) . Teoretyczne ograniczenia wynoszą do 256 węzłów i do 8192 krawędzi.

• -71 bajtów: zoptymalizowana procedura sprawdzania zużycia krawędzi i zerowania strony

Istnieje większa ( 883 805 bajtów) wersja z lepszymi funkcjami:

• wizualna informacja zwrotna podczas obliczeń (każda permutacja węzłów zmienia kolor obramowania)
• używa przełączania banków do przechowywania krawędzi w pamięci RAM „ukrytej” przez ROM w celu zaoszczędzenia miejsca
• wyświetla rozmiar i węzły maksymalnej znalezionej kliki

Demo online

Przeglądaj źródło

(*) Ostatni przypadek testowy zajmuje od 12 do 20 godzin (spałem, kiedy w końcu się skończył). Pozostałe przypadki testowe kończą się najgorzej w ciągu kilku minut.