Memoization optimization

[molten schooner]

Timezone appropriate greetings!

I've been working on a tournament seating script for Mahjong tournaments. Typically played in tables of 4 players (with a total number of players divisible by 4), for n rounds, the idea is to not have any two players play each other more than once. Quite literally the Social Golfer Problem. The total number of players will be checked externally before this function is called, hence the no checks in any of the functions.

Originally I tried solving it with vectorization, but after thinking about it for some time, today I decided to switch my approach from an iterative one to a recursive one (I did the math for fun today with my sample input - it was in the 10e36 range). The recursive approach seemed to work better almost instantly, but past a certain round # it started slowing down. I figured some memoization was in order, but had no idea how I would implement that into my recursive function, so I asked C||hatGPT|| for help in rewriting it. That made it slightly better, after some tinkering with the rewritten function. Which brings us to now.

For my testing input of 32 players, in groups of 4, for 8 rounds, it solves round 1-6 almost instantly, with round 7 taking anywhere from a few seconds to a few minutes, while round 8 just runs until it caps out my memory.
This test input has a theoretical possible solution for 10 rounds. My goal is to be able to solve this theoretical as fast as possible, with lower end specs in mind.

Since the code has gotten quite long, I pasted it into the playground:
https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=84cc976e5a9cddc51e3ab0fd076ffbfa

Any help and/or code review would be much appreciated

[digital dune]

hello fellow mahjong enjoyer

i am not totally clear what your requirement for solution is, but just rough ideas for optimization

take a look at ndarrays as I see you have nested vecs

can you phrase this problem as a graph? at first everyone is connected, and each round they drop connection with all who they have played. in that case take a look at the crate petgraph, specifically the MatrixGraph as the initial fully connected graph is dense

of course there is also https://crates.io/crates/memoize

[molten schooner]

Thanks for looking through it.
I'll take a look at some of the crates you mentioned after work today.
Petgraph in particular looks like it might even be usable for the actual script. I'm not too familiar with graphs in terms of programmimg, but I'll definitely check it out!

[digital dune]

also if you are building it for practical usage rather than theoretical exploration, take a look at this "good-enough" solver
https://goodenoughgolfers.com

[molten schooner]

It's a mix of both tbh.
That link was my first attempt at it, try to port that solution to Rust. My biggest issue with that one, is that it relies on random generation. Though I do like the weight system it uses, and I'm probably gonna use a variation of that for rounds past the theoretical possible solution (once I get that working).

Is there a way to make hashsets useable as keys to the memo hashmap? It was a random thought that occurred to me, but when I tried doing it, it wouldn't let me, since hashsets doesn't have the Hash trait

[molten schooner]

As in, instead of Vec<Vec<i32>> in the tuple, it's HashSet<Vec<i32>>