Последовательность магия представляет собой последовательность неотрицательных целых чисел , x[0..n-1]таких , что существует ровно x[i]экземплярыi

Например, 6,2,1,0,0,0,1,0,0,0 - это магическая последовательность, поскольку есть 6 0, 2 1 и т. Д.

Напишите функцию, которая при задании n выводит все магические последовательности длины n

Программа, которая может произвести правильный вывод для наибольшего значения n в течение 10 секунд, побеждает. (Все программы приветствуются)

Например, программа Алисы может обрабатывать до n = 15 в течение 10 секунд, в то время как Боб может обрабатывать до n = 20 в течение того же времени. Боб выигрывает.

Платформа: Linux 2,7 ГГц @ 4 процессора

Python, n≈10 ⁸

def magic_sequences(n):
    if n==4:
        return (1, 2, 1, 0),(2, 0, 2, 0) 
    elif n==5:
        return (2, 1, 2, 0, 0),
    elif n>=7:
        return (n-4,2,1)+(0,)*(n-7)+(1,0,0,0),
    else:
        return ()

Это использует тот факт, который я докажу, что единственные магические последовательности длины n:

• [1, 2, 1, 0]и [2, 0, 2, 0]дляn=4
• [2, 1, 2, 0, 0] за n=5
• [n-4, 2, 1, 0, 0, ..., 0, 0, 1, 0, 0, 0] за n>=7

Так что, n>=7нужно только вернуть огромный кортеж. Я могу сделать это примерно n=10^8на моем ноутбуке, который, вероятно, ограничен памятью; больше и он замерзает. (Спасибо trichoplax за идею использования кортежей, а не списков.) Или, если вместо этого можно напечатать словарь ненулевых записей, {0:n-4, 1:2, 2:1, (n-4):1}можно сделать это для большого количества n.

Я доказываю уникальность для n>=7; другие могут быть проверены грубой силой или делом.

Сумма записей l- это общее количество всех номеров списка, которое является его длиной n. В списке есть l[0]нули и, следовательно, n-l[0]ненулевые записи. Но по определению l[0]должно быть ненулевым, иначе мы получим противоречие, и каждая из других ненулевых записей равна по крайней мере 1. Это уже составляет сумму l[0] + (n-l[0]-1)*1 = n-1из общей суммы n. Таким образом, не считая l[0], может быть не более одного 2 и нет записи больше 2.

Но это означает, что единственными ненулевыми записями являются l[0], l[1], l[2], and l[l[0]]значения, значения которых не больше, l[0]и перестановка 1,1,2, что дает максимальную сумму l[0]+4. Поскольку эта сумма есть n, а это как минимум 7, у нас есть l[0]>=3и так l[l[0]]=1. Так вот, есть по крайней мере одно 1, что означает l[1]>=1, но если l[1]==1это другое 1, значит l[1]>=2, l[1]это одиночество 2. Это дает l[2]=1, и все остальные записи 0, так что l[0]=n-4, что завершает решение.

Python 3, n≈40

def plausible_suffix(l,N):
    if sum(l)>N:
        return False

    pairs = [(N-1-i,l[i]) for i in range(len(l))]

    if sum(i*x for i,x in pairs)>N:
        return False

    num_remaining = N - len(l)

    for index, desired_count in pairs:
        count = l.count(index)
        more_needed = desired_count - count
        if more_needed<0: 
            return False
        num_remaining -= more_needed
        if num_remaining<0:
            return False
    return True

plausible_func = plausible_suffix

def generate_magic(N):
    l=[0]
    while l:
        extend = False
        if plausible_func(l,N):
            if len(l)==N:
                yield l[::-1]
            else:
                extend = True
        if extend:
            l.append(0)
        else:
            while l[-1]>=N-2:
                l.pop(-1)
                if not l:raise StopIteration
            l[-1]+=1

n=40 #test parameter

if n>0:
    for x in generate_magic(n):
        print(n,x)

Выполняет поиск возможных списков в ширину, заполняя записи справа налево, останавливая поиск с суффиксом, если это невозможно, что может произойти, если:

• Сумма записей в суффиксе превышает n(сумма для всего списка должна быть n)
• Взвешенная сумма i*l[i]в суффиксе превышает n(сумма для всего списка должна быть n)
• Любое число появляется в суффиксе больше раз, чем суффикс говорит, что это должно
• Количество оставшихся незаполненных мест слишком мало, чтобы учесть все числа, которые должны появляться больше раз.

У меня были оригинальные проверенные префиксы слева направо, но это происходило медленнее.

Выходы до n=30:

4 [1, 2, 1, 0]
4 [2, 0, 2, 0]
5 [2, 1, 2, 0, 0]
7 [3, 2, 1, 1, 0, 0, 0]
8 [4, 2, 1, 0, 1, 0, 0, 0]
9 [5, 2, 1, 0, 0, 1, 0, 0, 0]
10 [6, 2, 1, 0, 0, 0, 1, 0, 0, 0]
11 [7, 2, 1, 0, 0, 0, 0, 1, 0, 0, 0]
12 [8, 2, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0]
13 [9, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
14 [10, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
15 [11, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
16 [12, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
17 [13, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
18 [14, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
19 [15, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
20 [16, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
21 [17, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
22 [18, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
23 [19, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
24 [20, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
25 [21, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
26 [22, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
27 [23, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
28 [24, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
29 [25, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
30 [26, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]

За исключением первых трех списков [1, 2, 1, 0], [2, 0, 2, 0], [2, 1, 2, 0, 0], существует ровно один список каждой длины n>6, и он имеет форму [n-4, 2, 1, ..., 0, 0, 1, 0, 0, 0]. Эта модель сохраняется по крайней мере до n=50. Я подозреваю, что это действует вечно, и в этом случае тривиально вывести огромное количество из них. Даже если нет, математическое понимание возможных решений значительно ускорит поиск.

Pyth - 15 байт

Использует грубую силу всеми возможными последовательностями len nи затем фильтрует.

f.A.eq/TkYT^UQQ

Полное объяснение скоро.

Попробуйте здесь онлайн .

К, 26 байт

{f@&{x~(+/x=)'!#x}'f:!x#x}

Как подход Малтисена, грубая сила. Сердцем программы является предикат, который проверяет, является ли данный вектор «магическим»:

{x~(+/x=)'!#x}

Постройте йота-вектор до входного вектора ( !#x), посчитайте вхождения каждой цифры ( (+/x=)') и сравните результат с входным вектором ( x~). Если есть совпадение, у вас есть волшебная последовательность.

К сожалению, этот первый удар кажется довольно медленным. Тестирование с использованием Kona на моем ноутбуке занимает около 12 секунд для обработки n = 7. Мне нужно больше об этом подумать.