Wataru

Формула включения-исключения. Берете все графы, где хотя бы одна вершина соединена со всеми (их n*2^(n-2)*(n-1)), вычитаете все графы, где хотя бы две вершины соеденины со всеми (2 раза, ведь они 2 раза подсчитались), прибавляете графы, где хотя бы 3 вершины соеденины со всеми (3 раза)... И т.д.

Графов, где хотя бы k вершин имеют степень n-1 - C(n, k)*2^{(n-k-1)(n-k)/2}: тут можно выбрать k вершин и для каждого ребра из оставшихся n-k вершин есть 2 варианта - оно или есть, или нет.

Это будет за O(n log n) решение, если пердподсчитать все факториалы и обратные к им по модулю в задаче. Ну, или O(n^2), если считать сочетания через треугольник паскаля.

Ражеванное объяснение:

Сложно подсчитать количество графов где ровно 1 вершина такая полная. Но легко подсчитать те, где k или более таких. Мы их такие зафиксируем и нарисуем от них все ребра. А все оставшиеся ребра в графе могут быть любыми. Во-первых, можно выбрать эти k вершин - поэтому у нас есть множитель C[n,k]. Оставшиеся, незафиксированные ребра идут между любыми двумя оставшимся n-k вершин. Их (n-k)(n-k-1)/2. И каждое может быть или проведено или нет.

Поэтому всего таких графов, с не менее k вершин: F(k)=C[n,k]*2^{(n-k)(n-k-1)/2}.

Теперь, как подсчитать графы ровно с 1 вершиной? Можно взять F(1). Но мы насчитали много лишнего, Графы с 2мя такими вершинами мы в F(1) подсчитали 2 раза. Поэтому вычтем 2F(2). Теперь графы ровно с 3 вершинами мы подсчитали 3 раза в F(1) и 3 раза в каждом F(2). Поэтому пока мы их насчитали 3-2*3 = -3 раза. Поэтому прибавим 3F(3). И далее, получится, что графы ровно с 4-мя вершинами мы подсчитали 4 раза (4-2*6+3*4). И т.д.

Посмотрите на ограничения в задаче. Введите вашей программе максимальный тест: 15 монеток и сумму примерно в 1000000000. Ваша программа попробует съесть дюжину гигабайт памяти и упадет.

У вас решениe за O(n^3), ибо у вас там 2 вложенных цикла до n, а внутри еще и постоянно вызываются min/max, которые проходятся по всему массиву.

Ограничения же в задаче n<10^5. С такими ограничениями максимум O(n log n) решение уложится в 3 секунды.

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

Что можно сделать с входным массивом, чтобы можно было получать несколько самых маленьких элементов быстро? Помните, что вам надо уложиться в O(n log n).

У вас все равно полный перебор, можно через itertools.combinations перебирать сочетания из заданного количества имеющихся чисел, считать их сумму и, если совпало, выводить. Там всего один цикл, буквально 4 строчки будет решение.

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

Более хитрые и быстрые варианты: динамическое программирование типа задачи о рюкзаке, где вы считаете количество способов набрать такую-то сумму стольки-то слагаемыми из стольки-то первых чисел. А потом используя это в рекурсивном переборе можно отрубать его тупиковые ветви: если ДП говорит, что там 0 наборов, то можно туда не идти в рекурсии. Или, если вам не сами наборы, а из количество нужно, то даже рекурсивного перебора не надо. Но это работает, только если target не очень большое.

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

Например, вот так:

def GenerateAll(source, rep):
  for comb in itertools.combinations(range(len(source)), len(source)-len(rep)):
    s = list()
    prev = 0
    for (i, j) in enumerate(comb):
      s.append(source[j]);
    yield "".join(s)

