perlかPHPで解決したいです。


複数(最大200程度)の配列があり、
それぞれ有している数字(それぞれ最大50程度)のうち、
二つ以上の値が同じ配列名を抜き出す。

という事をしたいです。
どのように表せば良いでしょうか。


例は以下の通りです。
3配列、有している値も最大5つと少ないですが、実際はもっと多いです。

-------------------
例:

配列「Aさん」=1,2,3,4,5
配列「Bさん」=1,2,3,4
配列「Cさん」=1,2,4,100

の場合の結果は以下の通り

1,2
Aさん・Bさん・Cさん

1,3
Aさん・Bさん

1,4
Aさん・Bさん・Cさん

2,3
Aさん・Bさん

2,4
Aさん・Bさん・Cさん

3,4
Aさん・Bさん

1,2,3
Aさん・Bさん

1,2,4
Aさん・Bさん・Cさん

1,3,4
Aさん・Bさん

1,2,3,4
Aさん・Bさん
-------------------

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2010/04/26 19:30:31
  • 終了:2010/05/03 19:35:08

回答(4件)

id:t-wata No.1

t-wata回答回数82ベストアンサー獲得回数132010/04/27 00:44:14

ポイント30pt

たとえば、ある配列の1つが50個の数値を持っていたとして、50個の数値から10個の数値を選ぶときの組み合わせって何通りあると思いますか?

答えは約 12,723,000,000 通り。50個の数字から25個の数値を選ぶ場合の組み合わせは 100兆を超えます。

たとえば2つの配列がそれぞれまったく同じ50個の数値を持っていた場合(それ以外に配列が無かったとしても)、

> 二つ以上の値が同じ配列名を抜き出す。

というのは、2つ以上の数値の組み合わせが全部でΣnCr (n=50, 2=< r =<50)通りで、全通り列挙するプログラムを組むと、1つの組み合わせを列挙するのに1msだとしても、処理が終わるまでに軽く100万日以上かかります。

本来の目的に合わせて手段を再考してください。

id:love2u2

なるほど、ありがとうございます!

ちょっと嫌な予感はしていました…。

明確なご指摘、ありがとうございます。

検討し直し、また質問しなおしてみます。その際はよろしくお願いします。

2010/04/27 21:17:32
id:gabill No.2

kurehajime回答回数4ベストアンサー獲得回数02010/04/28 01:19:39

ポイント20pt

"二つ以上の値が同じ配列名"を単純に抜き出すだけなら、こういうやり方はどうでしょうか。


例題だとちょっと長くなるので、少し変えます。

配列「Aさん」=1,2,3,5

配列「Bさん」=2,3,4

配列「Cさん」=1,2,6

配列「Cさん」=1,2,3


という配列が与えられていたとする。


①まずこれをbit列になおす。2進数表現ではなく、各桁に数字を割り当てる。

A:0000010111

B:0000001110

C:0000100011

D:0000000111


②それぞれで論理積(AND)を計算する。

AB:0000000110

AC:0000000011

AD:0000000111

BC:0000000010

BD:0000000110

CD:0000000011


③1のbitの数を数え、閾値(2)以上の組み合わせだけ抜き出す。

AB:0000000110→2

AC:0000000011→2

AD:0000000111→3

BC:0000000010→1

BD:0000000110→2

CD:0000000011→2


もし配列が200個あったとすれば、単純に比較すれば200*200=4万回、

その比較の中から自分自身との比較を引いて39800、

さらに重複した比較を省けば半分の19900回のAND演算ですみます。

ただし比較対象の数字が大きい数字の場合はAND演算する際の桁数も膨れあがるので、

登場した数字に連番を振って、その連番でAND演算すると良いかもしれません。

id:imo758 No.3

imo758回答回数121ベストアンサー獲得回数192010/04/29 20:52:47

ポイント20pt
#perl script start
#data start=============================================
#[qw(dataname data1 data2 data3 ... lastdata)],

@data = (
[qw(a 1 2 3   5 6)],
[qw(b 1 2 3   5)],
[qw(c 1   3   5     10 text)],
[qw(d   2     5   7 10)],
[qw(e 1   3 4 5     10 text)]
);

#data end=============================================
our @names;
our $bit_length;
our %bit;
{
	my %h;
	%h = &data_hush(@data);
	%bit = &hash_bit(%h);
	my @key = sort {$a <=> $b} keys %bit;
	my $all_1 = $bit{$key[0]} | ~$bit{$key[0]};
	$bit_length = 8 * length $all_1;
	&recursive_exist($all_1, [], \@key);
}

