Permutations without repetition

[maxgalli]

Hi everyone,

I was wondering if there is a function that performs permutations without (or with, but it wouldn't be my use case) repetitions of items inside an array. Taking as example the one from ak.combinations it would be something like:

>>> array = ak.Array(["a", "b", "c"])
>>> ak.to_list(ak.permutations(array=array, n=2, replacement=False, axis=0))
[('a', 'b'), ('a', 'c'), ('b', 'c'), ('b', 'a'), ('c', 'a'), ('c', 'b')]

My use case would be a tag and probe-like workflow, in which we select pairs of photons but each photon within the pair can be both tag and probe, hence we have to treat both cases.

If there is no such thing, are there any ideas about how it could be nicely and efficiently implemented (maybe not in awkward since outside HEP could be not so needed, but maybe inside something like coffea @lgray)?

Thanks a lot,

Massimiliano

[jpivarski]

Are you sure what you're looking for should be called "permutations"? It looks like you want the Cartesian product with the diagonal elements removed (see ak.cartesian).

Here's a way to get your desired output (up to the order, but I think the middle two are swapped):

>>> array = ak.Array(["a", "b", "c"])
>>> left, right = ak.unzip(ak.argcartesian([array, array], axis=0))
>>> left
<Array [0, 0, 0, 1, 1, 1, 2, 2, 2] type='9 * int64'>
>>> right
<Array [0, 1, 2, 0, 1, 2, 0, 1, 2] type='9 * int64'>
>>> different = (left != right)
>>> left[different]
<Array [0, 0, 1, 1, 2, 2] type='6 * int64'>
>>> right[different]
<Array [1, 2, 0, 2, 0, 1] type='6 * int64'>
>>> array[left[different]]
<Array ['a', 'a', 'b', 'b', 'c', 'c'] type='6 * string'>
>>> array[right[different]]
<Array ['b', 'c', 'a', 'c', 'a', 'b'] type='6 * string'>
>>> ak.zip([array[left[different]], array[right[different]]], depth_limit=1).tolist()
[('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b')]

This could be the implementation of what you're looking for, with some care to apply the cut (left[different] and right[different]) at the appropriate axis. But what should such a function be named?

---

Regarding permutations, all the ways that a multiset of items can be ordered as a sequence, we could use NumPy's function at axis=0... Or not! It turns out that NumPy doesn't have a function for listing all permutations. They have np.random.permutation, but not one that enumerates. There are various recipes online for doing it with np.repeat and np.tile, but by that point and because you'd want something that works at axis != 0, it would have to be a new, specialized Awkward Array function.

(A NumPy function that takes an array of length n and makes an array of length n! would probably be a bad idea. But for jagged arrays with typically small inner dimension, the output array would have total size sum_i (n_i!), which wouldn't be so bad.)

[maxgalli]

I wasn't indeed sure about how to call what I needed :)
Thank you for the very detailed answer, I will try it out!