Задний план

На момент написания этой статьи проблема P против NP все еще не решена, но вы, возможно, слышали о новой статье Норберта Блюма, в которой утверждается, что P! = NP, что уже считается ошибочным (но мы увидим).

Проблема, обсуждаемая в этой статье, является проблемой клики . По крайней мере, это то, что я прочитал в газетной статье, так что поправьте меня, если я ошибаюсь, но в любом случае я бы хотел, чтобы вы написали программу, которая решает следующий вариант:

Задание

Предположим, у нас большая школа с большим количеством учеников. У каждого из этих учеников есть друзья в этой школе. Клика студентов представляет собой группа , состоящая только из студентов , которые являются друзьями с каждым другим членом .

Ваша программа будет получать пары студентов, которые являются друзьями в качестве входных данных. Исходя из этой информации, программа должна найти размер самой большой клики . Студенты идентифицируются целочисленными идентификаторами .

Если вы предпочитаете математические термины, это означает, что вы задаете ребра неориентированного графа, каждый из которых идентифицируется двумя узлами.

вход

Ваш вход будет непустым списком положительных целых пар, например [[1,2],[2,5],[1,5]]. Вы можете использовать этот ввод в любой разумной форме, например, как массив массивов, как строки текста, содержащие по два числа в каждой и т. Д.

Выход

Ожидаемый результат - одно число n >= 2: размер самой большой клики. С приведенным выше примером ввода, результат будет 3, как и все студенты ( 1,2 и 5) являются друзьями друг с другом.

Контрольные примеры

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

Вы можете использовать эту (глупую) ссылочную реализацию (печатает дополнительный вывод с -dфлагом) для проверки результатов других тестовых случаев.

Правила

1. Ваша программа не требует определенного результата при неверном вводе. Таким образом, вы можете предположить, что:
   • вы всегда получите хотя бы одну пару идентификаторов
   • каждая пара состоит из двух разных идентификаторов
   • пара не появляется дважды (поменять местами идентификаторы все равно будет та же пара)
2. Вашему алгоритму не разрешено устанавливать верхнюю границу размера ввода. Чисто технические ограничения и ограничения, установленные вашим языком / средой (например, размер стека, время вычислений и т. Д.), Конечно, неизбежны.
3. Стандартные лазейки запрещены.
4. Это код-гольф , поэтому выигрывает самый короткий код в байтах.
5. Если ваш алгоритм имеет сложность за полиномиальное время, вы -1сразу получаете оценку независимо от размера вашего кода, но в этом случае вы можете отправить свое решение куда-нибудь еще. ;)

Желе ,  15 18  16 байт

+3 байта, чтобы исправить ошибки в моем методе.
-2 байта благодаря милям (учитывая, что n × (n-1) ÷ 2 = nC2 )

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

Монадическая ссылка, берущая список дружеских связей (ребер) и возвращающая целое число.

Попробуйте онлайн! формирует набор мощностей ребер в памяти, поэтому неэффективен как в пространстве, так и во времени (да, это O (2 ⁿ ) человек )!

Как?

Ẏ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 байта

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

В основном FindClique выполняет свою работу и «находит самую большую клику в графе g».
Все остальное - преобразование входного списка в граф

вход

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

Выход

4

вход

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

спасибо @Kelly Lowder за -10 байтов

Желе , 20 байт

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

Попробуйте онлайн!

Конечно, это не заслуживает миллиона: p

Это бы победило Pyth, если бы не µ(...)µ2-байтовый Ðf.

J , 36 байт

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

Попробуйте онлайн!

Работает за время O (2 ⁿ ), где n - количество пар.

Более быстрое решение для 65 байтов

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

Попробуйте онлайн!

объяснение

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

l{ef.AqLtl{T/LTTsMy

Попробуй это здесь.

Python 2 , 180 байт

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

Попробуйте онлайн!

-2 благодаря shooqie .
-1 спасибо мистеру Xcoder .
-3 благодаря рекурсивному .

Pyth, 28 байт

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

Попробуйте онлайн

объяснение

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 байт

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)

Попробуйте онлайн!

Функция c принимает вершины в виде набора отсортированных кортежей ({(x, y), ...}, где x меньше y). Функция под названием «запись» находится в заголовке TIO для проверки данных в формате списка несортированных списков . Если клик, возвращает длину. Если не клика, возвращает максимальный размер клики вершин, минус вершина для каждой вершины в вершинах. Превышает время последнего теста в TIO

Обновление: добавлена ​​часть "или (z, y) в x" для удаления зависимости от сортировки "f = lambda x: {i для s в x для i в s}" вместо itertools.chain, обернутого в набор.

минус 3 байта благодаря @ Джонатану Аллену

05AB1E , 19 байтов

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

Попробуйте онлайн!

Желе , 28 байт

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

Попробуйте онлайн!

Более быстрое решение, способное решить последний контрольный пример за секунду на TIO.

Java + Гуава 23,0, 35 + 294 = 329 байт

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

Этот алгоритм не строит графики, а генерирует все комбинации пар определенного размера. Я передаю все парные комбинации в мультимножество и проверяю, все ли они имеют ожидаемый размер (количество уникальных записей - 1). Если они это сделают, я нашел клику и пойду искать большую.

Из библиотеки Guava я использую новый combinationsметод и тип набора инструментов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 байта

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

Попробуйте онлайн!

6502 машинный код (C64), 774 703 байта

(Я только что был сделать это, мой C64 может сделать все ... хе-хе)

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

Онлайн демо

Использование: Начните с sys49152, затем введите пары по одной в строке, например, например

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

Backsapce не обрабатывается во время ввода (но если вы используетеvice , просто скопируйте и вставьте свой ввод в эмулятор). Введите пустую строку, чтобы начать расчет.

Это слишком велико, чтобы опубликовать пояснительный лист разборки здесь, но вы можете просмотреть исходный код сборки в стиле ca65 . Алгоритм очень неэффективен, он генерирует каждую возможную перестановку узлов и с каждым из них жадно строит клику, проверяя все ребра. Это позволяет пространство эффективности из O (N) (рода важно на машине с этой небольшой ОЗУ), но имеет попали эффективность выполнения (*) . Теоретические пределы - до 256 узлов и до 8192 ребер.

• -71 байт: оптимизированная процедура проверки ребер и использования нулевой страницы

Там больше ( 883 805 байт) версия с улучшенными функциями:

• визуальная обратная связь при расчете (каждая перестановка узлов меняет цвет границы)
• использует переключение банков для хранения ребер в оперативной памяти, «скрытой» ПЗУ для экономии места
• выводит размер и узлы максимальной найденной клики

Онлайн демо

Просмотр источника

(*) Последний тест занимает от 12 до 20 часов (я спал, когда он наконец закончился). Другие тестовые случаи заканчиваются в худшем случае в течение нескольких минут.