Inserting all elements of second list while maintaining the order of the elements in the first list in Python

Question

I have two lists, let's say lst1 = [4, 6, 11, 0, 1, 2, 5] and lst2 = [10, 3, 8]. I would like to list all permutations of inserting lst2 into lst1 such that the order of lst1 is maintained (order of lst2 need not be maintained). All elements in both lists are unique and order matters. Some potential valid results are

[10, 4, 6, 11, 0, 1, 3, 2, 8, 5]

[4, 6, 8, 10, 11, 0, 3, 1, 2, 5]

[4, 8, 6, 10, 11, 0, 1, 3, 2, 5] etc.

(lst1 elements are in order and lst2 elements may not be). Further, lst1 is circular, as is the resultant list containing all elements.

The total number of permutations of 7 (x) and 4(n) elements is given as the rising factorial --> (x+n-1)!/ (x-1)!. In this example, this would equal 7 * 8 * 9 * 10 = 5040 possibilities. error n=3 not 4, so the answer is 504. Thanks to Slothrop for catching the error!!

I tried the following, but it prints results that are not consistent with what I want. It prints lists without some elements of lst2 included in it. (I would like to do other operations for each of these permutations, so the result should not print results without including all elements of lst2.)

for locations in itertools.permutations(range(len(lst1) + len(lst2)-1), len(lst2)):
    result = lst1[:]
    for location, element in zip(locations, lst2):
        result.insert(location, element)
        print(result)
        

Answer 1

Without using libraries, a recursive generator function could progressively insert items of the second list after each element of the first list:

def insertPatterns(L1,L2):
    if not L2:
        yield L1
        return
    for i in range(1,len(L1)+1):
        yield from insertPatterns(L1[:i]+L2[:1]+L1[i:],L2[1:])

output:

lst1 = [4, 6, 11, 0, 1, 2, 5]
lst2 = [10, 3, 8]

sum(1 for _ in insertPatterns(lst1,lst2)) # 504 patterns

print(*insertPatterns(lst1,lst2),sep="\n")

