Sort matrix, but return the indices that would sort it, not the data itself (NumPy argsort)

[PseudoResonance]

I was looking around at the documentation, but I don't think there's a comparable method in math.js to NumPy's argsort. Unless I've missed it, I think it'd be a handy feature to have!

Examples from NumPy:

> x = [3, 1, 2]
> y = argsort(x)
[1, 2, 0] # If you replace each value, i, with x[i], you will get the same following sorted array, z.
> z = sort(x)
[1, 2, 3]

As an example, I am using argsort to make pairs between the most similar elements of 2 arrays.

I create a 2D matrix, with one dimension representing the index of 1 array, and the other represents the 2nd array. This is filled with numbers that represent the similarity of any 2 given elements of the arrays. Then I flatten the matrix, argsort it, unravel_index to get the original matrix indices back, and do a little more processing.

The end result is a single array, containing tuples (technically arrays) of the x,y coordinates of the original matrix, sorted by similarity. Then I can go through and fetch the pairs I want.

In hindsight, perhaps there was a better, already implemented way to solve this in JS, but I had the Python NumPy code so my first thought was to just directly port it over...

[PseudoResonance]

Here is an ugly implementation of this.

function argsort<T = unknown>(
	input: T[],
	compare?: (a: T, b: T) => number,
): number[] {
	// From https://stackoverflow.com/a/65410414
	return input
		.map((value, index) => [value, index])
		.sort(
			compare !== undefined
				? (a, b) => compare(a[0] as T, b[0] as T)
				: undefined,
		)
		.map((arr) => arr[1] as number);
}

[gwhitney]

I don't think you missed it; I do not think mathjs has a method equivalent to argsort. If so, it would presumably be in the "matrix" section of functions, where sort resides. Although mathjs can't become the Universal Compendium of All Algorithms ;-), this one seems close enough in spirit to what's already in mathjs that it might warrant inclusion. What do you think, @josdejong -- would you be accepting of a PR to add a function like argsort? Note that even if so, its inclusion would likely need a third-party pull request for it to happen; I don't see the main mathjs maintainers/developers as having time to implement this.

[josdejong]

Adding a function like argsort sounds like a good idea! We have to think through a way to let it play nice with the current subset functionality. So for example right now we can use subset and index:

const A = [3, 1, 2]
const i = [1, 2, 0] // this will be returned by this new function argsort
const ASorted = math.subset(A, math.index(i))

Thoughts:

• Maybe we want argsort to return an MatrixIndex rather than an Array, so its output can be used directly in math.subset(A, i)
• It also makes sense to extend function sort to accept an index, so we can do sort(A, i) like you propose.
• We also have to think through how to deal with the expression parser working one-based, whilst the JS API is zero-based.

Anyone interested in thinking through the API for this function and implementing it in a PR? Help would be very welcome.

[PseudoResonance]

Also, in the example above, unravel_indices might kind of go together with argsort. Those 2 functions were the only operations missing for me to implement my algorithm described above. I'm not entirely sure where the "bounds" of what makes sense in math.js are though, but it is just another idea.

Here's the simple TypeScript I threw together to make it work as well. There's probably a much better way to do the types, but I've never used Math.js before and was just learning what types are available and all that.

export function unravel_index<T extends math.MathArray>(
	x: T,
	sizes: number[],
): math.Matrix<math.MathNumericType> {
	let work: T = x.slice() as T;
	const result: T[] = [];
	for (let dim = sizes.length - 1; dim >= 0; dim--) {
		result[dim] = math.mod(work, sizes[dim] as number) as T;
		work = math.floor(math.divide(work, sizes[dim] as number) as T) as T;
	}
	return math.matrix(result);
}

On the other hand, this is a very slippery slope!