Shuffling list, but keeping some elements frozen

Question

I've such a problem:

There is a list of elements of class CAnswer (no need to describe the class), and I need to shuffle it, but with one constraint - some elements of the list have CAnswer.freeze set to True, and those elements must not be shuffled, but remain on their original positions. So, let's say, for a given list:

[a, b, c, d, e, f]

Where all elements are instances of CAnswer, but c.freeze == True, and for others freeze == False, the possible outcome could be:

[e, a, c, f, b, d]

So element with index 2 is still on its position.

What is the best algorithm to achieve it?

Thank you in advance :)

Answer 1

Use the fact that a list has fast remove and insert:

• enumerate fixed elements and copy them and their index
• delete fixed elements from list
• shuffle remaining sub-set
• put fixed elements back in

See https://stackoverflow.com/a/25233037/3449962 for a more general solution.

This will use in-place operations with memory overhead that depends on the number of fixed elements in the list. Linear in time. A possible implementation of shuffle_subset:

#!/usr/bin/env python
"""Shuffle elements in a list, except for a sub-set of the elments.

The sub-set are those elements that should retain their position in
the list.  Some example usage:

>>> from collections import namedtuple
>>> class CAnswer(namedtuple("CAnswer","x fixed")):
...             def __bool__(self):
...                     return self.fixed is True
...             __nonzero__ = __bool__  # For Python 2. Called by bool in Py2.
...             def __repr__(self):
...                     return "<CA: {}>".format(self.x)
...
>>> val = [3, 2, 0, 1, 5, 9, 4]
>>> fix = [2, 5]
>>> lst = [ CAnswer(v, i in fix) for i, v in enumerate(val)]

>>> print("Start   ", 0, ": ", lst)
Start    0 :  [<CA: 3>, <CA: 2>, <CA: 0>, <CA: 1>, <CA: 5>, <CA: 9>, <CA: 4>]

Using a predicate to filter.

>>> for i in range(4):  # doctest: +NORMALIZE_WHITESPACE
...     shuffle_subset(lst, lambda x : x.fixed)
...     print([lst[i] for i in fix], end=" ")
...
[<CA: 0>, <CA: 9>] [<CA: 0>, <CA: 9>] [<CA: 0>, <CA: 9>] [<CA: 0>, <CA: 9>]

>>> for i in range(4):                # doctest: +NORMALIZE_WHITESPACE
...     shuffle_subset(lst)           # predicate = bool()
...     print([lst[i] for i in fix], end=" ")
...
[<CA: 0>, <CA: 9>] [<CA: 0>, <CA: 9>] [<CA: 0>, <CA: 9>] [<CA: 0>, <CA: 9>]

"""
from __future__ import print_function
import random


def shuffle_subset(lst, predicate=None):
    """All elements in lst, except a sub-set, are shuffled.

    The predicate defines the sub-set of elements in lst that should
    not be shuffled:

      + The predicate is a callable that returns True for fixed
      elements, predicate(element) --> True or False.

      + If the predicate is None extract those elements where
      bool(element) == True.

    """
    predicate = bool if predicate is None else predicate
    fixed_subset = [(i, e) for i, e in enumerate(lst) if predicate(e)]

    fixed_subset.reverse()      # Delete fixed elements from high index to low.
    for i, _ in fixed_subset:
        del lst[i]

    random.shuffle(lst)

    fixed_subset.reverse()      # Insert fixed elements from low index to high.
    for i, e in fixed_subset:
        lst.insert(i, e)

if __name__ == "__main__":
    import doctest
    doctest.testmod()

Answer 2

One solution:

def fixed_shuffle(lst):
    unfrozen_indices, unfrozen_subset = zip(*[(i, e) for i, e in enumerate(lst)
                                            if not e.freeze])
    unfrozen_indices = list(unfrozen_indices)
    random.shuffle(unfrozen_indices)
    for i, e in zip(unfrozen_indices, unfrozen_subset):
        lst[i] = e

NOTE: If lst is a numpy array instead of a regular list, this can be a bit simpler:

def fixed_shuffle_numpy(lst):
    unfrozen_indices = [i for i, e in enumerate(lst) if not e.freeze]
    unfrozen_set = lst[unfrozen_indices]
    random.shuffle(unfrozen_set)
    lst[unfrozen_indices] = unfrozen_set

An example of its usage:

class CAnswer:
    def __init__(self, x, freeze=False):
        self.x = x
        self.freeze = freeze

    def __cmp__(self, other):
        return self.x.__cmp__(other.x)

    def __repr__(self):
        return "<CAnswer: %s>" % self.x


lst = [CAnswer(3), CAnswer(2), CAnswer(0, True), CAnswer(1), CAnswer(5),
       CAnswer(9, True), CAnswer(4)]

fixed_shuffle(lst)

Answer 3

Overengineered solution: create a wrapper class that contains indexes of the unfreezed elements and emulates a list, and make sure the setter writes to the original list:

class IndexedFilterList:
    def __init__(self, originalList, filterFunc):
        self.originalList = originalList
        self.indexes = [i for i, x in enumerate(originalList) if filterFunc(x)]

    def __len__(self):
        return len(self.indexes)

    def __getitem__(self, i):
        return self.originalList[self.indexes[i]]

    def __setitem__(self, i, value):
        self.originalList[self.indexes[i]] = value

And call:

random.shuffle(IndexedFilterList(mylist, lambda c: not c.freeze))

Answer 4

In linear time, constant space using random.shuffle() source:

from random import random

def shuffle_with_freeze(x):
    for i in reversed(xrange(1, len(x))):
        if x[i].freeze: continue # fixed
        # pick an element in x[:i+1] with which to exchange x[i]
        j = int(random() * (i+1))
        if x[j].freeze: continue #NOTE: it might make it less random
        x[i], x[j] = x[j], x[i] # swap

Answer 5

Another solution:

# memorize position of fixed elements
fixed = [(pos, item) for (pos,item) in enumerate(items) if item.freeze]
# shuffle list
random.shuffle(items)
# swap fixed elements back to their original position
for pos, item in fixed:
    index = items.index(item)
    items[pos], items[index] = items[index], items[pos]