Iterate though all permutations randomly

Question

I have imported an large array and I want to iterate through all row permutations at random. The code is designed to break if a certain array produces the desired solution. The attempt so far involves your normal iterative perturbation procedure:

import numpy as np
import itertools

file = np.loadtxt("my_array.csv", delimiter=", ")
for i in itertools.permutations(file):
    ** do something **
    if condition:
        break

However, I would like the iterations to cover all perturbation and at random, with no repeats.

Ideally, (unlike random iteration in Python) I would also avoid storing all permutations of the array in memory. Therefore a generator based solution would be best. Is there a simple solution?

Answer 1

The answer is to first write a function that given an integer k in [0, n!) returns the kth permutation:

def unrank(n, k):
    pi = np.arange(n)
    while n > 0:
        pi[n-1], pi[k % n] = pi[k % n], pi[n-1]
        k //= n
        n -= 1
    return pi

This technique is found in Ranking and unranking permutations in linear time by Wendy Myrvold and Frank Ruskey.

Then, if we can generate a random permutation of [0, n!) we are done. We can find a technique for this (without having to construct the whole permutation) in Sometimes-Recurse Shuffle by Ben Morris and Phillip Rogaway. I have an implementation of it available here.

Then, all we have to do is:

import math
a = np.array(...)  # Load data.
p = SometimeShuffle(math.factorial(len(a)), "some_random_seed")
for kth_perm in p:
    shuffled_indices = unrank(len(a), kth_perm)
    shuffled_a = a[shuffled_indices]