データの重複を調べる
あーバグありそうだ。$all_1が全てのビットを立てる保証がないような気がしてきた。後でデバッグする。
ちょいと
http://q.hatena.ne.jp/1272372071
用に書いたスクリプトのメモ
まずはデーター定義部。やけくそに長い。このテストデータは自動生成している。
あまりに長いのでここだけはてなダイアリーにはperlではなく単なるテキストと指示している。
#script start
#data start=============================================
#[qw(dataname data1 data2 data3 ... lastdata)],
@data = (
[qw(001 B C E G L M O P R S W Y Z
d f h j k l n o p q t w )],
[qw(002 B F G I K N O R T U V W Y Z
c d h i k l m o p q t w )],
[qw(003 A B C D G H I K N O P T X Z
c h j l r v )],
[qw(004 A C D E H I J L M R T U W Z
a b f j l n p s v x )],
[qw(005 B D E H J M R S U W
c d e g j k o q v w )],
[qw(006 B D E F G J K M N R T X
c d e g h i k p r s u )],
[qw(007 A B D E F H I J K L M N O P Q R S T V W X Y Z
a b c g i k l n p t x )],
[qw(008 A B C D E H I J L M O P U V W X Y Z
a b d f g i k l m n q r s u )],
[qw(009 B C F G H I J K L M N O R S T U W X Z
a b c e g i j l m q t u v w )],
[qw(010 A B E G J K L M P Q S U V Y Z
f h i j o p q t w x )],
[qw(011 A B F I J K L M R S V W X Z
b c d e g h i j k l o p q s t v x )],
[qw(012 A B C D G J L M P R S U V X
a d e h i n o p s u v )],
[qw(013 D F G J K O P Q W X Y
a b d f g i j n o q s t v w x )],
[qw(014 B C D E F H I J K O P Q S U V Z
c d e h i j o p q r t u x )],
[qw(015 A E N O P U V X Y
c e f i l q r t x )],
[qw(016 B C F G H J K S T
b c e f i l o r s t v w x )],
[qw(017 C D F J L Q S T W X Z
b d g h m n o p q r t w x )],
[qw(018 B C G I J K M N P Q S T W Y Z
d e h i j n o s u v x )],
[qw(019 B F J K M N O P T X Y
a c d e f g j m q r u )],
[qw(020 F G I J K L M N P S V Z
a e f g i j m o t u w )],
[qw(021 C F G I K P Q R S T U W
a b d e f g h i j m n p q r u v )],
[qw(022 C D F G H I J L M O P T U Y Z
a b c d e h i m o q t v x )],
[qw(023 B C D E F G H J K N S U V W Y
b e f k l o w x )],
[qw(024 G J K L M T W X
c d e g i l m n p t u w x )],
[qw(025 A B C H I J L N O P Q S U W Y Z
a d e h k l m n o q r s t u v w x )],
[qw(026 A B C D E G J K L P R W X
b c d e f h i j k l m n o q r s u x )],
[qw(027 A B D E F G I K L N R T U W X Y
a d l r t u v x )],
[qw(028 F I K L M O Q T U V W X Y Z
c f h k o p q s t w )],
[qw(029 A C F H I L N O Q R S T U X Y Z
a b c e h i j k l m o p q r s v w x )],
[qw(030 A E G H J K P Q S T V W Y Z
a b c e f k l n o p s w )],
[qw(031 A C F G H L M N P Q R S V X Y
a c d e f g h i k m n s t u w x )],
[qw(032 B C E F I M N Q U X Z
c g h i j l m o q r u )],
[qw(033 A F H J K L O P R U X Z
c d f g h p q w )],
[qw(034 B C D E F G J K M P Q W X Y Z
a b c d e i j k m o q r s t )],
[qw(035 B F G H I J K M N O P Q R X Y
b e j k l m n p t u w )],
[qw(036 B E F I J M N O P Q R Y Z
c e f g h j u v )],
[qw(037 C F G I J M O R T V W Y Z
a f h i l p t u x )],
[qw(038 D E G J K N P W X Y Z
a b c d e f p s u w x )],
[qw(039 B C F G H J L N O P R V Y
b d f k m o q t u w )],
[qw(040 B K M O P Y
a d g i j k l n p q u v w )],
[qw(041 A B C D E G I M N O Q S U V X
a b d e h j k o p q r s t )],
[qw(042 C F G H I J K M Q R V X
g k m o p t u w x )],
[qw(043 A D E H M O P T V X Z
b d f g j m o p q t u w x )],
[qw(044 D E F I K L N O Q T U W X Y
a b e f k m n o p q s u v w )],
[qw(045 C D E G H J K L M N P T U V Y Z
a b e f j k l r s t w )],
[qw(046 C D I M O P T U Y
h i k q s u v )],
[qw(047 B E F G H L N P Q U V W X Y Z
b c d h i j l p r t v w x )],
[qw(048 A B D I J M N O S T W
h i j m n p q v )],
[qw(049 C F G J M N Q T U W Y
a b c h i j k l m p q r t u w x )],
[qw(050 A B D G H I L M P Q R T U V W X Y
a b d e g i k l m s t u w )],
[qw(051 B C E F G H I L P U V Y Z
a e f h i j p u v x )],
[qw(052 A B D E F G H I J K M N O S T X Z
a b c d g j k p q s t v w )],
[qw(053 C E F G J K L N O T V W Z
a b d f g k l m n p q r t u w )],
[qw(054 A B C D G J K N P S T U V
a e f h l r w x )],
[qw(055 A B D E G H J L M R T U V X Y
a b d g j k l m p q r t x )],
[qw(056 C D G H I K M S U V W Y Z
a b e f g h j n o p v x )],
[qw(057 C D E G H I K L N P R U V Y Z
b e h j k m q r u )],
[qw(058 A B C H J M N O P Q R S T V W X
d e h j l m o r v x )],
[qw(059 B C F H I J L S U V Y Z
b c d e f i j k m p r s t )],
[qw(060 B D E F G I N O P T U W
b d e f h n o r u v )],
[qw(061 B D E F G H I J L N P Q R T W X Z
a c d e f g h k p q r t v x )],
[qw(062 E G I L M N O R U V W X Y Z
a b c d i k o p q t u w x )],
[qw(063 G L M N R S V Z
a e f g h k m n p u w )],
[qw(064 A B E H I K L O V W
a e f g j k m n o q r t v w )],
[qw(065 A C E G K L R S T W X Y Z
b d e j k l n q t w )],
[qw(066 A C D F I J K L M O P Q S T V X Y
b c d g i l p q r u v )],
[qw(067 A C D E F H I J L N O P Q T U Z
b c g i k l u w x )],
[qw(068 C D F H I N R V W Y Z
a b d e h k l o p s t u v w x )],
[qw(069 E F H I J K M N O P Q R T U W Y Z
a e k m t u v w )],
[qw(070 B C G H I L N O P R U V W X Y
c d e h j k o p q t w )],
[qw(071 D E G H J M Q R X Y Z
a b c d e f g h i k p q r s t u v x )],
[qw(072 B D E I J L N O P Q R V W X
a c f h j n o r s u v )],
[qw(073 A B C D H I J K N Q R T U V W
a b c e f i j k l m q u v w x )],
[qw(074 A B E F H I O Q S X Y
a b e f g j k m n q s t u v )],
[qw(075 A D E G H K L N O S T W X
b c d e f g h i l r s u w )],
[qw(076 B C D E F G H J K M Q U X Z
b c e f g l m o q r t u w )],
[qw(077 C D E F H I K M N V W X Y Z
a c d g h j m n o s v )],
[qw(078 A B C G Q T U V Z
a c d f g o r t v w )],
[qw(079 B C E F G J L O P Q U V W
b c g h i k m n o q s v w x )],
[qw(080 B C D F H L M O S T U Y Z
b g j l n q s u x )],
[qw(081 A C D F H J O T U W X
a b c d e f h i j k m n p r s t )],
[qw(082 A C E F G H J K L M Q R X Z
b d h n p q t u v w )],
[qw(083 A C E F K M O P R U W Y
a b h i j l n o r u w x )],
[qw(084 A C E F G H I J K L O P S V W
b c d f i l m n r t w )],
[qw(085 C D E G M N Q R S T U V X Z
c f g h m n o p q u v w x )],
[qw(086 A C D E F L P Q S X Z
c e f g i j o r t u )],
[qw(087 B D G H J K O R U V Z
d e f h n q v )],
[qw(088 A B C D G H I J K L N O P Q S T V W
a b e f g h i j l n q s t v w )],
[qw(089 A E G H I N P Q S U V X Y Z
c d e f g h j l m q s u v x )],
[qw(090 A C D F G H I J K L M P T V W Z
b f j k m n s u v w x )],
[qw(091 B J N S V
b c i k n o p r v )],
[qw(092 B D F G H K M N O P U X Z
c e j l m n o t w )],
[qw(093 A B C D G H K L N R S U V Z
e f g n r s x )],
[qw(094 A C F G M O P Q R T Y Z
a c d g i j k l m n p q r u w x )],
[qw(095 A B C D F K L N P Q R T U W Y
a b c d e f g h j k l n q r t )],
[qw(096 B E F G H I J L M N O Q R S T U
a d f g h i j k r s w )],
[qw(097 C D E F G H I J L M P Q R S T U V Y Z
a b e f i j l p q s t u w x )],
[qw(098 A D E F G H I M O P Q T U W X Z
b c d e h j k o q s t u v )],
[qw(099 B C D E H L M N P R S V W Y
c d g j k l r s t v )],
[qw(100 E F G H I L M N Q R T
a b d f i j l m n o p r t x )],
[qw(101 B D F I J K L M Q T U V W Y
d f g l m q r t u )],
[qw(102 A D I J K L M N O P R S U V X Y
c d e g h i j k m n o q v )],
[qw(103 A C E F H I M S U V W
a c f g i p t u w )],
[qw(104 A B D J L M O R U W X
a d f h i k p q r s v )],
[qw(105 A D H L M O Q R S T X Y
c g l n o s )],
[qw(106 C D G H J K L M O Q R S T U V Y Z
a b g i l o p q r s t x )],
[qw(107 D E G L N O P R S T V W X
a b c d e g h i j k l o p q u w x )],
[qw(108 A C D E F H L O P S W X Z
a f j n o p q t w )],
[qw(109 A B C F H J K M O T V W Y Z
b d g h n p r t v x )],
[qw(110 A C E F H I J L O P T V W
e f j o p r s t v x )],
[qw(111 A F G K L N Q R S V X Z
b d i k o t u w )],
[qw(112 D E I J K M N O P R T X Y Z
a d e h j l m p r s u v w )],
[qw(113 B C F G I J L M O P U V W
c d h k l m n p q r t w x )],
[qw(114 B C E F G I J L M P T U
c d e g i j k n q r s u )],
[qw(115 A B C E I L N P R V Y Z
a b c e f g i k l n o p q u w )],
[qw(116 A B C D H J L N O R S T V X Z
b e f g i l m n p q r w )],
[qw(117 B C D I K N P Q S T U V Y Z
b d e f g h i m n r t u v w )],
[qw(118 A B D I K M N P T V X
a b d f g o p q r s w )],
[qw(119 B C D F G H J L N P R S U X Z
b c d e g h i j k q r t x )],
[qw(120 B C D F H I J K M N O P R U W Y Z
b d h j k l o q t u v x )],
[qw(121 A B D E F H I J L T V X Z
b c d e f g k l n q r s u w )],
[qw(122 C E F G I J K L N O P Q R S T U V W Y
c e g i k l n o p r t u v w x )],
[qw(123 B D E H J K L N O R S W Y Z
g h i k l o q s t u w x )],
[qw(124 B C D E I K L M P T W Y
d f g j l m q t )],
[qw(125 D F G H I J K O P R T V Y
b d f h i j m n o q s t u v w x )],
[qw(126 A B E K L M O P Q
b c d e g h j l m n o p r t x )],
[qw(127 C D E G H J K N P R T Y Z
b d e f h j n p q t )],
[qw(128 B D E I J M N O Q R S T U V W Z
a d e g h k n o t u x )],
[qw(129 A B C G H I J K P Q R S T U W Y Z
b e f i j k m p r w x )],
[qw(130 A E F G H J L M O Q R S T W X Y Z
a b d j l n o q r t x )],
[qw(131 C F H J P R T U X Y
a b d e g i l m n o p q r s t u v w )],
[qw(132 C E H I J M N P S T V X Y
a c d f j k l m n q r v w x )],
[qw(133 G H I J M P Q S U V W X Z
a b c d f h i q s t u v w )],
[qw(134 B C D E F I J L O P S T U W Y Z
b d e j k l n p t u )],
[qw(135 A B C D E G H I J K L P R T U W X Y
a e f g h j k n o r s u v x )],
[qw(136 C F G H I J K L M V Y Z
b g i j l n o r s t u v w )],
[qw(137 B C D E G I J M N Q R V X Y Z
b c d f h i l o p q r t u v w x )],
[qw(138 A D E G H I J L M Q V
a c d e g h k m n o r u w )],
[qw(139 A D E F G H J K L P R T U V W X Y
d e j l o p s u x )],
[qw(140 B C D F I J N Q S T U V W Y
a b d g h j k l q )],
[qw(141 A C E G H K N O P S T X Y
f h k o p q s u v w x )],
[qw(142 A C F G I J M N Q R S T V W Y
b c d h k o p r v x )],
[qw(143 A B E F H K L M N O S W Y Z
a c d f g h i l m o q r s t v w x )],
[qw(144 E G I J L M N O P Q R T W X
a c d i k n p r s v x )],
[qw(145 A H I L M N Q S U W X
a b c d g m n o p r w x )],
[qw(146 B D E F G H K M O P U V Y Z
a b c d f h m q r s v w )],
[qw(147 B D H K L M O S T U W X Y
b c f i j l n o p r t u v )],
[qw(148 A B E F G J K L N O P Q T V Y Z
a c g h i j k m n p q r s w x )],
[qw(149 D G I L M N O T W Z
c f g h i j k m o p u )],
[qw(150 B C E F H I J Q S W X Z
b c d e f g k m o p r s v )],
[qw(151 D E H I J K L O Q R W Y
a b c d g m p q t u v )],
[qw(152 A E H L R S U Z
a b d h i j l m n o p q r s t w x )],
[qw(153 A F G H I K M N P W X Y Z
a b d e f g i j l n o p r s t u w x )],
[qw(154 A B E H J K M N O P Q U W
a c f g h j l m n p r s w )],
[qw(155 B C G J K L M N R S W X Y
a c d f i l m o p q t u v x )],
[qw(156 A B G I J K L O R T V W Z
a b d e h m n p r t w )],
[qw(157 A C D E H I J K L N Q R U V W Y Z
a b f j m o p q v w x )],
[qw(158 A B F H I J M N O Q V Y Z
b c d e f g i j m n o s v w x )],
[qw(159 B C D F J K M O Q T U V Y
a c d e g h i k n p q r s )],
[qw(160 A C F G J K P S T U Y Z
a b c d g h i j n o r s t v w )],
[qw(161 D F H L M N Q T W X Y Z
b c d g l m n o t u w )],
[qw(162 B F G H L O T Y
c f h i j l m q s t v w x )],
[qw(163 A B E F G J K M N P Q U V X Y
a g i j k l m n o p r u x )],
[qw(164 A C D H I J L P R T U V W X Y
e g h i j k m n o p s x )],
[qw(165 A E J L M P R T X Y Z
b c d e h i l m n p q s u v w )],
[qw(166 A C D G I J M O P Q U V W
b c d e f h l n p q t w x )],
[qw(167 A C D H I K O R S U V Y Z
e g h j m n o p s t u v x )],
[qw(168 A C J L M P Q Y
b c f g j l m n p r t x )],
[qw(169 A D E I M P S T W
a j n p s u v x )],
[qw(170 A B E F G H J L N O P R V X Z
b d f h k l m n s t )],
[qw(171 B C D E G H K N P R T V W X
a b d e f h i m o q t u x )],
[qw(172 A F I J K M P R S T V W X Z
d e f g h i n r s t u v w x )],
[qw(173 A B C F I L M N O P W
a b f g h l n s u w x )],
[qw(174 A D F G K M N P S T V Z
a g h i k n r s u x )],
[qw(175 D H I L M N Q R S T U V W X
a e h l n q r s t v w )],
[qw(176 B C E M O P Q S T V W Y
a b c f g i o p r w )],
[qw(177 B E G H J K M P R T U W Y
a b c d f g j n p q r u v w x )],
[qw(178 A B C D E G I J K L N O R U X Y Z
c d f h j l m n p r t u )],
[qw(179 A B D E I J L N R S U W Y Z
a f g h i j l n o p r s )],
[qw(180 A B F G J L M N R T V W X Z
a f h i j l n r v w )],
[qw(181 A C D G I L N O P Q R T W X
a b c e g l n p q s t )],
[qw(182 B D G H I J Q R S T U V Y Z
g i k l n t )],
[qw(183 A I J K L N O S U V W Y
f i m n o p q r s v x )],
[qw(184 A C F G I J K L S T X Y
a b c e g i l m n p q r w x )],
[qw(185 B C E I K L M O Q S T U W X Y Z
a b g l n s t w x )],
[qw(186 C F G H I L M N O P R S T U V W Y
b c f g h i j k l m q r v )],
[qw(187 H I M R T V W Y
b e f h i j k o r t u x )],
[qw(188 A G H I L P S T U W
a g h i n p q r s t u x )],
[qw(189 A B D E F G H I J K L M N O P S T V X Y Z
e f g i k l n o p q s v )],
[qw(190 A B E F G H I K N O S U X Y Z
a b d e g h i j n o p r s t w x )],
[qw(191 A B D E G H I J K L N O P V W X Y
a f g i j k l m n p q t u w x )],
[qw(192 A D E G H N R V W X Y
f i k l m n o p q r s u w x )],
[qw(193 B D E F G H N T U Y
b d f i j m n p q r v )],
[qw(194 A D E G H K L M O P V W Z
d f h i j r u )],
[qw(195 B C D I K M N P Q R S V W X
b e f g h n o p q r s t )],
[qw(196 D E G H M N P T Y Z
c d e i j l m n o p q s u v )],
[qw(197 B C D E J L M N O P S T U W X
b c d e f j m n p r s t x )],
[qw(198 D F G M O Q U W X Y
b d f g o q r s t )],
[qw(199 D F G H K Q S W X Y
d h i j o q r s t u w x )],
[qw(200 A D G J L O P S T X Y Z
a e i j l n p r u )]
);
#data end=============================================メインルーチン。下準備してから心臓部に突っ込む。
あとで解説を書く。
our @names; our $bit_length; our %bit; { my %h; %h = &data_hush(@data); %bit = &hash_bit(%h); my @key = sort {$a cmp $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) < 3; 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); } }
下準備ルーチン。フラグのビット列を作る。
あとで解（ry
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; }
下準備ルーチン。生データからとりあえずハッシュを作る。
あとで解（ry
sub data_hush{ my (@arrays) = @_; my %hash; for$n(0..$#arrays){ push @names, shift @{$arrays[$n]}; for$value(@{$arrays[$n]}){ push @{$hash{$value}}, $n; } # last if 20 < $n; #えらい計算量になる } return %hash; } #script end
テスト用データを作ったワンライナー。
perl -e "for$y('001'..'200'){print join '', qq/[qw($y/, join ' ', ((map{1 < rand 2 ? $_ : ' '}(A..Z)), qq/\n/, (map{1 < rand 2 ? $_ : ' '}(a..x))), qq/)],\n/;}"
