use strict;
use warnings;
use Math::Combinatorics;

my @listA = qw(first second third);
my @listB = qw(1 2 3);
my $permA = Math::Combinatorics->new (data => [@listA]); # Note copy

while (1) {
    my @listAperm = $permA->next_permutation ();
    
    last if ! @listAperm;
    my $permB = Math::Combinatorics->new (data => [@listB]); # Note copy
    
    while (1) {
        my @listBperm = $permB->next_permutation ();
        
        last if ! @listBperm;
        
        my @interList1;
        my @interList2;
        my $aIndex = 0;
        my $bIndex = 0;
        while ($aIndex < @listAperm || $bIndex < @listBperm) {
            push @interList1, $listAperm[$aIndex] if $aIndex < @listAperm;
            push @interList2, $listBperm[$bIndex] if $bIndex < @listBperm;
            push @interList2, $listAperm[$aIndex++] if $aIndex < @listAperm;
            push @interList1, $listBperm[$bIndex++] if $bIndex < @listBperm;
        }
        
        print "@interList1\n";
        print "@interList2\n";
    }
}