Perl による next_permutation の実装と AGC022 A

はじめに

AtCoderは、オンラインで参加できるプログラミングコンテスト(競技プログラミング)のサイトです。リアルタイムのコンテストで競い合ったり、約3000問のコンテストの過去問にいつでも挑戦することが出来ます。 では、時々、順列生成が必要な問題が出題されます。
Perl には標準モジュールとして、next_permutation が準備されていないので、自作により対応します。

Perl による実装

num.pl

my $next_perm = sub {
  my $t = shift;
  my $f = -1;
  for my $i (0..length($t)-1) {
    if (ord(substr($t, length($t)-1-$i, 1)) > ord(substr($t, length($t)-2-$i, 1))) {
      $f = length($t) - 2 - $i;
      last;
    }
  }
  return -1 if $f == -1;
  my @w = split '', substr($t, $f+1);
  my @x = sort {$a cmp $b} grep {ord($_) > ord(substr($t, $f, 1))} @w;
  my $r = shift @x;
  push @w, substr($t, $f, 1);
  @w = sort {$a cmp $b} grep {ord($_) != ord($r)} @w;
  return substr($t, 0, $f).$r.join('', @w);
};

ord 関数を使用することにより、数字・文字の両方に対応しています。

sample1.pl

print $next_perm->(13542);  # => 14235
print $next_perm->('CAEDB'); # => CBADE

while ループで -1 が返るまで回すこともできます。

while.pl

my $ans = 1234;
while ($ans != -1) {
  print $ans, "\n";
  $ans = $next_prem->($ans);
}
 # => 1234
 .
 .
 # => 4321

A - Diverse Word

AGC 022 A - Diverse Word

perl.pl

use v5.18; # strict say state
use warnings;
use List::Util qw(reduce first max min sum0);

chomp (my $s = <STDIN>);
my $next_perm = sub {
  my $t = shift;
  my $f = -1;
  for my $i (0..length($t)-1) {
    if (ord(substr($t, length($t)-1-$i, 1)) > ord(substr($t, length($t)-2-$i, 1))) {
      $f = length($t) - 2 - $i;
      last;
    }
  }
  return -1 if $f == -1;
  my @w = split '', substr($t, $f+1);
  my @x = sort {$a cmp $b} grep {ord($_) > ord(substr($t, $f, 1))} @w;
  my $r = shift @x;
  push @w, substr($t, $f, 1);
  @w = sort {$a cmp $b} grep {ord($_) != ord($r)} @w;
  return substr($t, 0, $f).$r.join('', @w);
};
my $ans;
if (length($s)==26) {
  $ans = $next_perm->($s);
} else {
  my %h;
  $h{$_}++ for ('a'..'z');
  $h{$_}++ for split('', $s);
  my @w = sort {$a cmp $b} grep {$h{$_}==1} keys %h;
  $ans = $s . $w[0];
}
say $ans;

まとめ

• next_permutation を自作した

参照したサイト
Javaでnext_permutationメソッドを作ってみる
Perl と Ruby で解く AtCoder ABC146 B - ROT N