Problem:

For the upcoming world-cup, the Indian Cricket Selection Committee has to come up with a possible batting order for their players. Instead of using the traditional approach they have decided to use computer algorithms to come up with all the possible batting orders and then decide from that. The algorithm however requires the possible batting positions for each player.

The algorithm takes a list of 11 players. Each player can have more than one position they can bat at. Your job for now is to help the selection committee calculate the total number of unique batting charts such that every player gets exactly one batting position from their list of positions and no two players are given the same batting position in one batting chart.

Requirements:

1. Formulate an efficient algorithm using dynamic programming to perform the above task.

2. Analyze the time complexity of your algorithm.

3. Implement the above problem statement using Python 3.7/3.8/3.9

Input:

Input should be taken in through a file called inputPS18.txt which has the fixed format mentioned below using the / as a field separator:

Player / < position 1> / < position 2> / < position 3>.

Example:

P1 / 1 / 2 / 3 / 4

P2 / 1 / 5 / 9 / 2 / 6 / 7 / 8

P3 / 1 / 2 / 7 / 10 / 3

P4 / 1 / 9 / 2 / 6 / 7 / 10 / 3 / 4

P5 / 5 / 9 / 2 / 8 / 3 / 4

P6 / 1 / 5 / 3 / 6

P7 / 6 / 7 / 4

P8 / 1 / 9 / 2 / 4

P9 / 9 / 6 / 11 / 3 / 4

P10 / 1 / 5 / 9 / 7 / 8 / 4

P11 / 6 / 11 / 7 / 10

Output:

Sample Output: The total number of allocations possible is: 4646.

(Output should look like this, i.e. total number possible combinations/allocations value)

Note:

1. Share code in python, in indented format.

2.Please check output getting properly or not.