How to find the probability of possible strings based on the input (number of rows)

Question

How to find the probability of possible strings based on the input (number of rows).

Let's say we have matrix like below of order 9x3 i.e., 9 rows & 3 columns.

A B C
D E F
G H I
. . .
. . .
X Y Z

User can provide any number between 1 to 9 So, if user provides 2 (number of rows) output should look like this

AD
AE
AF
BD
BE
BF
CD
CE
CF

If user provides input 3, output should look like this

ADG
ADH
ADI
AEG
AEH
AEI
AFG
AFH
AFI
BDG
BDH
BDI
BEG
BEH
BEI
BFG
BFH
BFI
CDG
CDH
CDI
CEG
CEH
CEI
CFG
CFH
CFI

Similarly, input number of rows can be vary from 1 to 9 How can i achieve this in python ? Any best possible way ? Recently, I came across this question in one of the interview. I couldn't solve this. May be this post will be helpful for many people.

Is the input matrix of letters always the same? Or it can vary? — polmonroig, Nov 24 '19 at 13:25
@polmonroig Given matrix will be of order 9x3 (as mentioned above, 9 rows & 3 columns). Input will be integer number i.e., number of rows from 1 to 9. — StackGuru, Nov 24 '19 at 13:28
'Find the probability of possible strings.' I take it this will be 1/N, where N is the number of possible strings for a given input (1-9)? — someguy, Nov 24 '19 at 13:34
I also want to confirm whether a string such as `GX` is a valid string for the first example, i.e. whether that list you gave is exhaustive or not. If you just want to calculate the number of possible strings (and thus the probability, given a uniform distribution), you can calculate this with a pocket calculator. — someguy, Nov 24 '19 at 13:38
@someguy Not just count of possible strings, all possible strings to be printed. GX can't be, it has complete list of alphabets in that order. I've just provided it as an example. If you can get the output to any one of the integer, that can be scaled to till 9. — StackGuru, Nov 24 '19 at 13:40
@someguy gave you the answer, if you need another implementation here is a reference https://stackoverflow.com/q/1681269/8493740 — polmonroig, Nov 25 '19 at 08:10

someguy · Answer 1 · 2019-11-24T14:00:11.300

1

You can take advantage of the product() function in the itertools module.

import itertools

for i in itertools.product(*A[:N]):
    print(''.join(i))

Assuming A is your matrix and N is the number of rows to select.

Here's a quick explanation. To generate the list with N=2, you would use two for loops:

for r1 in A[0]:
    for r2 in A[1]:
        print(''.join([r1, r2]))

For N=3, you would use three for loops:

for r1 in A[0]:
    for r2 in A[1]:
        for r3 in A[2]:
            print(''.join([r1, r2, r3]))

Therefore, in general, you need N nested for loops, which is what product() is generating.

edited Nov 24 '19 at 14:00

answered Nov 24 '19 at 13:54

someguy

7,144
12
43
57

But, I guess this would end up in very high complexity. Any other possible way ? – StackGuru Nov 24 '19 at 14:51
@StackGuru: You need to print C^N strings, where C is the number of columns. The complexity of this code happens to be O(C^N). You could probably improve the raw execution speed, but this algorithm is indeed the best you can do in terms of complexity. – someguy Nov 24 '19 at 15:03
can't it be simplified by eliminating N nested for loops ? any other way to arrive at solution ? – StackGuru Nov 25 '19 at 00:01
What do you mean by simplified? `itertools.product(*A[:N])` is pretty simple. The code I presented later is just to illustrate what is going on, in case you misunderstood. Ultimately, you have to print C^N strings, which is also the number of iterations of the loop. – someguy Nov 25 '19 at 01:41

How to find the probability of possible strings based on the input (number of rows)

1 Answers1