Программный поиск решений для OEIS A001839

Итак, вот целочисленная последовательность. В математическом стеке я узнал, что означает эта последовательность. В принципе:

  • Для данного n элемента a(n) - это количество групп из трех, которые вы можете создать, если ни у одной из двух групп нет более одного общего элемента.

Итак, если у вас есть 7 предметов, представленных буквами ag, вы можете сделать эти семь групп:

1. abc
2. ade
3. afg
4. bdf
5. beg
6. cdg
7. cef

'a' а также 'b' показывать только один раз вместе, то же самое с 'a' а также 'c'и любая другая пара.

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

var str = 'abcdefg';
var userPairs = [];
var found = 0
var x;
var y;
var z;

$('.bundles').append(str.length+'<br>');

for (x = 0; x < str.length; x += 1) {
    for (y = 0; y < str.length; y += 1) {
        for (z = 0; z < str.length; z += 1) {
            var possible = str[x]+str[y]+str[z];
            if (!tooSimilar(possible)) {
                found += 1;
                $('.bundles').append(found + ') ');
                $('.bundles').append(possible+'<br>');
                userPairs.push(str[x]+str[y]);
                userPairs.push(str[y]+str[z]);
                userPairs.push(str[x]+str[z]);
            }
        }
    }
}

function tooSimilar(possible) {
    if (possible[0] === possible[1] ||
        possible[1] === possible[2] ||
        possible[2] === possible[0]) {
        console.log('repeated char');
        return true;
    } else if (userPairs.indexOf(possible[0]+possible[1]) !== -1 ||
              userPairs.indexOf(possible[1]+possible[0]) !== -1 ||
              userPairs.indexOf(possible[1]+possible[2]) !== -1 ||
               userPairs.indexOf(possible[2]+possible[1]) !== -1 ||
               userPairs.indexOf(possible[0]+possible[2]) !== -1 ||
               userPairs.indexOf(possible[2]+possible[0]) !== -1){
        console.log('repeated pair');
        return true;          
    } else {
        console.log('FOUND ONE');
        return false;
    }
}

Вы можете увидеть функционирование JSFiddle здесь.

Это работает для семи символов или меньше, давая количество трио, которое вы ожидаете от последовательности. Но больше семи он ломается.

Список трио, которые он выводит, всегда соответствует критериям, но он, кажется, пропускает некоторые, и я понятия не имею, где.

Источник

2 ответа

Решение

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

Источник

Вот небольшая программа на Python, которую я только что написал, чтобы дать вам первые 10000 из этих чисел за несколько миллисекунд:

    from math import floor
    for n in xrange(1,10000):
        print int(floor((n/3)*floor((n-1)/2))+(n%3)*floor(n/6)),
Источник
Другие вопросы по тегам