[4, 8, 3, 10, 6, 11, 0, 1, 2, 5]
[4, 3, 8, 10, 6, 11, 0, 1, 2, 5]
[4, 3, 10, 8, 6, 11, 0, 1, 2, 5]
[4, 3, 10, 6, 8, 11, 0, 1, 2, 5]
[4, 3, 10, 6, 11, 8, 0, 1, 2, 5]
[4, 3, 10, 6, 11, 0, 8, 1, 2, 5]
[4, 3, 10, 6, 11, 0, 1, 8, 2, 5]
[4, 3, 10, 6, 11, 0, 1, 2, 8, 5]
[4, 3, 10, 6, 11, 0, 1, 2, 5, 8]
[4, 8, 10, 3, 6, 11, 0, 1, 2, 5]
[4, 10, 8, 3, 6, 11, 0, 1, 2, 5]
[4, 10, 3, 8, 6, 11, 0, 1, 2, 5]
[4, 10, 3, 6, 8, 11, 0, 1, 2, 5]
[4, 10, 3, 6, 11, 8, 0, 1, 2, 5]
[4, 10, 3, 6, 11, 0, 8, 1, 2, 5]
[4, 10, 3, 6, 11, 0, 1, 8, 2, 5]
[4, 10, 3, 6, 11, 0, 1, 2, 8, 5]
[4, 10, 3, 6, 11, 0, 1, 2, 5, 8]
[4, 8, 10, 6, 3, 11, 0, 1, 2, 5]
[4, 10, 8, 6, 3, 11, 0, 1, 2, 5]
[4, 10, 6, 8, 3, 11, 0, 1, 2, 5]
[4, 10, 6, 3, 8, 11, 0, 1, 2, 5]
[4, 10, 6, 3, 11, 8, 0, 1, 2, 5]
[4, 10, 6, 3, 11, 0, 8, 1, 2, 5]
[4, 10, 6, 3, 11, 0, 1, 8, 2, 5]
[4, 10, 6, 3, 11, 0, 1, 2, 8, 5]
[4, 10, 6, 3, 11, 0, 1, 2, 5, 8]
[4, 8, 10, 6, 11, 3, 0, 1, 2, 5]
[4, 10, 8, 6, 11, 3, 0, 1, 2, 5]
[4, 10, 6, 8, 11, 3, 0, 1, 2, 5]
[4, 10, 6, 11, 8, 3, 0, 1, 2, 5]
[4, 10, 6, 11, 3, 8, 0, 1, 2, 5]
[4, 10, 6, 11, 3, 0, 8, 1, 2, 5]
[4, 10, 6, 11, 3, 0, 1, 8, 2, 5]
[4, 10, 6, 11, 3, 0, 1, 2, 8, 5]
[4, 10, 6, 11, 3, 0, 1, 2, 5, 8]
[4, 8, 10, 6, 11, 0, 3, 1, 2, 5]
[4, 10, 8, 6, 11, 0, 3, 1, 2, 5]
[4, 10, 6, 8, 11, 0, 3, 1, 2, 5]
[4, 10, 6, 11, 8, 0, 3, 1, 2, 5]
[4, 10, 6, 11, 0, 8, 3, 1, 2, 5]
[4, 10, 6, 11, 0, 3, 8, 1, 2, 5]
[4, 10, 6, 11, 0, 3, 1, 8, 2, 5]
[4, 10, 6, 11, 0, 3, 1, 2, 8, 5]
[4, 10, 6, 11, 0, 3, 1, 2, 5, 8]
[4, 8, 10, 6, 11, 0, 1, 3, 2, 5]
[4, 10, 8, 6, 11, 0, 1, 3, 2, 5]
[4, 10, 6, 8, 11, 0, 1, 3, 2, 5]
[4, 10, 6, 11, 8, 0, 1, 3, 2, 5]
[4, 10, 6, 11, 0, 8, 1, 3, 2, 5]
[4, 10, 6, 11, 0, 1, 8, 3, 2, 5]
[4, 10, 6, 11, 0, 1, 3, 8, 2, 5]
[4, 10, 6, 11, 0, 1, 3, 2, 8, 5]
[4, 10, 6, 11, 0, 1, 3, 2, 5, 8]
[4, 8, 10, 6, 11, 0, 1, 2, 3, 5]
[4, 10, 8, 6, 11, 0, 1, 2, 3, 5]
[4, 10, 6, 8, 11, 0, 1, 2, 3, 5]
[4, 10, 6, 11, 8, 0, 1, 2, 3, 5]
[4, 10, 6, 11, 0, 8, 1, 2, 3, 5]
[4, 10, 6, 11, 0, 1, 8, 2, 3, 5]
[4, 10, 6, 11, 0, 1, 2, 8, 3, 5]
[4, 10, 6, 11, 0, 1, 2, 3, 8, 5]
[4, 10, 6, 11, 0, 1, 2, 3, 5, 8]
[4, 8, 10, 6, 11, 0, 1, 2, 5, 3]
[4, 10, 8, 6, 11, 0, 1, 2, 5, 3]
[4, 10, 6, 8, 11, 0, 1, 2, 5, 3]
[4, 10, 6, 11, 8, 0, 1, 2, 5, 3]
[4, 10, 6, 11, 0, 8, 1, 2, 5, 3]
[4, 10, 6, 11, 0, 1, 8, 2, 5, 3]
[4, 10, 6, 11, 0, 1, 2, 8, 5, 3]
[4, 10, 6, 11, 0, 1, 2, 5, 8, 3]
[4, 10, 6, 11, 0, 1, 2, 5, 3, 8]
[4, 8, 3, 6, 10, 11, 0, 1, 2, 5]
[4, 3, 8, 6, 10, 11, 0, 1, 2, 5]
[4, 3, 6, 8, 10, 11, 0, 1, 2, 5]
[4, 3, 6, 10, 8, 11, 0, 1, 2, 5]
[4, 3, 6, 10, 11, 8, 0, 1, 2, 5]
[4, 3, 6, 10, 11, 0, 8, 1, 2, 5]
[4, 3, 6, 10, 11, 0, 1, 8, 2, 5]
[4, 3, 6, 10, 11, 0, 1, 2, 8, 5]
[4, 3, 6, 10, 11, 0, 1, 2, 5, 8]
[4, 8, 6, 3, 10, 11, 0, 1, 2, 5]
[4, 6, 8, 3, 10, 11, 0, 1, 2, 5]
[4, 6, 3, 8, 10, 11, 0, 1, 2, 5]
[4, 6, 3, 10, 8, 11, 0, 1, 2, 5]
[4, 6, 3, 10, 11, 8, 0, 1, 2, 5]
[4, 6, 3, 10, 11, 0, 8, 1, 2, 5]
[4, 6, 3, 10, 11, 0, 1, 8, 2, 5]
[4, 6, 3, 10, 11, 0, 1, 2, 8, 5]
[4, 6, 3, 10, 11, 0, 1, 2, 5, 8]
[4, 8, 6, 10, 3, 11, 0, 1, 2, 5]
[4, 6, 8, 10, 3, 11, 0, 1, 2, 5]
[4, 6, 10, 8, 3, 11, 0, 1, 2, 5]
[4, 6, 10, 3, 8, 11, 0, 1, 2, 5]
[4, 6, 10, 3, 11, 8, 0, 1, 2, 5]
[4, 6, 10, 3, 11, 0, 8, 1, 2, 5]
[4, 6, 10, 3, 11, 0, 1, 8, 2, 5]
[4, 6, 10, 3, 11, 0, 1, 2, 8, 5]
[4, 6, 10, 3, 11, 0, 1, 2, 5, 8]
[4, 8, 6, 10, 11, 3, 0, 1, 2, 5]
[4, 6, 8, 10, 11, 3, 0, 1, 2, 5]
[4, 6, 10, 8, 11, 3, 0, 1, 2, 5]
[4, 6, 10, 11, 8, 3, 0, 1, 2, 5]
[4, 6, 10, 11, 3, 8, 0, 1, 2, 5]
[4, 6, 10, 11, 3, 0, 8, 1, 2, 5]
[4, 6, 10, 11, 3, 0, 1, 8, 2, 5]
[4, 6, 10, 11, 3, 0, 1, 2, 8, 5]
[4, 6, 10, 11, 3, 0, 1, 2, 5, 8]
[4, 8, 6, 10, 11, 0, 3, 1, 2, 5]
[4, 6, 8, 10, 11, 0, 3, 1, 2, 5]
[4, 6, 10, 8, 11, 0, 3, 1, 2, 5]
[4, 6, 10, 11, 8, 0, 3, 1, 2, 5]
[4, 6, 10, 11, 0, 8, 3, 1, 2, 5]
[4, 6, 10, 11, 0, 3, 8, 1, 2, 5]
[4, 6, 10, 11, 0, 3, 1, 8, 2, 5]
[4, 6, 10, 11, 0, 3, 1, 2, 8, 5]
[4, 6, 10, 11, 0, 3, 1, 2, 5, 8]
[4, 8, 6, 10, 11, 0, 1, 3, 2, 5]
[4, 6, 8, 10, 11, 0, 1, 3, 2, 5]
[4, 6, 10, 8, 11, 0, 1, 3, 2, 5]
[4, 6, 10, 11, 8, 0, 1, 3, 2, 5]
[4, 6, 10, 11, 0, 8, 1, 3, 2, 5]
[4, 6, 10, 11, 0, 1, 8, 3, 2, 5]
[4, 6, 10, 11, 0, 1, 3, 8, 2, 5]
[4, 6, 10, 11, 0, 1, 3, 2, 8, 5]
[4, 6, 10, 11, 0, 1, 3, 2, 5, 8]
[4, 8, 6, 10, 11, 0, 1, 2, 3, 5]
[4, 6, 8, 10, 11, 0, 1, 2, 3, 5]
[4, 6, 10, 8, 11, 0, 1, 2, 3, 5]
[4, 6, 10, 11, 8, 0, 1, 2, 3, 5]
[4, 6, 10, 11, 0, 8, 1, 2, 3, 5]
[4, 6, 10, 11, 0, 1, 8, 2, 3, 5]
[4, 6, 10, 11, 0, 1, 2, 8, 3, 5]
[4, 6, 10, 11, 0, 1, 2, 3, 8, 5]
[4, 6, 10, 11, 0, 1, 2, 3, 5, 8]
[4, 8, 6, 10, 11, 0, 1, 2, 5, 3]
[4, 6, 8, 10, 11, 0, 1, 2, 5, 3]
[4, 6, 10, 8, 11, 0, 1, 2, 5, 3]
[4, 6, 10, 11, 8, 0, 1, 2, 5, 3]
[4, 6, 10, 11, 0, 8, 1, 2, 5, 3]
[4, 6, 10, 11, 0, 1, 8, 2, 5, 3]
[4, 6, 10, 11, 0, 1, 2, 8, 5, 3]
[4, 6, 10, 11, 0, 1, 2, 5, 8, 3]
[4, 6, 10, 11, 0, 1, 2, 5, 3, 8]
[4, 8, 3, 6, 11, 10, 0, 1, 2, 5]
[4, 3, 8, 6, 11, 10, 0, 1, 2, 5]
[4, 3, 6, 8, 11, 10, 0, 1, 2, 5]
[4, 3, 6, 11, 8, 10, 0, 1, 2, 5]
[4, 3, 6, 11, 10, 8, 0, 1, 2, 5]
[4, 3, 6, 11, 10, 0, 8, 1, 2, 5]
[4, 3, 6, 11, 10, 0, 1, 8, 2, 5]
[4, 3, 6, 11, 10, 0, 1, 2, 8, 5]
[4, 3, 6, 11, 10, 0, 1, 2, 5, 8]
[4, 8, 6, 3, 11, 10, 0, 1, 2, 5]
[4, 6, 8, 3, 11, 10, 0, 1, 2, 5]
[4, 6, 3, 8, 11, 10, 0, 1, 2, 5]
[4, 6, 3, 11, 8, 10, 0, 1, 2, 5]
[4, 6, 3, 11, 10, 8, 0, 1, 2, 5]
[4, 6, 3, 11, 10, 0, 8, 1, 2, 5]
[4, 6, 3, 11, 10, 0, 1, 8, 2, 5]
[4, 6, 3, 11, 10, 0, 1, 2, 8, 5]
[4, 6, 3, 11, 10, 0, 1, 2, 5, 8]
[4, 8, 6, 11, 3, 10, 0, 1, 2, 5]
[4, 6, 8, 11, 3, 10, 0, 1, 2, 5]
[4, 6, 11, 8, 3, 10, 0, 1, 2, 5]
[4, 6, 11, 3, 8, 10, 0, 1, 2, 5]
[4, 6, 11, 3, 10, 8, 0, 1, 2, 5]
[4, 6, 11, 3, 10, 0, 8, 1, 2, 5]
[4, 6, 11, 3, 10, 0, 1, 8, 2, 5]
[4, 6, 11, 3, 10, 0, 1, 2, 8, 5]
[4, 6, 11, 3, 10, 0, 1, 2, 5, 8]
[4, 8, 6, 11, 10, 3, 0, 1, 2, 5]
[4, 6, 8, 11, 10, 3, 0, 1, 2, 5]
[4, 6, 11, 8, 10, 3, 0, 1, 2, 5]
[4, 6, 11, 10, 8, 3, 0, 1, 2, 5]
[4, 6, 11, 10, 3, 8, 0, 1, 2, 5]
[4, 6, 11, 10, 3, 0, 8, 1, 2, 5]
[4, 6, 11, 10, 3, 0, 1, 8, 2, 5]
[4, 6, 11, 10, 3, 0, 1, 2, 8, 5]
[4, 6, 11, 10, 3, 0, 1, 2, 5, 8]
[4, 8, 6, 11, 10, 0, 3, 1, 2, 5]
[4, 6, 8, 11, 10, 0, 3, 1, 2, 5]
[4, 6, 11, 8, 10, 0, 3, 1, 2, 5]
[4, 6, 11, 10, 8, 0, 3, 1, 2, 5]
[4, 6, 11, 10, 0, 8, 3, 1, 2, 5]
[4, 6, 11, 10, 0, 3, 8, 1, 2, 5]
[4, 6, 11, 10, 0, 3, 1, 8, 2, 5]
[4, 6, 11, 10, 0, 3, 1, 2, 8, 5]
[4, 6, 11, 10, 0, 3, 1, 2, 5, 8]
[4, 8, 6, 11, 10, 0, 1, 3, 2, 5]
[4, 6, 8, 11, 10, 0, 1, 3, 2, 5]
[4, 6, 11, 8, 10, 0, 1, 3, 2, 5]
[4, 6, 11, 10, 8, 0, 1, 3, 2, 5]
[4, 6, 11, 10, 0, 8, 1, 3, 2, 5]
[4, 6, 11, 10, 0, 1, 8, 3, 2, 5]
[4, 6, 11, 10, 0, 1, 3, 8, 2, 5]
[4, 6, 11, 10, 0, 1, 3, 2, 8, 5]
[4, 6, 11, 10, 0, 1, 3, 2, 5, 8]
[4, 8, 6, 11, 10, 0, 1, 2, 3, 5]
[4, 6, 8, 11, 10, 0, 1, 2, 3, 5]
[4, 6, 11, 8, 10, 0, 1, 2, 3, 5]
[4, 6, 11, 10, 8, 0, 1, 2, 3, 5]
[4, 6, 11, 10, 0, 8, 1, 2, 3, 5]
[4, 6, 11, 10, 0, 1, 8, 2, 3, 5]
[4, 6, 11, 10, 0, 1, 2, 8, 3, 5]
[4, 6, 11, 10, 0, 1, 2, 3, 8, 5]
[4, 6, 11, 10, 0, 1, 2, 3, 5, 8]
[4, 8, 6, 11, 10, 0, 1, 2, 5, 3]
[4, 6, 8, 11, 10, 0, 1, 2, 5, 3]
[4, 6, 11, 8, 10, 0, 1, 2, 5, 3]
[4, 6, 11, 10, 8, 0, 1, 2, 5, 3]
[4, 6, 11, 10, 0, 8, 1, 2, 5, 3]
[4, 6, 11, 10, 0, 1, 8, 2, 5, 3]
[4, 6, 11, 10, 0, 1, 2, 8, 5, 3]
[4, 6, 11, 10, 0, 1, 2, 5, 8, 3]
[4, 6, 11, 10, 0, 1, 2, 5, 3, 8]
[4, 8, 3, 6, 11, 0, 10, 1, 2, 5]
[4, 3, 8, 6, 11, 0, 10, 1, 2, 5]
[4, 3, 6, 8, 11, 0, 10, 1, 2, 5]
[4, 3, 6, 11, 8, 0, 10, 1, 2, 5]
[4, 3, 6, 11, 0, 8, 10, 1, 2, 5]
[4, 3, 6, 11, 0, 10, 8, 1, 2, 5]
[4, 3, 6, 11, 0, 10, 1, 8, 2, 5]
[4, 3, 6, 11, 0, 10, 1, 2, 8, 5]
[4, 3, 6, 11, 0, 10, 1, 2, 5, 8]
[4, 8, 6, 3, 11, 0, 10, 1, 2, 5]
[4, 6, 8, 3, 11, 0, 10, 1, 2, 5]
[4, 6, 3, 8, 11, 0, 10, 1, 2, 5]
[4, 6, 3, 11, 8, 0, 10, 1, 2, 5]
[4, 6, 3, 11, 0, 8, 10, 1, 2, 5]
[4, 6, 3, 11, 0, 10, 8, 1, 2, 5]
[4, 6, 3, 11, 0, 10, 1, 8, 2, 5]
[4, 6, 3, 11, 0, 10, 1, 2, 8, 5]
[4, 6, 3, 11, 0, 10, 1, 2, 5, 8]
[4, 8, 6, 11, 3, 0, 10, 1, 2, 5]
[4, 6, 8, 11, 3, 0, 10, 1, 2, 5]
[4, 6, 11, 8, 3, 0, 10, 1, 2, 5]
[4, 6, 11, 3, 8, 0, 10, 1, 2, 5]
[4, 6, 11, 3, 0, 8, 10, 1, 2, 5]
[4, 6, 11, 3, 0, 10, 8, 1, 2, 5]
[4, 6, 11, 3, 0, 10, 1, 8, 2, 5]
[4, 6, 11, 3, 0, 10, 1, 2, 8, 5]
[4, 6, 11, 3, 0, 10, 1, 2, 5, 8]
[4, 8, 6, 11, 0, 3, 10, 1, 2, 5]
[4, 6, 8, 11, 0, 3, 10, 1, 2, 5]
[4, 6, 11, 8, 0, 3, 10, 1, 2, 5]
[4, 6, 11, 0, 8, 3, 10, 1, 2, 5]
[4, 6, 11, 0, 3, 8, 10, 1, 2, 5]
[4, 6, 11, 0, 3, 10, 8, 1, 2, 5]
[4, 6, 11, 0, 3, 10, 1, 8, 2, 5]
[4, 6, 11, 0, 3, 10, 1, 2, 8, 5]
[4, 6, 11, 0, 3, 10, 1, 2, 5, 8]
[4, 8, 6, 11, 0, 10, 3, 1, 2, 5]
[4, 6, 8, 11, 0, 10, 3, 1, 2, 5]
[4, 6, 11, 8, 0, 10, 3, 1, 2, 5]
[4, 6, 11, 0, 8, 10, 3, 1, 2, 5]
[4, 6, 11, 0, 10, 8, 3, 1, 2, 5]
[4, 6, 11, 0, 10, 3, 8, 1, 2, 5]
[4, 6, 11, 0, 10, 3, 1, 8, 2, 5]
[4, 6, 11, 0, 10, 3, 1, 2, 8, 5]
[4, 6, 11, 0, 10, 3, 1, 2, 5, 8]
[4, 8, 6, 11, 0, 10, 1, 3, 2, 5]
[4, 6, 8, 11, 0, 10, 1, 3, 2, 5]
[4, 6, 11, 8, 0, 10, 1, 3, 2, 5]
[4, 6, 11, 0, 8, 10, 1, 3, 2, 5]
[4, 6, 11, 0, 10, 8, 1, 3, 2, 5]
[4, 6, 11, 0, 10, 1, 8, 3, 2, 5]
[4, 6, 11, 0, 10, 1, 3, 8, 2, 5]
[4, 6, 11, 0, 10, 1, 3, 2, 8, 5]
[4, 6, 11, 0, 10, 1, 3, 2, 5, 8]
[4, 8, 6, 11, 0, 10, 1, 2, 3, 5]
[4, 6, 8, 11, 0, 10, 1, 2, 3, 5]
[4, 6, 11, 8, 0, 10, 1, 2, 3, 5]
[4, 6, 11, 0, 8, 10, 1, 2, 3, 5]
[4, 6, 11, 0, 10, 8, 1, 2, 3, 5]
[4, 6, 11, 0, 10, 1, 8, 2, 3, 5]
[4, 6, 11, 0, 10, 1, 2, 8, 3, 5]
[4, 6, 11, 0, 10, 1, 2, 3, 8, 5]
[4, 6, 11, 0, 10, 1, 2, 3, 5, 8]
[4, 8, 6, 11, 0, 10, 1, 2, 5, 3]
[4, 6, 8, 11, 0, 10, 1, 2, 5, 3]
[4, 6, 11, 8, 0, 10, 1, 2, 5, 3]
[4, 6, 11, 0, 8, 10, 1, 2, 5, 3]
[4, 6, 11, 0, 10, 8, 1, 2, 5, 3]
[4, 6, 11, 0, 10, 1, 8, 2, 5, 3]
[4, 6, 11, 0, 10, 1, 2, 8, 5, 3]
[4, 6, 11, 0, 10, 1, 2, 5, 8, 3]
[4, 6, 11, 0, 10, 1, 2, 5, 3, 8]
[4, 8, 3, 6, 11, 0, 1, 10, 2, 5]
[4, 3, 8, 6, 11, 0, 1, 10, 2, 5]
[4, 3, 6, 8, 11, 0, 1, 10, 2, 5]
[4, 3, 6, 11, 8, 0, 1, 10, 2, 5]
[4, 3, 6, 11, 0, 8, 1, 10, 2, 5]
[4, 3, 6, 11, 0, 1, 8, 10, 2, 5]
[4, 3, 6, 11, 0, 1, 10, 8, 2, 5]
[4, 3, 6, 11, 0, 1, 10, 2, 8, 5]
[4, 3, 6, 11, 0, 1, 10, 2, 5, 8]
[4, 8, 6, 3, 11, 0, 1, 10, 2, 5]
[4, 6, 8, 3, 11, 0, 1, 10, 2, 5]
[4, 6, 3, 8, 11, 0, 1, 10, 2, 5]
[4, 6, 3, 11, 8, 0, 1, 10, 2, 5]
[4, 6, 3, 11, 0, 8, 1, 10, 2, 5]
[4, 6, 3, 11, 0, 1, 8, 10, 2, 5]
[4, 6, 3, 11, 0, 1, 10, 8, 2, 5]
[4, 6, 3, 11, 0, 1, 10, 2, 8, 5]
[4, 6, 3, 11, 0, 1, 10, 2, 5, 8]
[4, 8, 6, 11, 3, 0, 1, 10, 2, 5]
[4, 6, 8, 11, 3, 0, 1, 10, 2, 5]
[4, 6, 11, 8, 3, 0, 1, 10, 2, 5]
[4, 6, 11, 3, 8, 0, 1, 10, 2, 5]
[4, 6, 11, 3, 0, 8, 1, 10, 2, 5]
[4, 6, 11, 3, 0, 1, 8, 10, 2, 5]
[4, 6, 11, 3, 0, 1, 10, 8, 2, 5]
[4, 6, 11, 3, 0, 1, 10, 2, 8, 5]
[4, 6, 11, 3, 0, 1, 10, 2, 5, 8]
[4, 8, 6, 11, 0, 3, 1, 10, 2, 5]
[4, 6, 8, 11, 0, 3, 1, 10, 2, 5]
[4, 6, 11, 8, 0, 3, 1, 10, 2, 5]
[4, 6, 11, 0, 8, 3, 1, 10, 2, 5]
[4, 6, 11, 0, 3, 8, 1, 10, 2, 5]
[4, 6, 11, 0, 3, 1, 8, 10, 2, 5]
[4, 6, 11, 0, 3, 1, 10, 8, 2, 5]
[4, 6, 11, 0, 3, 1, 10, 2, 8, 5]
[4, 6, 11, 0, 3, 1, 10, 2, 5, 8]
[4, 8, 6, 11, 0, 1, 3, 10, 2, 5]
[4, 6, 8, 11, 0, 1, 3, 10, 2, 5]
[4, 6, 11, 8, 0, 1, 3, 10, 2, 5]
[4, 6, 11, 0, 8, 1, 3, 10, 2, 5]
[4, 6, 11, 0, 1, 8, 3, 10, 2, 5]
[4, 6, 11, 0, 1, 3, 8, 10, 2, 5]
[4, 6, 11, 0, 1, 3, 10, 8, 2, 5]
[4, 6, 11, 0, 1, 3, 10, 2, 8, 5]
[4, 6, 11, 0, 1, 3, 10, 2, 5, 8]
[4, 8, 6, 11, 0, 1, 10, 3, 2, 5]
[4, 6, 8, 11, 0, 1, 10, 3, 2, 5]
[4, 6, 11, 8, 0, 1, 10, 3, 2, 5]
[4, 6, 11, 0, 8, 1, 10, 3, 2, 5]
[4, 6, 11, 0, 1, 8, 10, 3, 2, 5]
[4, 6, 11, 0, 1, 10, 8, 3, 2, 5]
[4, 6, 11, 0, 1, 10, 3, 8, 2, 5]
[4, 6, 11, 0, 1, 10, 3, 2, 8, 5]
[4, 6, 11, 0, 1, 10, 3, 2, 5, 8]
[4, 8, 6, 11, 0, 1, 10, 2, 3, 5]
[4, 6, 8, 11, 0, 1, 10, 2, 3, 5]
[4, 6, 11, 8, 0, 1, 10, 2, 3, 5]
[4, 6, 11, 0, 8, 1, 10, 2, 3, 5]
[4, 6, 11, 0, 1, 8, 10, 2, 3, 5]
[4, 6, 11, 0, 1, 10, 8, 2, 3, 5]
[4, 6, 11, 0, 1, 10, 2, 8, 3, 5]
[4, 6, 11, 0, 1, 10, 2, 3, 8, 5]
[4, 6, 11, 0, 1, 10, 2, 3, 5, 8]
[4, 8, 6, 11, 0, 1, 10, 2, 5, 3]
[4, 6, 8, 11, 0, 1, 10, 2, 5, 3]
[4, 6, 11, 8, 0, 1, 10, 2, 5, 3]
[4, 6, 11, 0, 8, 1, 10, 2, 5, 3]
[4, 6, 11, 0, 1, 8, 10, 2, 5, 3]
[4, 6, 11, 0, 1, 10, 8, 2, 5, 3]
[4, 6, 11, 0, 1, 10, 2, 8, 5, 3]
[4, 6, 11, 0, 1, 10, 2, 5, 8, 3]
[4, 6, 11, 0, 1, 10, 2, 5, 3, 8]
[4, 8, 3, 6, 11, 0, 1, 2, 10, 5]
[4, 3, 8, 6, 11, 0, 1, 2, 10, 5]
[4, 3, 6, 8, 11, 0, 1, 2, 10, 5]
[4, 3, 6, 11, 8, 0, 1, 2, 10, 5]
[4, 3, 6, 11, 0, 8, 1, 2, 10, 5]
[4, 3, 6, 11, 0, 1, 8, 2, 10, 5]
[4, 3, 6, 11, 0, 1, 2, 8, 10, 5]
[4, 3, 6, 11, 0, 1, 2, 10, 8, 5]
[4, 3, 6, 11, 0, 1, 2, 10, 5, 8]
[4, 8, 6, 3, 11, 0, 1, 2, 10, 5]
[4, 6, 8, 3, 11, 0, 1, 2, 10, 5]
[4, 6, 3, 8, 11, 0, 1, 2, 10, 5]
[4, 6, 3, 11, 8, 0, 1, 2, 10, 5]
[4, 6, 3, 11, 0, 8, 1, 2, 10, 5]
[4, 6, 3, 11, 0, 1, 8, 2, 10, 5]
[4, 6, 3, 11, 0, 1, 2, 8, 10, 5]
[4, 6, 3, 11, 0, 1, 2, 10, 8, 5]
[4, 6, 3, 11, 0, 1, 2, 10, 5, 8]
[4, 8, 6, 11, 3, 0, 1, 2, 10, 5]
[4, 6, 8, 11, 3, 0, 1, 2, 10, 5]
[4, 6, 11, 8, 3, 0, 1, 2, 10, 5]
[4, 6, 11, 3, 8, 0, 1, 2, 10, 5]
[4, 6, 11, 3, 0, 8, 1, 2, 10, 5]
[4, 6, 11, 3, 0, 1, 8, 2, 10, 5]
[4, 6, 11, 3, 0, 1, 2, 8, 10, 5]
[4, 6, 11, 3, 0, 1, 2, 10, 8, 5]
[4, 6, 11, 3, 0, 1, 2, 10, 5, 8]
[4, 8, 6, 11, 0, 3, 1, 2, 10, 5]
[4, 6, 8, 11, 0, 3, 1, 2, 10, 5]
[4, 6, 11, 8, 0, 3, 1, 2, 10, 5]
[4, 6, 11, 0, 8, 3, 1, 2, 10, 5]
[4, 6, 11, 0, 3, 8, 1, 2, 10, 5]
[4, 6, 11, 0, 3, 1, 8, 2, 10, 5]
[4, 6, 11, 0, 3, 1, 2, 8, 10, 5]
[4, 6, 11, 0, 3, 1, 2, 10, 8, 5]
[4, 6, 11, 0, 3, 1, 2, 10, 5, 8]
[4, 8, 6, 11, 0, 1, 3, 2, 10, 5]
[4, 6, 8, 11, 0, 1, 3, 2, 10, 5]
[4, 6, 11, 8, 0, 1, 3, 2, 10, 5]
[4, 6, 11, 0, 8, 1, 3, 2, 10, 5]
[4, 6, 11, 0, 1, 8, 3, 2, 10, 5]
[4, 6, 11, 0, 1, 3, 8, 2, 10, 5]
[4, 6, 11, 0, 1, 3, 2, 8, 10, 5]
[4, 6, 11, 0, 1, 3, 2, 10, 8, 5]
[4, 6, 11, 0, 1, 3, 2, 10, 5, 8]
[4, 8, 6, 11, 0, 1, 2, 3, 10, 5]
[4, 6, 8, 11, 0, 1, 2, 3, 10, 5]
[4, 6, 11, 8, 0, 1, 2, 3, 10, 5]
[4, 6, 11, 0, 8, 1, 2, 3, 10, 5]
[4, 6, 11, 0, 1, 8, 2, 3, 10, 5]
[4, 6, 11, 0, 1, 2, 8, 3, 10, 5]
[4, 6, 11, 0, 1, 2, 3, 8, 10, 5]
[4, 6, 11, 0, 1, 2, 3, 10, 8, 5]
[4, 6, 11, 0, 1, 2, 3, 10, 5, 8]
[4, 8, 6, 11, 0, 1, 2, 10, 3, 5]
[4, 6, 8, 11, 0, 1, 2, 10, 3, 5]
[4, 6, 11, 8, 0, 1, 2, 10, 3, 5]
[4, 6, 11, 0, 8, 1, 2, 10, 3, 5]
[4, 6, 11, 0, 1, 8, 2, 10, 3, 5]
[4, 6, 11, 0, 1, 2, 8, 10, 3, 5]
[4, 6, 11, 0, 1, 2, 10, 8, 3, 5]
[4, 6, 11, 0, 1, 2, 10, 3, 8, 5]
[4, 6, 11, 0, 1, 2, 10, 3, 5, 8]
[4, 8, 6, 11, 0, 1, 2, 10, 5, 3]
[4, 6, 8, 11, 0, 1, 2, 10, 5, 3]
[4, 6, 11, 8, 0, 1, 2, 10, 5, 3]
[4, 6, 11, 0, 8, 1, 2, 10, 5, 3]
[4, 6, 11, 0, 1, 8, 2, 10, 5, 3]
[4, 6, 11, 0, 1, 2, 8, 10, 5, 3]
[4, 6, 11, 0, 1, 2, 10, 8, 5, 3]
[4, 6, 11, 0, 1, 2, 10, 5, 8, 3]
[4, 6, 11, 0, 1, 2, 10, 5, 3, 8]
[4, 8, 3, 6, 11, 0, 1, 2, 5, 10]
[4, 3, 8, 6, 11, 0, 1, 2, 5, 10]
[4, 3, 6, 8, 11, 0, 1, 2, 5, 10]
[4, 3, 6, 11, 8, 0, 1, 2, 5, 10]
[4, 3, 6, 11, 0, 8, 1, 2, 5, 10]
[4, 3, 6, 11, 0, 1, 8, 2, 5, 10]
[4, 3, 6, 11, 0, 1, 2, 8, 5, 10]
[4, 3, 6, 11, 0, 1, 2, 5, 8, 10]
[4, 3, 6, 11, 0, 1, 2, 5, 10, 8]
[4, 8, 6, 3, 11, 0, 1, 2, 5, 10]
[4, 6, 8, 3, 11, 0, 1, 2, 5, 10]
[4, 6, 3, 8, 11, 0, 1, 2, 5, 10]
[4, 6, 3, 11, 8, 0, 1, 2, 5, 10]
[4, 6, 3, 11, 0, 8, 1, 2, 5, 10]
[4, 6, 3, 11, 0, 1, 8, 2, 5, 10]
[4, 6, 3, 11, 0, 1, 2, 8, 5, 10]
[4, 6, 3, 11, 0, 1, 2, 5, 8, 10]
[4, 6, 3, 11, 0, 1, 2, 5, 10, 8]
[4, 8, 6, 11, 3, 0, 1, 2, 5, 10]
[4, 6, 8, 11, 3, 0, 1, 2, 5, 10]
[4, 6, 11, 8, 3, 0, 1, 2, 5, 10]
[4, 6, 11, 3, 8, 0, 1, 2, 5, 10]
[4, 6, 11, 3, 0, 8, 1, 2, 5, 10]
[4, 6, 11, 3, 0, 1, 8, 2, 5, 10]
[4, 6, 11, 3, 0, 1, 2, 8, 5, 10]
[4, 6, 11, 3, 0, 1, 2, 5, 8, 10]
[4, 6, 11, 3, 0, 1, 2, 5, 10, 8]
[4, 8, 6, 11, 0, 3, 1, 2, 5, 10]
[4, 6, 8, 11, 0, 3, 1, 2, 5, 10]
[4, 6, 11, 8, 0, 3, 1, 2, 5, 10]
[4, 6, 11, 0, 8, 3, 1, 2, 5, 10]
[4, 6, 11, 0, 3, 8, 1, 2, 5, 10]
[4, 6, 11, 0, 3, 1, 8, 2, 5, 10]
[4, 6, 11, 0, 3, 1, 2, 8, 5, 10]
[4, 6, 11, 0, 3, 1, 2, 5, 8, 10]
[4, 6, 11, 0, 3, 1, 2, 5, 10, 8]
[4, 8, 6, 11, 0, 1, 3, 2, 5, 10]
[4, 6, 8, 11, 0, 1, 3, 2, 5, 10]
[4, 6, 11, 8, 0, 1, 3, 2, 5, 10]
[4, 6, 11, 0, 8, 1, 3, 2, 5, 10]
[4, 6, 11, 0, 1, 8, 3, 2, 5, 10]
[4, 6, 11, 0, 1, 3, 8, 2, 5, 10]
[4, 6, 11, 0, 1, 3, 2, 8, 5, 10]
[4, 6, 11, 0, 1, 3, 2, 5, 8, 10]
[4, 6, 11, 0, 1, 3, 2, 5, 10, 8]
[4, 8, 6, 11, 0, 1, 2, 3, 5, 10]
[4, 6, 8, 11, 0, 1, 2, 3, 5, 10]
[4, 6, 11, 8, 0, 1, 2, 3, 5, 10]
[4, 6, 11, 0, 8, 1, 2, 3, 5, 10]
[4, 6, 11, 0, 1, 8, 2, 3, 5, 10]
[4, 6, 11, 0, 1, 2, 8, 3, 5, 10]
[4, 6, 11, 0, 1, 2, 3, 8, 5, 10]
[4, 6, 11, 0, 1, 2, 3, 5, 8, 10]
[4, 6, 11, 0, 1, 2, 3, 5, 10, 8]
[4, 8, 6, 11, 0, 1, 2, 5, 3, 10]
[4, 6, 8, 11, 0, 1, 2, 5, 3, 10]
[4, 6, 11, 8, 0, 1, 2, 5, 3, 10]
[4, 6, 11, 0, 8, 1, 2, 5, 3, 10]
[4, 6, 11, 0, 1, 8, 2, 5, 3, 10]
[4, 6, 11, 0, 1, 2, 8, 5, 3, 10]
[4, 6, 11, 0, 1, 2, 5, 8, 3, 10]
[4, 6, 11, 0, 1, 2, 5, 3, 8, 10]
[4, 6, 11, 0, 1, 2, 5, 3, 10, 8]
[4, 8, 6, 11, 0, 1, 2, 5, 10, 3]
[4, 6, 8, 11, 0, 1, 2, 5, 10, 3]
[4, 6, 11, 8, 0, 1, 2, 5, 10, 3]
[4, 6, 11, 0, 8, 1, 2, 5, 10, 3]
[4, 6, 11, 0, 1, 8, 2, 5, 10, 3]
[4, 6, 11, 0, 1, 2, 8, 5, 10, 3]
[4, 6, 11, 0, 1, 2, 5, 8, 10, 3]
[4, 6, 11, 0, 1, 2, 5, 10, 8, 3]
[4, 6, 11, 0, 1, 2, 5, 10, 3, 8]

