And I think my solution is better because Z has only one relation. (YMMV)

use v5.12;
use warnings;
use Data::Dump qw/pp dd ddx/;

use Test::More;

my @list1= qw( K B I S Y A Q );
my @list2= qw( B S N A );
my @list3= qw( Y N Q );

my $combined = combined_order(\@list1, \@list2, \@list3);
my $expected = [qw( K B I S Y N A Q )];


is_deeply( $combined, $expected )
  or diag pp { got => $combined, exp => $expected };


my @lists2= (
    [qw( X P Y )],
    [qw( X B Y N )],
    [qw( P B N )],
    [qw( X B P N )],
    [qw( X B P Y )],
    [qw( A Z )],
    [qw( A K L )],
   );

# my $dbg_sort = gen_sort_by_orders(@lists2);
# ($a,$b) = qw/B X/;
# is(signum(&$dbg_sort), 1, "$a cmp $b");
# ($a,$b) = qw/X B/;
# is(signum(&$dbg_sort), -1, "$a cmp $b");



my $combined2 = combined_order(@lists2);
my $expected2 = [qw( X B P Y N A Z K L )];
is_deeply( $combined2, $expected2 )
  or diag pp { got => $combined2, exp => $expected2 };

sub combined_order {
    my @orders = @_;
    my @total = map {@$_} @orders;

    my %uniq;
    @uniq{@total} =();
    @total = keys %uniq;

    my $osort = gen_sort_by_orders (@orders);

    #ddx @total;
    return [ sort {&$osort} @total ]; 
}

sub signum {
    my ($val) = @_;
    return 0  unless $val;              # 0 or undef
    return $val / abs($val);
}

sub gen_sort_by_orders {
    my @orders = @_;

    my %cmp;                            # relation matrix
    my %count;
    for my $order (@orders) {
        my @list = @$order;
        while (my $before = shift @list) {
            for my $after (@list) {
                # comparing lesser < greater is enough bc of symmetry
                $before lt $after  
                  ? $cmp{$before}{$after}--
                  : $cmp{$after}{$before}++;

                # we count the relations for second criteria
                $count{$before}++;
                $count{$after}++;
            }
        }
    }

    ddx { "Matrix:" => \%cmp, "Count:" =>  \%count };           # debu
+g
    
    my $osort = sub {
        return
          (
              $a lt $b
              ?   ( $cmp{$a}{$b} // 0 )
              : - ( $cmp{$b}{$a} // 0 ) 
           )
          || ( $count{$b} - $count{$a} ) # more relations win
          || $a cmp $b                   # default anti ambiguity
      };
    
    return $osort;
}


done_testing;
[download]

perl /home/lanx/perl/multisort.pl
# multisort.pl:83: {
#   "Count:"  => { A => 9, B => 9, I => 6, K => 6, N => 5, Q => 8, S =
+> 9, Y => 8 },
#   "Matrix:" => {
#                  A => { B => 2, I => 1, K => 1, N => 1, Q => -1, S =
+> 2, Y => 1 },
#                  B => { I => -1, K => 1, N => -1, Q => -1, S => -2, 
+Y => -1 },
#                  I => { K => 1, Q => -1, S => -1, Y => -1 },
#                  K => { Q => -1, S => -1, Y => -1 },
#                  N => { Q => -1, S => 1, Y => 1 },
#                  Q => { S => 1, Y => 2 },
#                  S => { Y => -1 },
#                },
# }
ok 1
# multisort.pl:83: {
#   "Count:"  => { A => 3, B => 11, K => 2, L => 2, N => 8, P => 10, X
+ => 11, Y => 8, Z => 1 },
#   "Matrix:" => {
#                  A => { K => -1, L => -1, Z => -1 },
#                  B => { N => -3, P => -1, X => 3, Y => -2 },
#                  K => { L => -1 },
#                  N => { P => 2, X => 2, Y => 1 },
#                  P => { X => 3, Y => -2 },
#                  X => { Y => -3 },
#                },
# }
not ok 2
#   Failed test at /home/lanx/perl/multisort.pl line 39.
#     Structures begin differing at:
#          $got->[6] = 'K'
#     $expected->[6] = 'Z'
# {
#   exp => ["X", "B", "P", "Y", "N", "A", "Z", "K", "L"],
#   got => ["X", "B", "P", "Y", "N", "A", "K", "L", "Z"],
# }
1..2
# Looks like you failed 1 test of 2.
[download]

Thanks! This is pretty similar to what I had, but yours works :-)

Your welcome.

I think the basic idea to construct a dedicated sort with a special lookup table %cmp mimicking cmp is trivial.

Testing the edge cases is tricky tho. Even more with non-ambiguity.

One needs multiple runs to be -kind of - sure that it's stable for different internal permutations.

Not sure if there is a fault prove way to test it.

On a side note: which version do you prefer, mine or tybalt89's?

Cheers Rolf
_{(addicted to the Perl Programming Language :)
see Wikisyntax for the Monastery}

Could you please elaborate where and why your $combined2 is better?

(UPDATE: If there is a quantifiable reason why "X" should be ordered before "A", I'm sure this can be added to the sort function, see cmp_more_frequently($a,$b) )

It wasn't really a requirement, other than that every time you give the algorithm those inputs in that order, you get the same output. In other words I don't want it to depend on hash randomization, so I think original input order should be used as a tie-breaker. When I built the example, I put 'A' after everything else since there was no relation to the previous rules and the rule with 'A' came later. Same with 'Z' vs. 'K'.