Assume a string of four symbols, for example
Consider only those strings with exactly one instance of each symbol, such that s=bacd and s=dacb are both valid strings but s=aabc is not. This gives 4! possible combinations.
Now, each symbol can take a value among
a = [0, 1] b = [0, 1, 2, 3] c = [0, 1] d = [0, 1, 2]
Consequently I may end up having s=cdab=0112 or s=abcd=0000 or s=abdc=1320 etc..
I wish to compute how many combinations (no repetitions) can string s take.
I have written an algorithm that probes all different combinations and discards duplicates, but I would like to understand if a formula can be constructed that returs the same result (not the list of all valid combinatins, but only the number of them).
Here is a practical example: If I have 3 symbols a= b=[0,1] c=[0,1,2] and s=abc, then possible combinations for s are (000,001,002,010,011,012). For s=acb you have (000,001,010,011,020,021) and so forth. You discard the duplicates and (in this example) are left with 16 combinations (000,001,002,010,011,012,020,021,100,101,102,110,120,200,201,210). I have found an algorithm that runs in O(n!) (in this example 3!), but I was wondering whether O(n) or O(1) is feasible.