Answer 2

I also only get 504 elements after accounting for duplicates but the below does it efficiently without storing anything:

from itertools import permutations

def generate_binary_numbers(n, k):
    # yields all binary numbers of bit-length n with exactly k bits set to one
    if k == 0:
        yield [0] * n  # Base case: All zeros
    elif k == n:
        yield [1] * n  # Base case: All ones
    else:
        for num in generate_binary_numbers(n - 1, k - 1):
            yield [1] + num
        for num in generate_binary_numbers(n - 1, k):
            yield [0] + num


def insertion_pattern(lst1, lst2):
    for binary_num in generate_binary_numbers(len(lst1 )+ len(lst2)-1  , len(lst2)):
        yield [0] + binary_num # 0 is never a valid insertion place
        
def all_valid_samples(lst1, lst2):
    for pattern in insertion_pattern(lst1, lst2):
        for permutation in permutations(lst2):
            result = []
            j=0
            k=0
            for i in range(len(lst1)+len(lst2)):
                if pattern[i]==1:
                    # Choose from the permutation if it's a 1
                    result.append(permutation[j])       
                    j+=1
                else:
                    # Choose from list 1 if it's a 0
                    result.append(lst1[k])
                    k+=1
            yield tuple(result)

Example usage

lst1 = [4, 6, 11, 0, 1, 2, 5]
lst2 = [10, 3, 8]
print(len(set(all_valid_samples(lst1,lst2))))

