Swap Items in an Array
Swap Two Variables
In Python, swapping two variables is a one-liner: a, b = b, a.
In languages such as Java, swapping requires the use of a temporary variable:
java temp = a; a = b; b = temp;
If we know the two variables are integers, can we swap them without using a temporary variable?
python
a, b = 5, 20 a ^= b b ^= a a ^= b a, b (20, 5)
It’s a fun little exercise to convince yourself that the above procedure indeed works. Keep in mind that the XOR operator is commutative and that x ^ x = 0.
Another way is to use the plus and minus operators:
python
a, b = 5, 20 a = a + b b = a - b a = a - b a, b (20, 5)
Note that the above two procedures only work when a and b are integers.
Swap Two Items in an Array
Given a list L and two indices i and j, we can swap the L[i] and L[j] in one-line: L[i], L[j] = L[j], L[i].
Shuffle an Array
Given an array, write a program to generate a random permutation of array elements.
The Fisher–Yates shuffle is a well-known algorithm to solve this problem. In pseudocode, the algorithm works as follows
for i from n−1 down to 1 do
j ← random integer such that 0 ≤ j ≤ i
swap a[j] and a[i]
Here’s the Python implementation:
python import random
def shuffle_list(L): for i in range(len(L) - 1, 0, -1): j = random.randint(0, i) L[i], L[j] = L[j], L[i]
Note that random.randint(a, b) returns a random integer n such that a <= n <= b.
Let’s see the function in action:
python
L = list(range(10)) shuffle_list(L); L [4, 8, 3, 0, 7, 6, 5, 9, 2, 1] shuffle_list(L); L [3, 5, 6, 0, 7, 8, 4, 2, 1, 9] shuffle_list(L); L [0, 7, 8, 4, 1, 2, 5, 3, 9, 6]