Как построить последовательность натуральных чисел с уникальной суммой любых смежных чисел? - PullRequest
Новая
       47

Как построить последовательность натуральных чисел с уникальной суммой любых смежных чисел?

4 голосов
/ 04 августа 2011

Например: 1,2,4,5 имеет следующую сумму:

1,2,4,5

3,6,9

7,11

12

и каждая сумма уникальна.

Теперь 1,2,3 имеет следующую сумму:

1,2,3

3,5

6

и, очевидно, не каждая сумма уникальна.

Существует ли эффективный способ генерирования последовательности, аналогичной первому примеру сцель выбрать каждое число как можно меньше (не просто 1,2,4,8,16 ...)?Я понимаю, что мог бы написать программу, возможно, для того, чтобы это исправить, но мне просто любопытно, можно ли это сделать лучше.

Ответы [ 2 ]

8 голосов
/ 04 августа 2011

Я думаю, что вы ищете здесь Golomb Ruler .Если вы берете числа, которые вы описываете выше, как расстояние между знаками, вы описали линейку Голомба.Когда набор меток на линейке не имеет дубликатов, как вы уже описали, это делает его линейкой Голомба.

По-видимому, стандартный способ описания линейки Голомба - это представление местоположения каждой метки, а не расстояния между ними.Следовательно, ваш 1,2,4,5 будет описан как линейка Голомба 0-1-3-7-12.

Цитирование Википедии:

В настоящее время сложностьНахождение OGR произвольного порядка n (где n задано в унарном порядке) неизвестно.В прошлом были некоторые предположения, что это NP-сложная проблема.Доказано, что проблемы, связанные со строительством Правителей Голомба, являются NP-трудными, при этом также отмечается, что ни одна из известных NP-полных проблем не имеет такого же вкуса, как поиск Правителей Голомба.

1 голос
/ 04 августа 2011 
Seen <- emtpy set  # Sums seen so far
Open <- empty set  # Sums ending at the last element
for x from 1 to Limit do
    if x in Seen then
        # quick fail
        continue with next x
    end
    # Build new set
    Pending <- empty set
    add x to Pending
    for each s in Open do
        add (s+x) to Pending
    end
    # Check if these numbers are all unique
    if (Pending intersection Seen) is empty then
        # If so, we have a new result
        yield x
        Open <- Pending
        Seen <- Seen union Pending
    end
end

Он просматривает все суммы, которые были видны до сих пор, и суммы, заканчивающиеся на последнем элементе. Нет необходимости отслеживать начальные и конечные позиции.

Если n является значением Limit, этот алгоритм будет принимать O (n 2 log n) , предполагая, что проверка набора элементов и вставка O (log n) , и пересечение / объединение не медленнее, чем O (n log n) .

(хотя я могу ошибаться в последнем предположении)

Первые несколько значений будут: 

1, 2, 4, 5, 8
...