Output:

504

Answer 3

While not winning any races, I believe this code will give you your list.

import itertools

## ------------------------
## per: https://stackoverflow.com/questions/15415237/in-python-efficiently-determine-if-two-lists-are-shifted-copies-of-one-another
## ------------------------
def is_shifted_copy(l1, l2):
    l1l1 = l1 * 2
    n = len(l1)
    return next((i for i in range(n) if l1l1[i:i + n] == l2), None) is not None
## ------------------------

lst1 = ["1","2"]
lst2 = ["a","b"]
lst3 = lst1 + lst2
results = []
for candidate in itertools.permutations(lst3, len(lst3)):
    ## -----------------
    ## reject candidate if not in acceptable order
    ## -----------------
    test_indexes = [candidate.index(i) for i in lst1]
    if test_indexes != sorted(test_indexes):
        continue
    ## -----------------

    ## -----------------
    ## reject candidate if it is a rotation of an existing candidate
    ## -----------------
    if any(is_shifted_copy(candidate, existing) for existing in results):
        continue
    ## -----------------

    results.append(candidate)

for result in results:
    print(result)

This will give you:

('1', '2', 'a', 'b')
('1', '2', 'b', 'a')
('1', 'a', '2', 'b')
('1', 'a', 'b', '2')
('1', 'b', '2', 'a')
('1', 'b', 'a', '2')

