This Python function takes two arguments:chr_list which is a mutable sequence of characters cchr_counts which maps to each character c the number of occurrences nFor 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}>>> insert_repetitions_before(chr_list, chr_counts)>>> 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.)
Random permutation with defined order of last occurrences
python;performance;algorithm;complexity
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()] = ccopy tmpList to chr_listThe 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 valueclass 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.valueNote: 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.