This sounds either like an XY Problem or like homework. Perhaps you should paint the broarder picture for us so we understand better what you are after?

It seems it doesn't matter what order the list elements occur in so long as they alternate from list A and list B. Can the lists have duplicate entries (either between lists, or within a list)? Is it guaranteed that the lists differ by no more than 1 in the number of their elements?

not homework but almost certainly an xy problem

what i need is ALL the lists which you can make by interleaving elements from listA and listB

why is another question entirley, i don't really know except that its for some form of memory experiment, the guy i work for asked me for a script to do all the permutations of a list which i gave him and then he asked me for this

and yes your right the brute force method of just generating all the permutations and then selecting the ones i'm interested was assumption on my part of the easiest way to do it

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]

Read more... output (2 kB)

---

DWIM is Perl's answer to Gödel

Sounds like the guy you're working for may have an XY problem, too... (Does that mean you have an X^2Y^2 problem? Or would it be an X^2 + 2XY + Y^2 problem?)

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.

# comparing @merged with @a and @b:
my $pass = 1;
for (my ($ai,$bi,$mi) = (0,0,0); $mi < $#merged; ) {
    ($a[$ai++] eq $merged[$mi++]) or $pass = 0 or last;
    ($b[$bi++] eq $merged[$mi++]) or $pass = 0 or last;
}
[download]

How (Not) To Ask A Question

(Removed as this smells too much like homework)