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!
CodePudding user response：
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.
CodePudding user response：
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)]