24

I have a numpy array [0, 1, 1, 2, 2, 0, 1, ...] which only contains the numbers 0-k. I would like to create a new array that contains the n possible arrays of permutations of 0-k. A small example with k=2 and n=6:

a = [0, 1, 0, 2]
permute(a)
result = [[0, 1, 0, 2]
          [0, 2, 0, 1]
          [1, 0, 1, 2]
          [2, 1, 2, 0]
          [1, 2, 1, 0]
          [2, 0, 2, 1]]

Does anyone have any ideas/solutions as to how one could achieve this?

MBrown
  • 545
  • 1
  • 3
  • 14
  • 3
    This is a duplicate plus a [google away](http://stackoverflow.com/questions/27323448/numpy-array-to-permutation-matrix). – kabanus Dec 18 '16 at 15:58
  • 14
    @kabanus OP seems to want *distinguishable* permutations -- which that link doesn't give. – John Coleman Dec 18 '16 at 16:02

2 Answers2

54

Your a is what combinatorists call a multiset. The sympy library has various routines for working with them.

>>> from sympy.utilities.iterables import multiset_permutations
>>> import numpy as np
>>> a = np.array([0, 1, 0, 2])
>>> for p in multiset_permutations(a):
...     p
...     
[0, 0, 1, 2]
[0, 0, 2, 1]
[0, 1, 0, 2]
[0, 1, 2, 0]
[0, 2, 0, 1]
[0, 2, 1, 0]
[1, 0, 0, 2]
[1, 0, 2, 0]
[1, 2, 0, 0]
[2, 0, 0, 1]
[2, 0, 1, 0]
[2, 1, 0, 0]
Ocaso Protal
  • 19,362
  • 8
  • 76
  • 83
Bill Bell
  • 21,021
  • 5
  • 43
  • 58
34

if your permutations fit in the memory, you could store them in a set and thus only get the distinguishable permutations.

from itertools import permutations

a = [0, 1, 0, 2]

perms = set(permutations(a))
Jonas Adler
  • 10,365
  • 5
  • 46
  • 73
hiro protagonist
  • 44,693
  • 14
  • 86
  • 111
  • 2
    This is probably okay for small examples, but this involves generating n! permutations when the number of distinguishable permutations might be much smaller – John Coleman Dec 18 '16 at 16:29
  • @JohnColeman: i agree. but as i have no idea how big the sample is... it might just work. – hiro protagonist Dec 18 '16 at 16:31
  • As is often the case in Python, it is a question of scale. This is a perfectly good approach for smaller examples (which is why I upvoted it). For larger examples you would want to use a library with multiset support (as the other answer has). – John Coleman Dec 18 '16 at 16:33
  • 9
    By the way -- `set(permutations(a))` is a 1-line implementation of your idea. – John Coleman Dec 18 '16 at 16:39