通过编程找到OEIS A001839的解决方案

Question

好的，这是一个整数序列。在数学堆栈交换会上，我了解了这个序列的含义。基本上:

• 给定n个项目，a(n)是您可以创建的三个组的数量，其中两个组没有多于一个共同项目。

如果你有7个项目，用字母a-g表示，你可以把它们分成7组:

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。

它适用于7个或更少的字符，给出您期望从序列中得到的三重奏的数量。但超过7个就会分解。

它输出的三重奏列表总是符合标准，但它似乎缺少一些，我不知道在哪里。

Answer 1

您正在进行贪婪搜索，而找到最大值可能需要某种形式的回溯。另一种思考方式是，你在图中寻找一个最大的独立集其中三个顶点是顶点两个三个顶点有一条共同的边如果它们有两个字母。并不是说这是一个很好的建模方法，但你可以看到你如何找到一个独立的集合它不能被扩展，但它仍然不是全局最大的

Answer 2

下面是我刚刚编写的一个小python程序，它可以在几毫秒内给出这些数字中的前10,000个:

    from math import floor
    for n in xrange(1,10000):
        print int(floor((n/3)*floor((n-1)/2))+(n%3)*floor(n/6)),