Programmatically finding solutions to OEIS A001839

Question

Okay, so here is an integer sequence. Over at the math stackexchange, I learned what this sequence means. Basically:

• Given n item, a(n) is the number of groups of three you can create where no two groups have more than one item in common.

So if you have 7 items, represented by the letters a-g, you can make these seven groups:

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

'a' and 'b' only show up once together, same with 'a' and 'c', and every other pair.

I'm trying to write a little program that can give me these trios for any number. Right now it works with a string that is n characters long. Here's what I have. I think it explains itself pretty well.

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;
    }
}

You can see the functioning JSFiddle here.

It works for seven characters or less, giving the number of trios you'd expect from the sequence. But more than seven it breaks down.

The list of trios it outputs always fits the criteria, but it seems to be missing some and I have no idea where.

Answer 1

You are doing a greedy search, while finding the maximum might require some form of backtracking. An alternate way to think of it, you are looking for a maximal independent set in a graph where the trios are the vertices and two trios have an edge in common iff they share two letters. Not saying that this is a good way to model things, but you see how you'd find an independent set which cannot be extended, but which is still not globally maximal.

Answer 2

Here is a small python program I just wrote to give you the first 10,000 of these numbers in a few milliseconds:

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