CODEWITHSUNDEEP
algorithmdynamic-programmingmemoization
Za Hirah
Za Hirah

Reputation: 43

Dynamic Programming to solve Permutation

I have four digits, "1", "2", "3", "4".

The input of the program is an integer which can only comprise of the above 4 digits. There is going to be a lot of inputs.

Example of inputs: 1123, 4123, 4444

I need to calculate the number of permutations of a given input that adheres to the following rules:

  1. No two similar digits should be adjacent to each other. Example: 1223 is not allowed but 2123 is allowed.
  2. The start end end digits should not be the same. They are considered as being circularly adjacent. Example: 2132 is not allowed.
  3. If the input is 4 digits of length, your resulting permutation should also be of 4 digits of length.

Could I use any type of memoization to solve this problem? How do i store it in a 2d array? Do give tips thanks!

Upvotes: 2

Views: 2688

Answers (1)

Henry
Henry

Reputation: 43738

Since you are only interested in the number of allowed arrangements, most of the inputs lead to identical results.

  • the order of the digits in the input does not matter
  • only the frequency distribution of digits is important, i.e. 1123 and 1223 lead to the same answer.

Classifying the inputs according to digit frequencies leads to just 5 different cases for four digit inputs:

class     examples
4         4444, 2222, ...
3 1       1211, 2232, ...
2 2       1331, 4422, ...
2 1 1     3413, 1123, ...
1 1 1 1   1234, 4231, ...

Once you have figured out the answer for each case, any new input can be handled very fast.

Upvotes: 2

Related Questions