I'm looking for an algorithm that can take lists of strings that are in a user-declared logical order, and merge those lists in the way that preserves the most of those logical orderings.

Example:

use Test2::V0;
use v5.40;

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= fancy_algorithm(\@list1, \@list2, \@list3);
is( $combined, [qw( K B I S Y N A Q )] );
[download]

use Test2::V0;
use v5.40;

my @lists= (
  [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 $combined= fancy_algorithm(@lists);
is( $combined, [qw( X B P Y N A Z K L )] );
[download]

Why is it relevant? because on more than one occasion I've wanted to export user data with the columns in the "natural order", but I'm combining multiple independent data sets and for each dataset the user has chosen the column names according to some ordering that makes sense to them but which the system has no knowledge of. I have a solution that "mostly works", but I keep finding edge cases where it breaks. I'm curious if there is a complete solution to the problem.

Edit: ...and hopefully more efficient than just running every permutation of output looking for the one with the highest score. Sometimes there are a lot of columns and that could be bad.

snprintf (enc->cur, IVUV_MAXCHARS, "%" UVuf, uv)
[download]

XS.xs:2449:66: warning: format '%u' expects argument of type 'unsigned
+ int', but argument 4 has type 'long long unsigned int' [-Wformat=]
[download]