Обратите внимание, перебираем не сочетания из удаляемых позиций, а из 22 оставляемых (кстати, у вас числа не бьются, 48+22 = 60 != 64). Тут порядок в ответе будет обратный (первая строка будет "xxxxxx...xxxx12..." а не "12..xxx..xx". Если нужен тот же порядок, то будет чуть сложнее:

def GenerateAll(source, rep):
  for comb in itertools.combinations(range(len(source)), len(rep)):
    s = list()
    prev = 0
    last = 0
    for (i, j) in enumerate(comb):
      while (last < j):
          s.append(source[last]);
          last += 1
      last += 1
    while (last < len(source)):
          s.append(source[last]);
          last += 1
    yield "".join(s)

Это не самое питонистое решение, возможно в какой-то библиотеке уже есть готовая функция, которая вырезает из строки символы по индексам.

Надо, чтобы "четность" перестановки совпадала с четностью финального поля (1).
Занумеруйте все 16 позиций слева направо сверху вниз.
чтобы подсчитать четность, рассматривайте каждую пару заполненных позиций (15\*14/2=105 пар) - если числа идут не в том порядке (большее число на позиции с меньшим номером) - то прибавьте 1 к ответу. В конце возьмите ответ по модулю 2. Это и будет четность перестановки.

Чтобы получить поле, которое можно собрать, сгенерируйте любую перестановку (случайно перемешайте 15 чисел), а потом посчитайте ee четность. Если четность плохая, то поменйте местами любые 2 соседних элемента (выберите случайно, или меняйте первые 2 всегда - на вероятности всех возможных полей это не влияет).

Edit: Но вы это почти все итак знатете, ибо функция is_solvable в вашем коде как раз инверсии уже считает.
Значит, Но вы знаете, что плохое поле от хорошего отличается лишь четностью, значит, если поле плохое - меняйте местами 2 соседних по порядку элемента. Например верхний левый со вторым в верхней строке.

Это все ссылки. Вершина хранит ссылки на ребра, ребра хранят ссылки на вершины. Поэтому эта вложенность не страшна. Она - головная боль сборщика мусора (так называется часть менеджера памяти, которая освобождает ненужную больше память).

Я бы действительно не вводил сущность ребро. И просто в вершинах хранил список соседних вершин (оно еще называется список смежности). Так экономнее, быстрее и проще.

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

В питоне большие целые числа встроенные. Но только целые.
Если вы хотите соранить всю точность, то вам нельзя использовать числа с плавающей точкой. В вашем коде у вас деление на 100, которое и приводит к преобразованию в float и потерю точности. Замените деление на целочисленное и ответ будет точным.

i - i * p // 100 посчитает точно, но там окргуление при делении будет вниз. Чтобы округлить вверх, можно воспользоваться хитростью - прибавть в числитель знаменатель -1: (i * p + 99) // 100 округлит вверх.

В коментариях указали, что списки можно переставлять.

Это известная, очень сложная (NP-сложная) задача об упаковке.

Для сотен тысяч входных списков вы оптимальное по количеству кусков в ответе решение не найдете за все время до тепловой смерти вселенной. Всякие аппроксимации, вроде вашего жадного алгоритма, могут найти лишь какое-то хорошее, но не лучшее разбиение. В частности, у вас используется Next-Fit аппроксимация - вы в итоге можете выдать в 2 раза больше кусков в ответе, чем можно было бы. Есть более сложные алгоритмы, которые, например, гарантируют ухудшение максимум в 1.7 раза.

Соглашусь с Dr. Bacon, через yield код вашего решения может быть чуть красивее, но я не совсем понимаю, что в вашей реализации вам так "не красиво". Хотя я не питонист.

Далее, вы упоминули, что ключи во входных данных - это номера домов, а числа в списках - номера квартир. Вы как-то объединяете дома с ограничением на количество квартир. Не знаю, что у вас за задача на самом деле, но мне кажется логичным, что вам надо бы объединять дома только рядом. С одной улицы, или вообще идущие подряд. Ведь если в одной группе идут квартиры из домов в разных концах города, то какая вообще разница, что квартиры из одного дома могут быть в разных группах? Если такое ограничение ввести, то задача упрощается и ваше решение будет оптимальным.