Coin change problem on Rust?


#1

For one unit test I need algorithm to generate all possible
combinations of natural numbers from 1 to n to that give sum equal to n.

This looks like particular case of coin change problem discussed here,
but I do want not write solution by myself, because of then I need unit test to unit test.

So may be there is crate/project somewhere with solution of this problem on Rust?


#2

Would quickcheck work for your needs?


#3

No, I can run it to generate vec: Vec<u32>, but what propbility of that vec.iter().fold(0, |c, x| c + x) give me n ?


#4

Once you have a Vec<i32>, can’t you sum them together to get the n? So for example, if quickcheck generates vec![1, 9, 17], then the n that goes with the vector would be 27.

I’m probably missing some constraint here, could you elaborate?


#5

Actually I want test for several fixed n, so for fixed n I want vec (may be random), which sum of element give me
n. Not opposite. But I see your point, thanks for reply.


#6

Then

let s = Vec<i32>.sum();
if s > n {
skip test, it is in quickchek somewhere;
}
Vec<i32>.push(n-s)

#7

And what’s the problem with testing test code?

Tell you what. I’ve written probably about a dozen variations of this sort of algorithm for various Project Euler problems; as it turns out I even have some written in rust.

But if you use one of these, then I hope you still also validate its output (or at least, the properties that matter for your test) before using it as input to your test. Why? Simple logic! A test is only meaningful if its premises are valid… and who wants to write a meaningless test?


All that’s really necessary to validate it is to verify that (1) the solutions returned are true solutions (i.e. correct sum, all positive integers), (2) they’re all different, and (3) there’s the right number of them. (I included links to OEIS sequences describing the correct number of solutions for various n)


Edit: ok guess I misread a bit, and didn’t realize you were trying to sample the solutions rather than generate all of them.