5

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?

theotheraccount
  • 145
  • 5
  • 1
    is it a requirement that it remains a generator? Otherwise it would be pretty simple to convert the result to a list and then shuffle that – questionerofdy Dec 03 '20 at 22:04
  • @questionerofdy, I should say that the ideal result would not store a large number of permutations in memory. I shall add this comment to my question - but good thinking. – theotheraccount Dec 03 '20 at 22:10

1 Answers1

4

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]
orlp
  • 112,504
  • 36
  • 218
  • 315
  • The `random_perms()` seems not really generating random permutations. The iterated permutations are highly ordered. – Libin Wen Apr 10 '22 at 14:45
  • @LibinWen Yeah you're right, I deleted that part of the answer. The first picked permutation is random but then it's correlated with the next one, etc. – orlp Apr 10 '22 at 15:55