Split/divide amount into bills and coins randomly

Question

Before I reinvent the wheel, I wanted to find out if there is an algorithm that randomly divides an amount of money into bills and coins.

e.g. I have an amount of 125.50€. possible 1st division:

100 € = 1
50 € = 0
20 € = 1
10 € = 0
5 € = 1
2 € = 0
1 € = 0
0,5 € = 0
0,2 € = 2
01 € = 1

possible 2nd division:

100 € = 0
50 € = 2
20 € = 1
10 € = 0
5 € = 1
2 € = 0
1 € = 0
0,5 € = 1
0,2 € = 0
01 € = 0

It is important that the distribution must be random. Can you give me some advice or is that too complicated?

thanks in advance for the help and advice.

Best regards

Answer 1

Here is a VB.NET solution. Feel free to modify it as needed. For example, I'm not sure how you want the output.

Dim startAmount As Decimal = 125.5
Dim currentAmount As Decimal = startAmount
Dim money As Dictionary(Of Decimal, Integer) = ".01,.2,.5,1,2,5,10,20,50,100".Split(",").ToList().Select(Function(c) CType(c, Decimal)).ToList.ToDictionary(Of Decimal, Integer)(Function(m) m, Function(z) 0)
Dim rand As New Random
Do Until currentAmount < money.Min(Function(m) m.Key)
    Dim increment As Decimal = Decimal.MaxValue
    Do Until increment <= currentAmount
        increment = money.ElementAt(rand.Next(money.Count - 1)).Key
    Loop
    currentAmount -= increment
    money(increment) = money(increment) + 1
Loop
For Each denomination As KeyValuePair(Of Decimal, Integer) In money
    If denomination.Value > 0 Then Console.WriteLine(String.Format("{0} items of value {1}", denomination.Value, denomination.Key))
Next
Console.WriteLine(String.Format("This leaves {0} left over.", currentAmount))