This still sounds like an answer to the wrong problem. For even modest sized lists the number of permutations is huge. However the following code using Math::Combinatorics should get you started:

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 co
+py
    
    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 < @listAp
+erm;
            push @interList2, $listBperm[$bIndex] if $bIndex < @listBp
+erm;
            push @interList2, $listAperm[$aIndex++] if $aIndex < @list
+Aperm;
            push @interList1, $listBperm[$bIndex++] if $bIndex < @list
+Bperm;
        }
        
        print "@interList1\n";
        print "@interList2\n";
    }
}
[download]

If you already have the means to generate all the permutations of a list, then I suspect that generating all permutations of each source list and then interleaving each pair of those would be much faster, much simpler, and much less memory-intensive than generating all permutations of the combined source lists and filtering out those which aren't interleaved.

thanks for you help guys

this sounds like the easy way to do it i new was staring me in the face all along

i've also had a bit of a better chat with him about why its needed etc and i think there are multiple powers of xy problem involved here

basically its all to do with how easy different lists of symbols (generally letters) are to remember due to factors like whether or not the letters sound the same and the probability of them occuring together in the native language

he wants all the permutations because once he has them he's going to have me remove any that contain well known acronyms and then sort them into subsets according to these transitional probabilities (and yes i'm well aware we are talking about very large numbers of permutations), the interleaving thing was for mixing sets of confusable (sound the same) and nonconfusable letters

the thing is for the time being he wants each letter to occupy each place an equal number of times in his set of lists - a latin square which i could have easily done anyway so yes xy^3 sorry (i will still need to do this permute and interleave though)