人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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さん
-------------------

●質問者: love2u2
●カテゴリ:コンピュータ ウェブ制作
✍キーワード:Perl PHP 数字 配列
○ 状態 :終了
└ 回答数 : 4/4件

▽最新の回答へ

1 ● t-wata
●30ポイント

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

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

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

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

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

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

◎質問者からの返答

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

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

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

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


2 ● kurehajime
●20ポイント

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


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

配列「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演算すると良いかもしれません。


3 ● imo758
●20ポイント
#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


4 ● villain
●20ポイント

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

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

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

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;
}

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

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