sub recursive_exist{
	my ($flag, $selected, $key) = @_;
	my (@new_keys);
	for$k(@{$key}){
		my $f = $flag & $bit{$k};
		next if (unpack "%".$bit_length."b*", $f) < 2;
		push @new_keys, $k;
	}
	while(@new_keys){
		$k = shift @new_keys;
		my $f = $flag & $bit{$k};
		if(@{$selected}){
			print join ',', (@{$selected}, $k);
			print "\n  ";
			print join ',', (grep{$_}map{vec($f,$_,1) ? $names[$_] : ''}(0..$#names));
			print "\n";
		}
		&recursive_exist($f, [@{$selected}, $k], \@new_keys);
	}
}

sub hash_bit{
	my (%in, %out) = @_;
	foreach$key(keys %in){
		if($#{$in{$key}} < 1){
		}else{
			$flag = '';
			for$x(0..$#{$in{$key}}){
				vec ($flag, $in{$key}->[$x], 1) = 1;
			}
			$out{$key} = $flag;
		}
	}
	return %out;
}

sub data_hush{
	my (@arrays) = @_;
	my %hash;
	for$n(0..$#arrays){
		push @names, shift @{$arrays[$n]};
		for$value(@{$arrays[$n]}){
			push @{$hash{$value}}, $n;
		}
	}
	return %hash;
}
#script end
__END__
さてこれではたしていいのやら…バグがあったらすいません
あと効率悪いかもしれないので、いきなり巨大なデーターを突っ込むと
どのくらい計算時間がかかるのかわかりません。
小規模のテストデーターでどのくらいの計算時間がかかるかお見積りください。
#プログラムの行儀とか最悪だろうなあ…

出力例

text,1
  c,e
text,1,3
  c,e
text,1,3,5
  c,e
text,1,3,5,10
  c,e
text,1,3,10
  c,e
text,1,5
  c,e
text,1,5,10
  c,e
text,1,10
  c,e
text,3
  c,e
text,3,5
  c,e
text,3,5,10
  c,e
text,3,10
  c,e
text,5
  c,e
text,5,10
  c,e
text,10
  c,e
1,2
  a,b
1,2,3
  a,b
1,2,3,5
  a,b
1,2,5
  a,b
1,3
  a,b,c,e
1,3,5
  a,b,c,e
1,3,5,10
  c,e
1,3,10
  c,e
1,5
  a,b,c,e
1,5,10
  c,e
1,10
  c,e
2,3
  a,b
2,3,5
  a,b
2,5
  a,b,d
3,5
  a,b,c,e
3,5,10
  c,e
3,10
  c,e
5,10
  c,d,e

id:villain No.4

villain回答回数174ベストアンサー獲得回数122010/05/02 00:45:18

ポイント20pt

バグなどがある可能性もあるし数が多くなると処理にどれだけかかるか分からないけど

こんな方法はどうでしょうか。

(そもそもから解釈を間違ってるかもしれないですが)

use Data::Dumper;
my @a = (
	1,
	2,
	3,
	4,
	5
);
my @b = (
	1,
	2,
	3,
	4
);
my @c = (
	1,
	2,
	4,
	100
);

my $d = [\@a, \@b, \@c];

print "'1, 2'\n";
print Dumper(&extract($d, 1, 2));
print "'1, 3'\n";
print Dumper(&extract($d, [1, 3]));
print "'1, 4'\n";
print Dumper(&extract($d, [1, 4]));
print "'2, 3'\n";
print Dumper(&extract($d, [2, 3]));
print "'2, 4'\n";
print Dumper(&extract($d, [2, 4]));
print "'3, 4'\n";
print Dumper(&extract($d, [3, 4]));
print "'1, 2, 3'\n";
print Dumper(&extract($d, [1, 2, 3]));
print "'1, 2, 4'\n";
print Dumper(&extract($d, [1, 2, 4]));
print "'1, 3, 4'\n";
print Dumper(&extract($d, [1, 3, 4]));
print "'1, 2, 3, 4'\n";
print Dumper(&extract($d, [1, 2, 3, 4]));

sub extract {
	my $data = shift;
	my $val  = shift;
	my @array = ();
	foreach my $list (@$d) {
		my @tmp = &extract2($list, $val);
		push(@array, $list) if($#tmp == $#$val);
	}
	return @array;
}

sub extract2 {
	my $data = shift;
	my $val  = shift;
	my @lists = ();
	for my $i (@$val) {
		my @tmp = grep { $_ == $i } @$data;
		push(@lists, @tmp) if($#tmp >= 0);
	}
	return @lists;
}

この方法では、同じ配列内に重複した値が含まれていると上手く動きません。

  • id:imo758
    ひとつバグが見つかりました。
    誤:
    my $all_1 = $bit{$key[0]} | ~$bit{$key[0]};

    正:
    my $all_1 = pack "b". @data, ("1" x @data);
    に差し替えてください。

この質問への反応(ブックマークコメント)

トラックバック

  • perl - 配列の∪と∩ 404 Blog Not Found 2010-05-01 13:28:18
    これを解くためには、配列の∩(交わり、intersection)がわかればいいのですが… Perl Cookbook (English) Christiansen / Torkington [邦訳: Perlクックブック] perlかPHPで解決したいです。 複数(最
  • 積集合の抽出に挑む 1 まずは用語と共に、何をしようとしているのかを述べる。 集合とはモノの集まりとする。例えば集合A={1,2,3},集合B={2,3,5}など。 次に積集合とは、対象となるどの集合
「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません