Problem Statement

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. Analyse the time complexity of your algorithm.

3. Implement the above problem statement using Python 3.7

Also it needs to be an efficient algorithm using dynamic programming to perform the above task. and to analyse the time complexity of your algorithm

Input file :

Input should be taken in through a file called “inputPS12.txt” which has the fixed format mentioned below using the “/” as a field separator: Player / < position 1> / < position 2> / < position 3>….

Ex: 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

Please help in suggesting this and how it can be implemented in python .

Note : Use only native data types like lists and tuples in Python. Use of libraries like graph, numpy, pandas library etc. is not allowed.

It is compulsory to use Python 3.7 for implementation