Random permutation with defined order of last occurrences This Python function takes two arguments:


chr_list which is a mutable sequence of characters c
chr_counts which maps to each character c the number of occurrences n


For each character c in chr_list, it inserts this character into the list before its last occurrence n-1 times, where n equals chr_counts[c]. The resulting list contains chr_counts[c] occurrences of each character c, and the order of last occurrences is preserved.

def insert_repetitions_before(chr_list, chr_counts):

  for c, num_occurences in chr_counts.items():
    num_repeats = num_occurences - 1
    orig_pos_last = chr_list.index(c)

    for curr_pos_last in range(orig_pos_last, orig_pos_last+num_repeats):
      random_pos_before_last = random.randint(0, curr_pos_last)
      chr_list.insert(random_pos_before_last, c)


Example output:

chr_list = ['c','o','d','e']
chr_counts = {'c': 3, 'o': 1, 'd': 2, 'e': 2}
&gt;&gt;&gt; insert_repetitions_before(chr_list, chr_counts)
&gt;&gt;&gt; chr_list
['c', 'd', 'c', 'c', 'e', 'o', 'd', 'e']


I want to make it more efficient. Currently its time complexity is O(n*m), n being the number of distinct characters and m the average number repetitions. Perhaps something like random.shuffle on a list containing all characters with repetitions, followed by some reordering?



(I'm not sure whether this is the right site to ask, since this question isn't quite specific to Python. Maybe I'll move it to CS.)
I want to make it more efficient. Currently its time complexity is O(n*m), n being the number of distinct characters and m the average number repetitions.


There are two important errors there. Firstly, the time complexity of the given code is worse than stated. Secondly, the stated complexity is optimal.

Taking those in reverse order: the stated complexity is optimal because the number of items which must be inserted into chr_list is \$\Theta(mn)\$, and no matter how you arrange things each insertion will take \$\Omega(1)\$ time.

However, the given code does insertions at random, and an insertion into a random position in a list takes \$\Theta(\textrm{len})\$ time, so the overall complexity of the given code should be \$\Theta(m^2 n^2)\$.



How to achieve optimal asymptotic performance? You need to arrange for the insertions to be done in order. I think that probably requires some additional datastructures. The simplest approach conceptually is to have an array (or a list in Python terms) to store the characters in their final positions and a datastructure of unassigned indexes which allows fast selection of the maximum element and a random element. In Pythonesque pseudocode:

tmpList = [None] * sum(chr_counts)
unassigned = new Datastructure(sum(chr_counts))
for c in reverse(chr_list):
  tmpList[unassigned.removeMax()] = c
  for i in 1 to chr_counts[c] - 1:
    tmpList[unassigned.removeRandom()] = c
copy tmpList to chr_list


The best implementation I've thought of so far for the datastructure of unassigned indexes combines a linked list for fast implementation of max with an array for fast implementation of random. I'm not familiar with Python's OO syntax, so this is again pseudocode:

class LinkedListNode:
  LinkedListNode prev
  LinkedListNode next
  int arrayIdx
  int value

class Datastructure:
  LinkedListNode[] array
  LinkedListNode sentinel = new LinkedListNode

  init(len):
    array = []
    for i in range(len):
      array[i] = new LinkedListNode { arrayIdx = i, value = i }
    for i in range(len-1):
      array[i].next = array[i+1]
      array[i+1].prev = array[i-1]
    sentinel.next = array[0]
    sentinel.prev = array[len-1]
    sentinel.next.prev = sentinel
    sentinel.prev.next = sentinel

  removeMax():
    return removeNode(sentinel.prev)

  removeRandom(rnd):
    randIdx = rnd.randint(0, len(array))
    return removeNode(array[randIdx])

  removeNode(node):
    # Remove from linked list
    node.next.prev = node.prev
    node.prev.next = node.next
    # Remove from array
    array[node.arrayIdx] = array[-1]
    array[node.arrayIdx].arrayIdx = node.arrayIdx
    del array[-1]

    return node.value


Note: I don't really think Datastructure is a good name, but it's not an easy class to name so I'm using it as a placeholder instead of Foo.