Python: How to efficiently create all possible 2 element swaps of an array?

Question

I try to generate all possible 2-element swaps of a given array.

For example:

candidate = [ 5, 9, 1, 8, 3, 7, 10, 6, 4, 2]

result = [[ 9,  5,  1,  8,  3,  7, 10,  6,  4,  2]
[ 1,  9,  5,  8,  3,  7, 10,  6,  4,  2]
[ 8,  9,  1,  5,  3,  7, 10,  6,  4,  2]
[ 3,  9,  1,  8,  5,  7, 10,  6,  4,  2]
[ 7,  9,  1,  8,  3,  5, 10,  6,  4,  2]
[10,  9,  1,  8,  3,  7,  5,  6,  4,  2]
[ 6,  9,  1,  8,  3,  7, 10,  5,  4,  2]
[ 4,  9,  1,  8,  3,  7, 10,  6,  5,  2]
[ 2,  9,  1,  8,  3,  7, 10,  6,  4,  5]
[ 5,  1,  9,  8,  3,  7, 10,  6,  4,  2]
[ 5,  8,  1,  9,  3,  7, 10,  6,  4,  2]
[ 5,  3,  1,  8,  9,  7, 10,  6,  4,  2]
[ 5,  7,  1,  8,  3,  9, 10,  6,  4,  2]
[ 5, 10,  1,  8,  3,  7,  9,  6,  4,  2]
[ 5,  6,  1,  8,  3,  7, 10,  9,  4,  2]
[ 5,  4,  1,  8,  3,  7, 10,  6,  9,  2]
[ 5,  2,  1,  8,  3,  7, 10,  6,  4,  9]
[ 5,  9,  8,  1,  3,  7, 10,  6,  4,  2]
[ 5,  9,  3,  8,  1,  7, 10,  6,  4,  2]
[ 5,  9,  7,  8,  3,  1, 10,  6,  4,  2]
[ 5,  9, 10,  8,  3,  7,  1,  6,  4,  2]
[ 5,  9,  6,  8,  3,  7, 10,  1,  4,  2]
[ 5,  9,  4,  8,  3,  7, 10,  6,  1,  2]
[ 5,  9,  2,  8,  3,  7, 10,  6,  4,  1]
[ 5,  9,  1,  3,  8,  7, 10,  6,  4,  2]
[ 5,  9,  1,  7,  3,  8, 10,  6,  4,  2]
[ 5,  9,  1, 10,  3,  7,  8,  6,  4,  2]
[ 5,  9,  1,  6,  3,  7, 10,  8,  4,  2]
[ 5,  9,  1,  4,  3,  7, 10,  6,  8,  2]
[ 5,  9,  1,  2,  3,  7, 10,  6,  4,  8]
[ 5,  9,  1,  8,  7,  3, 10,  6,  4,  2]
[ 5,  9,  1,  8, 10,  7,  3,  6,  4,  2]
[ 5,  9,  1,  8,  6,  7, 10,  3,  4,  2]
[ 5,  9,  1,  8,  4,  7, 10,  6,  3,  2]
[ 5,  9,  1,  8,  2,  7, 10,  6,  4,  3]
[ 5,  9,  1,  8,  3, 10,  7,  6,  4,  2]
[ 5,  9,  1,  8,  3,  6, 10,  7,  4,  2]
[ 5,  9,  1,  8,  3,  4, 10,  6,  7,  2]
[ 5,  9,  1,  8,  3,  2, 10,  6,  4,  7]
[ 5,  9,  1,  8,  3,  7,  6, 10,  4,  2]
[ 5,  9,  1,  8,  3,  7,  4,  6, 10,  2]
[ 5,  9,  1,  8,  3,  7,  2,  6,  4, 10]
[ 5,  9,  1,  8,  3,  7, 10,  4,  6,  2]
[ 5,  9,  1,  8,  3,  7, 10,  2,  4,  6]
[ 5,  9,  1,  8,  3,  7, 10,  6,  2,  4]]

I currently achive this by using two nested for-loops:

    neighborhood = []
    for node1 in range(candidate.size - 1):
        for node2 in range(node1 + 1, candidate.size):
            neighbor = np.copy(candidate)
            neighbor[node1] = candidate[node2]
            neighbor[node2] = candidate[node1]
            neighborhood.append(neighbor)

The larger the array gets, the more inefficient and slower it becomes. Is there a more efficient way here that can also process arrays with three-digit contents?

Thank you!

@FranArenas In my opinion it doesn't. I don't need all possible combinations, just those that are one swap of two elements away. — No110, Aug 31 '22 at 08:28
Do you need all the lists at once, or are you going to look at them one by one? — Riccardo Bucco, Aug 31 '22 at 08:28

Riccardo Bucco · Accepted Answer · 2022-08-31T09:54:42.647

You can use a generator if you need to use those arrays one by one (in this way, you don't need to memorize them all, you need very little space):

from itertools import combinations

def gen(lst):
    for i, j in combinations(range(len(lst)), 2):
        yield lst[:i] + lst[j] + lst[i:j] + lst[i] + lst[j:]

And then you can use it in this way:

for lst in gen(candidate):
    # do something with your list with two swapped elements

This is going to save much space, but it's probably going to be still slow overall.

Here is a solution using NumPy. This is not space efficient (because it's memorizing all possible lists with swapped elements), but it might be much faster because of NumPy optimizations. Give it a try!

from itertools import combinations
from math import comb

arr = np.tile(candidate, (comb(len(candidate), 2), 1))
indices = np.array(list(combinations(range(len(candidate)), 2)))
arr[np.arange(arr.shape[0])[:, None], indices] = arr[np.arange(arr.shape[0])[:, None], np.flip(indices, axis=-1)]

Example (with candidate = [0, 1, 2, 3]):

>>> arr
array([[1, 0, 2, 3],
       [2, 1, 0, 3],
       [3, 1, 2, 0],
       [0, 2, 1, 3],
       [0, 3, 2, 1],
       [0, 1, 3, 2]])

Notice that math.comb (which gives you the total number of possible lists with 2 swapped elements) is available only with python >= 3.8. Please have a look at this question to know how to replace math.comb in case you're using an older python version.

Looks like I should have refreshed before posting. Good answer. — theherk, Aug 31 '22 at 08:43
@theherk Thank you both for the answers. Those are much more elegant ways. To be honest time efficiency is my main problem, so if you have an idea in that direction that would be awesome. — No110, Aug 31 '22 at 08:55
@No110 Please have a look at the numpy solution, and let me know if this is now sufficiently efficient. — Riccardo Bucco, Aug 31 '22 at 09:55
@RiccardoBucco Both ideas are more time efficient than the loops and I could measure slightly better performance of the numpy implementation. It takes about 1 min for arrays with around 50 elements. Unfortunatly that adds up in my implementation case. — No110, Sep 01 '22 at 11:54

theherk · Answer 2 · 2022-08-31T08:47:12.857

To swap only two items in any given list, I'd recommend using range with itertools.combinations. It is probably good to use a generator with the yield statement too, though if you are getting all results at once, it probably doesn't matter much.

from itertools import combinations


def swap2(l):
    for pair in combinations(range(len(l)), 2):
        l2 = l[:]
        l2[pair[0]], l2[pair[1]] = l2[pair[1]], l2[pair[0]]
        yield l2


if __name__ == "__main__":
    candidate = [5, 9, 1, 8, 3, 7, 10, 6, 4, 2]
    result = [l for l in swap2(candidate)]

Python: How to efficiently create all possible 2 element swaps of an array?

2 Answers2