Random permutation with defined order of last occurrences
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.