# 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}
>>> 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.)

• So chr_list contains exactly the keys of chr_counts exactly once each? Commented Mar 27, 2017 at 11:48
• @PeterTaylor Yes, and each value in chr_counts is at least 1. Commented Mar 27, 2017 at 12:26

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:
int arrayIdx
int value

class Datastructure:

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):
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.

• Correct me if I'm wrong, but max(unassigned) would be unnecessary if unassigned was ordered (ie. a list, not a set). Then you can just pick the last element. Also, unassigned.remove is linear-time operation with respect to size of unassigned. If you use a list, then it's just tmpList[unassigned.pop(-1)] = c. Either way, it's significantly faster than the original version. I might post a version with the efficient implementation of random you mentioned. Commented Mar 27, 2017 at 14:44
• @kyrill, I don't think that either list or set have the desired performance, which is for max, random, and remove to all be constant time. That's why I suggested a composite data structure. To expand slightly, the linked list would be ordered (which is why max is fast) but the array would start ordered and become unordered (fast deletion by swapping the deleted element to the end). I also fudged the remove a bit: really max and random would have to return more complicated elements than just the index so that you can do that swap to the end without first searching for the node Commented Mar 27, 2017 at 14:49
• I gave it some thought and it would be possible but ugly. You would need two arrays with three doubly-linked lists upon them to make it linear-time. One array will hold indices in order, a linked list will link these indices both ways to allow for quick deletions and max. Then a randomly shuffled array with indices and a linked list for this array (again quick deletions and random). Finally a linked list connecting these two arrays, to allow for quick deletions from max array when an index is picked from the random array and vice versa. There must be a nicer way to do it... Commented Mar 27, 2017 at 15:17
• Actually the structure connecting the max and random arrays would not be a doubly-linked list but two maps (dictionaries). It would be nicer if implemented in OO-style, but arguably less efficient, especially since it's an interpreted language. Commented Mar 27, 2017 at 15:26
• @kyrill, updated with more pseudocode. The reason for putting the node's info into the node itself rather than using a dictionary is that the node exists purely for the purposes of this datastructure, so we can do so without harming other code, and we save the overhead of a dictionary. Commented Mar 27, 2017 at 16:01