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

Vic_Yu

现在有两个数组，如何能够确定，小的数组是大数组的真子集，举个例子：

a[4] = {1,2,3,4}

b[10] = {1,2,1,2,3,4,5,6,7,8}

像这样的，a就是b的真子集，a必须在b里面，且在b中是连续的。
请问这个算法如何的写呢，请指教

Lonki

"真子集"的话, B必须包含不在A中的元素咯?

Vic_Yu

原帖由 Lonki 于 2007-10-26 11:29 发表
"真子集"的话, B必须包含不在A中的元素咯?

真子集不是你说的这个含义啦。b若是a的真子集，那么b必须包括a中的元素，且与a不相同，而且不能包括a以外的元素。

Lonki

那就是我说的这个意思咯, 如果B>A

你说的是A>B吧

Vic_Yu

原帖由 Lonki 于 2007-10-26 12:20 发表
那就是我说的这个意思咯, 如果B>A

你说的是A>B吧

HOHO，一个意思一个意思 ，用BM算法倒是能做，可惜是C的，不是perl的，perl又没有现成的库文件可以使用呢

royalzhang

如果是两个集合就好办，楼主还要考虑顺序，麻烦些。

Lonki

#1. 你要求"连续", 而集合是无序的, 所以现成的Set相关module只能作为你的部分检测.
#2. 按纯算法来做, 就失去了Perl的优势. 写了一个检测, 应该可以..

my @set1 = qw/1 2/; my @set2 = qw/1 2 3/; my @set3 = qw/1 1 2 2/; my @set4 = qw/1 3/; print isYourSubset(\@set1, \@set1), "\n"; print isYourSubset(\@set1, \@set2), "\n"; print isYourSubset(\@set1, \@set3), "\n"; print isYourSubset(\@set1, \@set4), "\n"; sub isYourSubset { &nbsp;&nbsp;&nbsp;&nbsp;my ($a_ref, $b_ref) = ($_[0], $_[1]); &nbsp;&nbsp;&nbsp;&nbsp;my ($a_str, $b_str) = ('', ''); &nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;map { $a_str .= "<$_>" } @$a_ref; &nbsp;&nbsp;&nbsp;&nbsp;map { $b_str .= "<$_>" } @$b_ref; &nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;print "$a_str $b_str\n"; &nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;return 'No' if (index($b_str, $a_str) < 0); &nbsp;&nbsp;&nbsp;&nbsp;map { return 'Yes' if (index($a_str, "<$_>") < 0)} @$b_ref; &nbsp;&nbsp;&nbsp;&nbsp;return 'No'; }

另外, 如果LZ的数组仅包含整数, 那么有不同的办法.

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

vincentn

这样?
my @a=(1,2,3,4);
my @b=(1,2,1,2,3,4,5,6,7,;
print "true\n"  if(join("",@b)=~join("",@a) and $#a!=$#b);

Lonki

原帖由 vincentn 于 2007-10-26 16:36 发表
这样?
my @a=(1,2,3,4);
my @b=(1,2,1,2,3,4,5,6,7,;
print "true\n"  if(join("",@b)=~join("",@a) and $#a!=$#b);

1. 用""来join的话, 2位数就混淆了.
2. 没有判断"真子集".

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

vincentn

且在b中是连续的
my @a=(12,34,45,29);      #join后是12344529
my @b=(77,54,12,34,45,29,34,89);      #join后是7754123445293489