求数列反转距离

rubyish

maybe:

1. #!/usr/bin/perl
   
2. 
   
3. my ( $more, $less, $ok, %has );
   
4. 
   
5. sub pick {
   
6.     my ( $a, $min ) = ( shift, $more );
   
7.     my @bad = map {
   
8.         my ( $m, @in ) = ( 0, 0, @$_, $more );
   
9.         abs( $in[ $_ + 1 ] - $in[$_] ) != 1 and $m++ for 0 .. @$_;
   
10.         $m < $min ? ( $min = $m ) : $m;
    
11.     } @$a;
    
12.     [ @$a[ grep { $bad[$_] == $min } 0 .. $#bad ] ];
    
13. }
    
14. 
    
15. sub turn {
    
16.     my ( $a, $it ) = @_;
    
17.     my @good = map {
    
18.         my @fore = @$_;
    
19.         map {
    
20.             my $i = $_;
    
21.             map {
    
22.                 my @new = @fore;
    
23.                 @new[ $i .. $_ ] = reverse @new[ $i .. $_ ];
    
24.                 my $this = join $", @new;
    
25.                 print "count = $it\n" and return if $this eq $ok;
    
26.                 !$has{$this}++ ? [@new] : ()
    
27.             } $i + 1 .. $#fore;
    
28.         } 0 .. $less;
    
29.     } @$a;
    
30.     [@good];
    
31. }
    
32. 
    
33. sub count {
    
34.     my ( $A, $B ) = @_;
    
35.     print "count = 0\n" and return if "@$A" eq "@$B";
    
36.     my $it   = 0;
    
37.     my @A    = map { $_ + 1 } sort { $A->[$a] <=> $A->[$b] } 0 .. $#$A;
    
38.     my @B    = map { $A[ $_ - 1 ] } @$B;
    
39.     my $good = [ [@B] ];
    
40.     %has = ( "@B", 1 );
    
41.     $good = pick( turn( $good, ++$it ) or return ) while 1;
    
42. }
    
43. 
    
44. while (<DATA>) {
    
45.     my $next = <DATA>;
    
46.     print $/, $_, $next;
    
47.     my $A = [split];
    
48.     my $B = [ split /\s/, $next ];
    
49.     $more = @$A + 1;
    
50.     $less = $#$A - 1;
    
51.     $ok   = join $", 1 .. @$A;
    
52.     count $A, $B;
    
53. }
    
54. 
    
55. # 9 4 5 7 0
    
56. 
    
57. __DATA__
    
58. 1 2 3 4 5 6 7 8 9 10
    
59. 3 1 5 2 7 4 9 6 10 8
    
60. 3 10 8 2 5 4 7 1 6 9
    
61. 5 2 3 1 7 4 10 8 6 9
    
62. 8 6 7 9 4 1 3 10 2 5
    
63. 8 2 7 6 9 1 5 3 10 4
    
64. 3 9 10 4 1 8 6 7 5 2
    
65. 2 9 8 5 1 7 3 4 6 10
    
66. 1 2 3 4 5 6 7 8 9 10
    
67. 1 2 3 4 5 6 7 8 9 10
    

复制代码

anna_bi

回复 11# rubyish
测试了，结果是对的，谢谢大神


   

anna_bi

回复 11# rubyish
大神，我perl知识有限，没看太明白，能大概讲一下思路算法吗


   

rubyish

回复 13# anna_bi

biru [pseudocode]:

1. 
   
2. 
   
3. ok = [1 .. 10]
   
4. b  = [5 4 1 8 7 6 2 3 9 10]
   
5. B  = [b]
   
6. c  = 0
   
7. 
   
8. LOOP
   
9.     c++
   
10.     all = turn B
    
11.     FOR this all
    
12.         IF this EQ ok
    
13.             SAY c
    
14.             STOP LOOP
    
15. 
    
16.     B = pick all
    
17.    
    

复制代码

1: sub count

__DATA__
3 10 8 2 5 4 7 1 6 9
5 2 3 1 7 4 10 8 6 9


$A: 3 10 8 2 5 4 7 1 6 9
@A: 8 4 1 6 5 9 7 3 10 2

8:  1 de index + 1
4:  2 de index + 1
1:  3 de index + 1
6:  4 de index + 1
...
2:  10 de index + 1

@A: 8 4 1 6 5 9 7 3 10 2
$B: 5 2 3 1 7 4 10 8 6 9
@B: 5 4 1 8 7 6 2 3 9 10

5:  @A de index ( 5 - 1 )
4:  @A de index ( 2 - 1 )
1:  @A de index ( 3 - 1 )
...
10: @A de index ( 9 - 1　)

@B:     5 4 1 8 7 6 2 3 9 10
$ok:    1 2 3 4 5 6 7 8 9 10

IF @B EQ $ok => finish


2: sub turn, reverse 1 ci, pailie chu suoyou de keneng

@all = turn [ [ 1, 2, 3, 4, 5 ] ];
@all:

[ 2, 1, 3, 4, 5 ]   0 .. 1
[ 3, 2, 1, 4, 5 ]   0 .. 2
[ 4, 3, 2, 1, 5 ]   0 .. 3
[ 5, 4, 3, 2, 1 ]   0 .. 4
[ 1, 3, 2, 4, 5 ]   1 .. 2
[ 1, 4, 3, 2, 5 ]   1 .. 3
[ 1, 5, 4, 3, 2 ]   1 .. 4
[ 1, 2, 4, 3, 5 ]   2 .. 3
[ 1, 2, 5, 4, 3 ]   2 .. 4
[ 1, 2, 3, 5, 4 ]   3 .. 4



3: sub pick, xuanze breakpoint zhuishao de zuhe

@good = pick @all;

breakpoint: X
2 X 5 6 X 1 X 7   

abs( 5 - 2 ) != 1   => bp
abs( 6 - 5 ) == 1   => not bp
abs( 1 - 6 ) != 1   => bp
...



   

anna_bi

回复 14# rubyish
明白了，谢谢大神