How to find all combinations of coins when given some dollar value [closed]

by

I looked into this once a long time ago, and you can read my little write-up on it. Here’s the Mathematica source.

By using generating functions, you can get a closed-form constant-time solution to the problem. Graham, Knuth, and Patashnik’s Concrete Mathematics is the book for this, and contains a fairly extensive discussion of the problem. Essentially you define a polynomial where the nth coefficient is the number of ways of making change for n dollars.

Pages 4-5 of the writeup show how you can use Mathematica (or any other convenient computer algebra system) to compute the answer for 10^10^6 dollars in a couple seconds in three lines of code.

(And this was long enough ago that that’s a couple of seconds on a 75Mhz Pentium…)

More Related Contents:

  1. SICP example: Counting change, cannot understand
  2. What is tail recursion?
  3. What is tail call optimization?
  4. Understanding recursion [closed]
  5. Expand a random range from 1–5 to 1–7
  6. Is log(n!) = Θ(n·log(n))?
  7. How to find list of possible words from a letter matrix [Boggle Solver]
  8. Finding a single number in a list [duplicate]
  9. recursion versus iteration
  10. Breadth First Vs Depth First
  11. Algorithm to generate anagrams
  12. Design patterns for converting recursive algorithms to iterative ones
  13. How to generate Sudoku boards with unique solutions
  14. find all subsets that sum to a particular value
  15. Quicksort: Iterative or Recursive
  16. Efficiently reverse the order of the words (not characters) in an array of characters
  17. Why is the complexity of computing the Fibonacci series 2^n and not n^2?
  18. Basic Recursion, Check Balanced Parenthesis
  19. Programming Riddle: How might you translate an Excel column name to a number?
  20. Fastest algorithm for circle shift N sized array for M position
  21. Why does the greedy coin change algorithm not work for some coin sets?
  22. Finding height in Binary Search Tree
  23. Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin
  24. Why is my recursive function so slow in R?
  25. Convert recursion to tail recursion
  26. How to print all possible balanced parentheses for an expression?
  27. Memory efficient power set algorithm
  28. Hash table runtime complexity (insert, search and delete)
  29. Finding all the shortest paths between two nodes in unweighted undirected graph
  30. How to calculate or approximate the median of a list without storing the list

Leave a Comment