Create permutation matrix - numpy

Question

Given an integer k how would I create a permutation matrix with all possible permutations of the sequence 1 to k? For example, let's consider k=2. Then I would like to create the matrix:

1 2
2 1

and for k=3:

1 1 2 2 3 3
2 3 1 3 1 2 
3 2 3 1 2 1

I've tried using numpy.random.permutation but this only produces a single permutation. So, I could continue using this function, appending unique permutations until the number of columns is equal to k! but this seems incredibly inefficient.

what about feeding `itertools.permutations` into a numpy array? — hilberts_drinking_problem, Nov 28 '16 at 23:02
@YakymPirozhenko is it possible to do this without importing `itertools`? — Apollo, Nov 28 '16 at 23:04
Well, not unless you want to write your own function to generate a list of permutations. Also, as `itertools` is a builtin module, I can't see much downside to importing unless you have some explicit restrictions. — hilberts_drinking_problem, Nov 28 '16 at 23:08
What kind of `k` do you have in mind? The matrix won't fit into RAM if it's a dozen or more. — , Nov 29 '16 at 00:00
`itertools` is the best choice. Some `numpy` test code uses it. While the result can be collected in a array, generating the permutations is really a iterative process, not an array one. — hpaulj, Nov 29 '16 at 02:35

score 1 · Answer 1 · edited May 23 '17 at 12:01

1

Based off this answer:

import numpy as np
import itertools as it
import math
def myPerms(k):
  f_k=math.factorial(k)
  A=np.empty((k,f_k))
  for i,perm in enumerate(it.permutations(range(k))):
    A[:,i] = perm
  A+=1
  return A

print(myPerms(3))
#[[ 1.  1.  2.  2.  3.  3.]
# [ 2.  3.  1.  3.  1.  2.]
# [ 3.  2.  3.  1.  2.  1.]]

edited May 23 '17 at 12:01

Community

1
1

answered Nov 30 '16 at 15:20

Felipe Lema

2,700
12
19

Kh40tiK · Answer 2 · 2016-11-30T16:08:27.490

How about a pure numpy solution:

from math import factorial as fac
import numpy as np

def permmat(n):
    if n==1:
        return np.array([[1]], dtype=np.int8)
    fnm1 = fac(n-1)
    pmat_nm1 = permmat(n-1)
    pmat = np.empty((n, fac(n)), dtype=np.int8)
    pmat[0] = np.repeat(np.arange(n,0,-1), fnm1)
    pmat[1:, :fnm1] = pmat_nm1
    for i in range(1,n):
        view = pmat[1:, fnm1*i:fnm1*(i+1)]
        view[:,:] = pmat_nm1
        view[pmat_nm1==(n-i)] = n
    return pmat

print(permmat(4))

Output:

[[4 4 4 4 4 4 3 3 3 3 3 3 2 2 2 2 2 2 1 1 1 1 1 1]
 [3 3 2 2 1 1 4 4 2 2 1 1 3 3 4 4 1 1 3 3 2 2 4 4]
 [2 1 3 1 2 3 2 1 4 1 2 4 4 1 3 1 4 3 2 4 3 4 2 3]
 [1 2 1 3 3 2 1 2 1 4 4 2 1 4 1 3 3 4 4 2 4 3 3 2]]

There's still space for some performance hack but I'm too lazy to write them.

score -1 · Answer 3 · answered Jul 02 '17 at 20:25

-1

my solution:

perm_mat = np.zeros(PERM_SIZE,NUM_OF_PERM))
for i in range(NUM_OF_PERM):
perm_mat[:,i] = np.random.permutation(PERM_SIZE))
perm_mat = perm_mat.astype(int)

answered Jul 02 '17 at 20:25

Nadav

157
1
1
7

This may produce repeating permutations and not produce all possible permutations. – Viktoriya Malyasova Jun 13 '19 at 10:29

Create permutation matrix - numpy

3 Answers3