请问一个算法"如何实现一组数组是另一组数组的真子集"

Vic_Yu

原帖由 Lonki 于 2007-10-26 15:25 发表
#1. 你要求"连续", 而集合是无序的, 所以现成的Set相关module只能作为你的部分检测.
#2. 按纯算法来做, 就失去了Perl的优势. 写了一个检测, 应该可以..

my @set1 = qw/1 2/;
my @set2 = qw/1 2 3/;
my @s ...

这个是输出的结果，
。。。。。。
<1><2> <1><1><2><2>
No
。。。。。。
这个是有问题的，前一个应该是后一个的子集。

Lonki

原帖由 Vic_Yu 于 2007-10-26 17:15 发表


这个是输出的结果，
。。。。。。

No
。。。。。。
这个是有问题的，前一个应该是后一个的子集。

(1, 2)当然不是 (1, 1, 2, 2)的真子集.
(1, 1, 2, 2)不包含(1, 2)以外的元素.

我前面还向你确认过, 忘了?

如果对此你的需求是"是真子集", 那么应该称之为"子串",  代码就很简单了.

[ 本帖最后由 Lonki 于 2007-10-26 17:22 编辑 ]

Vic_Yu

原帖由 Lonki 于 2007-10-26 17:19 发表




(1, 2)当然不是 (1, 1, 2, 2)的真子集.
(1, 1, 2, 2)不包含(1, 2)以外的元素.

我前面还向你确认过, 忘了?

OK，那我们现在讨论子集。（1，1，2，2）也应该包括（1，2）对吧。
其实这个东西是一个抽象，高层次的，我主要是想看对于用HASH分析的2个BMP位图。是用C#做起来快些，还是用perl做一起来快些。两个位图的二进制代码存贮到两个数组里面，然后比较两个数组。用来判断，其中一个图，是不是另外一个图的一部分。如果结合这个考虑，那么（1，1，2，2）应该是包含（1，2）的。

放驴娃

这是“真子集”嘛。
不会用名词就别乱用，
真子集，还甄子丹呢。

Lonki

原帖由 放驴娃 于 2007-10-26 17:30 发表
这是“真子集”嘛。
不会用名词就别乱用，
真子集，还甄子丹呢。

:>

这个头像是哪个片里面的啊? 悄悄告诉我

Lonki

原帖由 Vic_Yu 于 2007-10-26 17:27 发表


OK，那我们现在讨论子集。（1，1，2，2）也应该包括（1，2）对吧。
其实这个东西是一个抽象，高层次的，我主要是想看对于用HASH分析的2个BMP位图。是用C#做起来快些，还是用perl做一起来快些。两个位图的二 ...

速度真难说..

用C++吧 ^_^

Vic_Yu

原帖由 放驴娃 于 2007-10-26 17:30 发表
这是“真子集”嘛。
不会用名词就别乱用，
真子集，还甄子丹呢。

第一，（１，１，２，２）这个并不是一个集合，集合是不允许有重复的．
第二，概念：

子集就是一个集合中的元素全部都是另一个集合中的元素，有可能与另一个集合相等

真子集就是一个集合中的元素全部是另一个集合中的元素，但不存在相等

我分析不是有人不懂．如果有人不懂，我感觉可以是＂你＂啦

放驴娃

你自己都知道集合是不能重复的，那还扯什么真子集啊。

smonkey0

use strict;
my @aa = (1,2,3,4);
my @bb = (1,2,1,2,3,4,5,6,7,8  ) ;
my %aa_hash=();
my %bb_hash=();

for(@aa){
    $aa_hash{$_}=' ';
}
for(@bb){
    $bb_hash{$_}=' ';
}
foreach(keys %bb_hash ) {
    if(exists $aa_hash{$_}){
        delete $aa_hash{$_};
        delete $bb_hash{$_};
    }
}

if((scalar keys %aa_hash) ==0 and (scalar keys %bb_hash)>0 ){
    print '@aa is @bb\'s child',"\n";
}

[ 本帖最后由 smonkey0 于 2007-10-26 19:21 编辑 ]

smonkey0

靠，搞半天原来是在比图。这种相似性问题，建议参考生物学的blast的算法比较好~