Use a Schwartzian transform - like this: (update: but see salva's comment below for a better approach)

@sorted = map {$_->[0]}
          map {
             $i=0; sort {$b->[1]<=>$a->[1]} map {[$i++,$_]} splice (@s
+im,0,9)
          } 0..8;

print "\@index_ordered =(\n";
for(0..8) {
    print " " x 4, join(', ', splice (@sorted,0,9) ),"\n";
}
print ");\n";
[download]

Output:

@index_ordered =(
    0, 1, 3, 2, 4, 5, 7, 8, 6
    1, 0, 3, 8, 2, 4, 7, 6, 5
    2, 3, 8, 0, 1, 4, 7, 5, 6
    3, 0, 1, 2, 8, 7, 6, 4, 5
    4, 8, 7, 0, 1, 2, 6, 3, 5
    5, 0, 7, 1, 2, 3, 6, 8, 4
    6, 7, 8, 3, 4, 1, 2, 0, 5
    7, 6, 8, 3, 4, 0, 1, 5, 2
    8, 7, 6, 3, 4, 1, 2, 0, 5
);
[download]

For equal elements in each row of @sim the order of their indices is undetermined. Note that this is destructive to @sim - it will be empty after the sort.

While the above code DWYM, you would have been better off having an array of arrays in the first place.

_($_=" "x(1<<5)."?\n".q·/)Oo.  G°\        /
                              /\_¯/(q    /
----------------------------  \__(m.====·.(_("always off the crowd"))."·
");sub _{s./.($e="'Itrs `mnsgdq Gdbj O`qkdq")=~y/"-y/#-z/;$e.e && print}

Use a Schwartzian transform

To sort lists of nine elements, applying the ST is probably counterproductive. And anyway, for that particular problem, using a Orcish Maneuver would be more suitable:

my @index_sorted = map {
  my @row = splice @sim, 0, N;
  sort { $row[$b] <=> $row[$a] } 0..(N-1);
} 0..(M-1);
[download]

Just a nit - while your approach is far better than mine and less convoluted, there's no OR and no cache, so there's no Orcish (or-cache) Maneuver. That would be (from Shlomo Yona's Perl lectures 2002):

The Orcish Maneuver -- example

keys my %or_cache = @in;
@out = sort {
    ($or_cache{$a} ||= KEY($a))
    cmp
    ($or_cache{$b} ||= KEY($b))
} @in;
[download]

The first part of the sortsub sees if the sortkey for $a is cached.

If not, it extracts the value of the sortkey from the operand and caches it.

The sortkey for $a is then compared to the sortkey for $b.

Anyways, salva++ for simplifying things :-)

--shmem

_($_=" "x(1<<5)."?\n".q·/)Oo.  G°\        /
                              /\_¯/(q    /
----------------------------  \__(m.====·.(_("always off the crowd"))."·
");sub _{s./.($e="'Itrs `mnsgdq Gdbj O`qkdq")=~y/"-y/#-z/;$e.e && print}

use constant M => 9;
use constant N => 9;

my @index_sorted;
for my $m (0..(M-1)) {
  my $ix0 = $m * N
  push @index_sorted,
    sort { $sim[$ix0 + $b] <=> $sim[$ix0 + $a] } 0..(N-1);
}
[download]

Ooops!

syntax error at /tmp/615254.pl line 41, near "N
    push"
[download]

After some correction (and addition to print out the sorted array), here is the result:

0   1   3   2   4   5   7   8   6
1   0   3   8   2   4   7   6   5
2   3   8   0   1   4   7   5   6
3   0   1   2   8   7   6   4   5
4   8   7   0   1   2   6   3   5
5   0   7   1   2   3   6   8   4
6   7   8   3   4   1   2   0   5
7   6   8   3   4   0   1   5   2
8   7   6   3   4   1   2   0   5
[download]

This orcish manuever is really new to me. And I'm tempted to benchmark these two techniques. Here it goes:

#!/usr/bin/perl

use strict;
use warnings;

my @sim_st = qw(
    1.0    0.9    0.3    0.6    0.3    0.3    0.2    0.3    0.3
    0.9    1.0    0.3    0.5    0.3    0.1    0.2    0.3    0.4
    0.3    0.3    1.0    0.6    0.3    0.2    0.2    0.3    0.4
    0.6    0.6    0.6    1.0    0.2    0.2    0.3    0.4    0.5
    0.3    0.3    0.3    0.2    1.0    0.1    0.3    0.4    0.5
    0.3    0.2    0.2    0.2    0.1    1.0    0.2    0.3    0.2
    0.1    0.2    0.2    0.3    0.3    0.1    1.0    0.8    0.6
    0.3    0.3    0.2    0.4    0.4    0.3    0.8    1.0    0.8
    0.3    0.4    0.4    0.5    0.5    0.2    0.6    0.8    1.0
);

my @sim_om = @sim_st;

use Benchmark 'cmpthese';

my $count = shift || -1;
cmpthese $count, {
    sort_with_st => \&sort_st,
    sort_with_om => \&sort_om,
};

sub sort_st {
    my @sim = @sim_st;
    my @sorted =
       map { $_->[0] }
          map {
            my $i = 0;
            sort { $b->[1] <=> $a->[1] }
                 map { [$i++, $_] } splice (@sim, 0, 9)
         }
         0..8;
}

use constant { M => 9, N => 9 };
sub sort_om {
   my @index_sorted;
   for my $m (0..(M-1)) {
      my $ix0 = $m * N;
      push @index_sorted,
           sort { $sim_om[$ix0 + $b] <=> $sim_om[$ix0 + $a] }
                0..(N-1);
   }
}
[download]

And here is the benchmark, kinda speaks for itself:

$ perl benchmark-sort.pl
               Rate sort_with_st sort_with_om
sort_with_st 3011/s           --         -61%
sort_with_om 7724/s         156%           --
[download]

Thanks and ++ goes to shmem and salva for the lessons.

---

Open source softwares? Share and enjoy. Make profit from them if you can. Yet, share and enjoy!

Unless I'm being dense (quite possible), I think that you are going to have to explain what you mean by

... the index is sorted decreasingly according to similarity value in @sim.

because I can see no corrolation between the values in those two arrays?

The identical values (1.0) along the main (tl/br) diagonal are mapped to 5 different values (0,1,2,5,8) in the result? You have 9 "indexes" (0..8) in the result, and there are 9 unique values in the input which seems to indicate something, but how the same value in the input results in different indexes in the output completely eludes me.

I'm guessing that the "according to similarity value" is the key, but it's going right over my head at the moment?