0

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

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

所以如果你有 7 个项目，用字母 ag 表示，你可以组成这七个组：

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

'a'并且'b'只一起出现一次，与'a'and'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。

它适用于七个或更少的字符，给出您期望从序列中获得的三重奏数量。但是超过七个它就坏了。

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

4

2 回答 2

0

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

于 2014-05-05T06:58:14.370 回答
0

这是我刚刚编写的一个 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)),
于 2014-08-03T21:04:47.980 回答