CODEWITHSUNDEEP
pythonalgorithmlistsorting
Woooooooooooooow
Woooooooooooooow

Reputation: 191

Randomly move a certain number of items in a Python list

So I've been doing some sorting algorithms and I want to run a test function that generates lists of different varieties to run my sorting algorithms on.

One such list would be an already sorted list, where n number of the items in the list have been shuffled around randomly (but not all of them, the list should still be sorted other than the n items)

testlist = random.sample(range(0,10),10)
testlist.sort()

This gives me a sorted list of unique items of size 10, but then I'm unsure how to go about moving n of these 10 items around the list to a random location, just to mix the sorting up

Upvotes: 9

Views: 2137

Answers (3)

Brendan Abel
Brendan Abel

Reputation: 37509

Something like this would work. Basically, just pick two indexes at random and switch them, and not switching the same index more than once. If run on a sorted array, it does guarantee that exactly n elements are unsorted. Only works on even number replacements though.

array = list(range(10))

def shuffle_n(array, n):
    assert n <= len(array) and n % 2 == 0
    indexes = set(range(len(array)))
    for i in range(n // 2):
        a, b = random.sample(indexes, 2)
        indexes.remove(a)
        indexes.remove(b)
        array[a], array[b] = array[b], array[a]

Upvotes: 2

Prune
Prune

Reputation: 77837

Here's a controlled implementation. Pick four indices at random to get switched. Shuffle those values, and put them back into the four designated spots. Note that it does not guarantee that the new values will all be different.

import random
import copy

testlist = random.sample(range(0, 20), 10)
testlist.sort()
print testlist

n = 4
move_set = set()
while len(move_set) < n:
    move_set.add(random.randrange(0, 10))

print move_set
move_list = list(move_set)

# Replace n elements
test1 = copy.copy(testlist)
migrant = [test1[_] for _ in move_set]
random.shuffle(migrant)
print migrant
test_case = []
for i in range(n):
    test1[move_list[i]] = migrant[i]
print test1

Output:

[0, 3, 4, 5, 7, 8, 9, 12, 16, 17]
set([9, 3, 4, 5])
[5, 17, 8, 7]
[0, 3, 4, 17, 8, 7, 9, 12, 16, 5]

In this run, it's only coincidence that all four indices were also values in the list. Elements 9, 3, 4, and 5 have values 17, 5, 7, and 8, respectively. The shuffle puts each of the four into new locations.

Upvotes: 3

Matt Hall
Matt Hall

Reputation: 8122

Here's one way to shuffle some items in the list:

import random
import numpy as np

# Make a sorted list of integers.
x = np.array(range(100))

# Choose 10 indices at random.
r = random.sample(range(len(x)), 10)

# Copy this list and shuffle.
s = r.copy()
random.shuffle(s)

# Replace the indices with the shuffled ones.
x[r] = x[s]

Note this might leave some indices unchanged.

Upvotes: 5

Related Questions