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

user_8498461 0
Viewed 72

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!

swap python-3.x arrays python
2 Answers

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.

user_52961060

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)]
user_20818350
Related