ACK; I really like having unit tests for the coin selection algorithm.

@gavinandresen I noticed that the shuffle was missing some time ago. It has been added back in in #1017 which is my current branch for these changes, and includes the coincontrol and lesschange changes too.

I'll also add a new unit test for randomness too.

Do you need this pull request with just the refactoring updated too? I merged these related changes all together to make them easier to keep up to date.

Notice that the coins are sorted into order before running the stochastic approximation:

// Solve subset sum by stochastic approximation
sort(vValue.rbegin(), vValue.rend());

and so the shuffle's work will be undone in the case you propose. The only times the shuffle has any effect is if:

1. there are multiple coins with the exact value requested (e.g. have 1,1,1 and request 1), or
2. there is no coin with the exact value requested, and the sum of coins smaller than the sum requested is less than the sum requested, and there are a multiple coins of the same value all representing the smallest value that is larger than the sum requested (e.g. have 1,1,1,5,5,6 and request 4; sum of smaller coins = 3 < requested 4; smallest value larger than requested 4 is 5; there are multiple 5 coins). I'll add tests for both these cases to make sure the shuffle is happening.

I added your suggested "4-from-100 identical" test to check that different random coins were being selected each time. It ran the test 100 times. And every time it failed on iterations 49 and 51. It turns out that this is because rand() is being used in the stochastic approximation code:

if (nPass == 0 ? rand() % 2 : !vfIncluded[i])

and rand() isn't being seeded, so returns the same sequence each time bitcoin is run. See new bug #1057.

If I use GetRandInt(2) instead of rand()%2 then the tests fail occasionally, but randomly. It turns out that selecting 4 coins from a sorted list of 100 often picks the same 4. So I'll pick 50 from 100 instead to minimise the chance of a random identical selection.

I've merged my latest changes to the unit tests from lesschange-v0.6.0 (#1017) back onto this branch. There are also tests for sub-cent change suggested by Luke here: #898 (comment) which didn't get into this branch before.

Is this superceded or not?

Closing; I pulled 1416 which was an updated version.