Menu
say I have a set of numbers '0', '1', '2', ..., '9'. I want to find all numbers that contain exactly one of each of the numbers in my set.
The problem is: Before I start my program, I do not know how many numbers and which numbers my set will include. (For example, the set could include the numbers '1', '3' and '14'.)
I searched the internet, and stumbled upon the term 'dynamic programming' which apparently is something to use to solve problems like mine, but I did not understand the examples.
Can somebody give me a hint on how to solve this problem (possibly with dynamic programming)?
EDIT: When the set includes numbers like '14' the different numbers of the set would of course have to be separated by some means, e.g. when the set includes the numbers '1', '3', and '14', combinations could be something like 1-3-14 or 3-14-1 (= individual numbers separated by a '-'-character).
EDIT 2: One problem that seems to be somewhat similar is described here: one of the solutions uses dynamic programming.
601
Remember, the formula to calculate combinations is nCr = n! / r! * (n - r)!, where n represents the number of items, and r represents the number of items being chosen at a time. Let's look at an example of how to calculate a combination.
If you meant to say "permutations", then you are probably asking the question "how many different ways can I arrange the order of four numbers?" The answer to this question (which you got right) is 24.
The formula for combinations is generally n! / (r! (n -- r)!), where n is the total number of possibilities to start and r is the number of selections made. In our example, we have 52 cards; therefore, n = 52. We want to select 13 cards, so r = 13.
To find all the combinations of two numbers, we multiply the number of possible outcomes for the first number by the number of possible outcomes for the second number. Let us look at this with an example. If the numbers we can use are 0 through 9, then there will always be 10 possible outcomes for the first number.
To me, it looks like you are looking for all permutations of a given set of elements.
If you use C++ there is a standard function next_permutation() that does exactly what you are looking for. You start with the sorted array and then call next_permutation repeatedly.
The example is here: http://www.cplusplus.com/reference/algorithm/next_permutation/
121
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
