与えた条件を満たす候補 in Perl DouKaku?

与えた条件を満たす候補

['and', 'or', 'not', 'and']
のような入力が与えられた場合に、
式 x1 and x2 or not x3 and x4 の値が
Trueとなるような、x1～x4の組み合わせを全て
出力するプログラムを作成してください。
x1～x4には真と偽の2通りの値だけが入るものとします。

Pythonであれば上の入力に対し、
(True, True, True, True)
(True, True, False, True)
(True, False, False, True)
(False, True, False, True)
(False, False, False, True)
と出力します。

andとorの優先順位は同じで左結合性、
つまりa and b or c and dは
(((a and b) or c) and d)
という順番で評価されるものとします。

参考：
d.y.d.

キミならどう書く2.0の小町算問題と似てますが。

このお題はmorchinさんの投稿をもとに作成しました。ご投稿ありがとうございました。
元ネタの充足可能性問題 - Wikipedia は、同じリテラル(x1とかnot x2とか)が複数回出てくることを想定しているので、今回の問題のようにそれぞれ別の変数でだと乗法標準形 - Wikipediaにした場合に、答えが…と色々悩みどころでした。

post comment

Posted feedbacks - Perl

右から値を決めていき、orで分岐して解を構成します。
計算量は、
O(MAX(変数の数, 2^(最右のorの位置)))
になります。(orがなければ変数の数に対して線形時間になります)

sub output_inner{
  my ($n, $r, @l) = @_;
  if($n){
    output_inner(--$n,$r,0,@l);
    output_inner($n,$r,1,@l);
  } else {
    print "(" . join(", ", (map {$_?"True":"False"} @l), $r);
  }
}

sub output{
  my $n = shift @_;
  my $r = join(", ", map {$_?"True":"False"} @_) . ")\n";
  output_inner ($n, $r, ());
}

sub f{
  my $n = 0;
  do { ++ $n if $_ ne 'not' } for @_;
  my $t = 1;
  my @r = ();
  while(scalar @_){
    my $p = pop @_;
    if($p eq 'not'){
      $t = !$t;
      next;
    }
    if($p eq 'and'){
      unshift @r, $t;
    }elsif($p eq 'or'){
      output($n,$t,@r);
      unshift @r, !$t;
    }else{
      die("Unknown operator $p");
    }
    $t = 1;
    -- $n;
  }
  output(0,$t,@r);
}

#f(qw|and or not and|);

DouKaku?

与えた条件を満たす候補

Posted feedbacks - Perl

Index

Feed

Other

Link

Pathtraq