以编程方式查找OEIS的解决方案A001839

好的，所以here is an integer sequence。在数学堆栈交换中，我学习了这个序列的含义。基本上：以编程方式查找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; 
    } 
}

You can see the functioning JSFiddle here。

它适用于7个或更少的字符，给出您希望从序列中选择的三重奏的数量。但超过七分之一。

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

来源

2014-05-05 fnsjdnfksjdb

您正在做greedy search，而找到最大值可能需要某种形式的回溯。换一种方式来思考它，你正在寻找一个maximal independent set在一个图中，其中trios是顶点，两个trios有一个共同的边，如果它们共享两个字母。并不是说这是模拟事物的好方法，但是你会发现你会找到一个独立的集合，它不能被扩展，但它仍然不是全局最大的。

来源

2014-05-05 06:58:14 MvG

谢谢！我想我现在明白我的剧本可能缺少一些答案。你能指点我一些能帮助我想出更好的搜索算法吗？ – fnsjdnfksjdb

@fnsjdnfksjdb：我建议您尝试阅读并理解OEIS提及的参考文献。如果他们有一个确切的公式，他们也有可能有一个枚举算法。尽管如此，还没有发现它们。如果这没有帮助，请查找独立设置的启发式。 – MvG

这里是一个小的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)),

来源

2014-08-03 21:04:47

以编程方式查找OEIS的解决方案A001839

回答

相关问题