Faster element rolled permutation swaping between two lists

user_266068 0
Viewed 57

I have two lists, X and Y.
X = [1,2,3] and Y = ['A','B','C']

I would like to take all combinations of two, from list A and place it in a second list in any position.
From the original second list I would like to take all elements one by one and place it in list X in any position.

The outcome should look like this:

# Original lists: (X = [1,2,3], Y = ['A','B','C'])

[
 ([1, 'A'], ['B', 'C', 2, 3]),  # 2,3 went to list (Y) and 'A' went to list (X)
 ([1, 'B'], ['A', 'C', 2, 3]),  # 2,3 went to list (Y) and 'B' went to list (X)
 ([1, 'C'], ['A', 'B', 2, 3]),  # 2,3 went to list (Y) and 'C' went to list (X)
 ([2, 'A'], ['B', 'C', 1, 3]),  # 1,3 went to list (Y) and 'A' went to list (X)
 ([2, 'B'], ['A', 'C', 1, 3]),  # 1,3 went to list (Y) and 'B' went to list (X)
 ([2, 'C'], ['A', 'B', 1, 3]),  # 1,3 went to list (Y) and 'C' went to list (X)
 ([3, 'A'], ['B', 'C', 1, 2]),  # 1,2 went to list (Y) and 'A' went to list (X)
 ([3, 'B'], ['A', 'C', 1, 2]),  # 1,2 went to list (Y) and 'B' went to list (X)
 ([3, 'C'], ['A', 'B', 1, 2])   # 1,2 went to list (Y) and 'C' went to list (X)
]

My implementation looks like this:

def itwo(l1,l2):
    ln2 = l2[:]
    final = []
    z = list(it.combinations(l1, 2))
    for i in range(len(z)):
        ln1 = [ elem for elem in l1 if elem not in list(z[i])] 
        ln2 = l2 + list(z[i])
        for y in range(len(l2)):
            ln1.append(l2[y])
            ln2.remove(l2[y])
            final.append((ln1, ln2))    
            ln2 = l2 + list(z[i])
            ln1 = [ elem for elem in l1 if elem not in list(z[i])]
    return(final)

If X has 100 elements and Y ten, e.g. A = [1, 2, ...., 100]
and B = [A, B, C, D, E, F, G, H, I, J] the performance in my PC is: 

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    49500    0.910    0.000    0.910    0.000 C:\...\test.py:25(<listcomp>)
     4950    0.086    0.000    0.086    0.000 C:\...\test.py:18(<listcomp>)
        1    0.040    0.040    1.049    1.049 C:\...\test.py:13(itwo)
    99000    0.006    0.000    0.006    0.000 {method 'append' of 'list' objects}
    49500    0.006    0.000    0.006    0.000 {method 'remove' of 'list' objects}
     4951    0.000    0.000    0.000    0.000 {built-in method builtins.len}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}


         207903 function calls in 1.049 seconds

I was wondering if it can go faster using another approach.

list algorithm python
2 Answers

It seems like you should be able to do this with itertools.product and set functions to remove the nested loops:

import itertools as it

X = range(100)
Y = ['A','B','C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']

def itwo_s(l1,l2):
    s1 = set(l1)
    s2 = set(l2)
    
    for l in it.product(l1, l2):
        yield [list(l), [*s2.difference(l), *s1.difference(l)]]


list(itwo_s(X, Y))

timing:

# original:
%timeit itwo(X, Y)
# 1.55 s ± 13.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

# code above:
%timeit list(itwo_s(X, Y))
# 2.97 ms ± 179 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Because you are depending on sets, you do loose ordering on the sublists in exchange of the speed. Not sure if this is important.

user_38746230

you can simplify it a bit by understanding exactly the transform rules (which arguably i dont quite ... but i think this answers your question...

X = [1,2,3]; Y = ['A','B','C']
import itertools
def itwo(l1,l2):
    list_left = list(itertools.product(l1,l2))
    list_right1 = list(itertools.combinations(l1,2))
    list_right2 = list(itertools.combinations(l2,2))
    list_right = [y+x for x,y in itertools.product(list_right1,list_right2)]
    return list(zip(list_left,list_right))
    



itwo(X,Y)

which outputs

[
    ((1, 'A'), ('A', 'B', 1, 2)), 
    ((1, 'B'), ('A', 'C', 1, 2)), 
    ((1, 'C'), ('B', 'C', 1, 2)), 
    ((2, 'A'), ('A', 'B', 1, 3)), 
    ((2, 'B'), ('A', 'C', 1, 3)), 
    ((2, 'C'), ('B', 'C', 1, 3)), 
    ((3, 'A'), ('A', 'B', 2, 3)), 
    ((3, 'B'), ('A', 'C', 2, 3)), 
    ((3, 'C'), ('B', 'C', 2, 3))
]

the key is taking advantage of the builtin itertools, product to combine all combinations of 2 lists, and combinations, to return combinations of 1 list of length n

using your example of X = 1..100 and Y = A .. J my computer took 0.07 seconds (assuming I understood the requirements and the output is right the length is 1,000 elements)

[EDIT] upon further reflection i think that the rules for your second set of lists matches the other anwser better ... I will leave this in case its helpful to someone ... but i think the other answer is right and i misunderstood something

user_5410380
Related