With:

lst1 = [4, 6, 11, 0, 1, 2, 5] 
lst2 =  [10, 3, 8]

The length of the result is 504 items.

Answer 4

One way: for each configuration of "insert a lst2 item" locations, use a defaultdict that, for a location, gives either the relevant lst2 item, or by default the next element of lst1.

import itertools as it
from collections import defaultdict

lst1 = [4, 6, 11, 0, 1, 2, 5]
lst2 = [10, 3, 8]

total_len = len(lst1) + len(lst2)
results = []

for locations in it.permutations(range(1, total_len), len(lst2)):
    # Note, it's range(1, total_len). Because of the circularity of the result,
    # we can stipulate without loss of generality that element 0 of the result
    # is lst1[0], and avoid generating "distinct" results that differ only
    # modulo a rotation. So 0 isn't an eligible index for placing a lst2 item.
    it1 = iter(lst1)
    item_at_position = defaultdict(lambda: next(it1),
                                    zip(locations, lst2))
    perm = [item_at_position[i] for i in range(total_len)]
    results.append(perm)
    print(perm)

print(len(results))

For the given inputs, this gives 504 results (equal to (x+n-1)!/ (x-1)! with x=7, n=3).

For example, [4, 10, 3, 6, 11, 0, 8, 1, 2, 5] appears as a member of the results list, so [10, 3, 6, 11, 0, 8, 1, 2, 5, 4] does not also appear: that's simply a different way of representing the same circular list, by choosing a different arbitrary starting point to write it from.

For lst1 = [4, 6, 11] and lst2 = [10, 3, 8], it gives 60 results.

Answer 5

First generate all possible combinations of insertion locations. Need combination with replacement since we can repeatedly insert at the same index. Then zip it with all permutations of lst2. Since the combinations are always sorted, we can adjust for the changing result length by keeping track of elements inserted.

import itertools as it

lst1 = [4, 6, 11, 0, 1, 2, 5]
lst2 = [10, 3, 8]

insertion_locations = it.combinations_with_replacement(range(len(lst1) + 1), len(lst2))

l2_perms = list(it.permutations(lst2, len(lst2)))

results = []

for il in insertion_locations:
    for perm in l2_perms:
        result = lst1.copy()
        inserted = 0

        for index, val in zip(il, perm):
            result.insert(index + inserted, val)
            inserted += 1

        results.append(result)
        print(result)