# counting the permutations(subset) of sting

• (2 Pages)
• 1
• 2

## 16 Replies - 587 Views - Last Post: 10 January 2019 - 08:25 PM

### #1 RyanMco

Reputation: -9
• Posts: 93
• Joined: 27-December 18

# counting the permutations(subset) of sting

Posted 10 January 2019 - 12:54 PM

Hi guys, regarding to what've written in my last thread, I'm going to explain what's not cleared for me and what I've solved of the problem of counting words.
well, as you know I must do a function (called Num_Ways(string) )which counts the words that represents string number from a-z, I mean if I have "1" then there's one letter "a" representing that's number. if I have "12" then "ab" or "l" representing that number "12", so there's two words which representing that number.
Now I arrived to the case that I have more string than two digit like "123456" so what do I do in that case?! what I think to solve is like this : lets assume I have "123456" so it's the same as to say "123456"="1" + "23456" , so for finding the number of words that "123456" representing, I have to do like this Num_Way("123456")=Num_Way("1") + Num_Way("23456") ; but the output of this is wrong and the output is always more than 1 from the correct output. what I'm not understanding, there're some guys said I must multiply Num_Way("1") * Num_Way("23456") , but why? I've read the rule of produce and combinatorics but didn't get the idea of !

So please, anyone can elaborate and interpret why we need to multiply and not add? thank in advance and I hope that the admin will not close this thread because it's about two days stuck in this problem, so please !

Is This A Good Question/Topic? 0

## Replies To: counting the permutations(subset) of sting

### #2 modi123_1

• Suitor #2

Reputation: 14687
• Posts: 58,690
• Joined: 12-June 08

## Re: counting the permutations(subset) of sting

Posted 10 January 2019 - 12:59 PM

As it has been pointed out your math is flawed. You cannot assume you break down a four character string into four permutations on individual objects. That ignores ordering and location in the string.

You need to sit down with the math and write it out.

The web is full of resources..

Examples:
http://mathworld.wol...ermutation.html
https://study.com/ac...ermutation.html

### #3 RyanMco

Reputation: -9
• Posts: 93
• Joined: 27-December 18

## Re: counting the permutations(subset) of sting

Posted 10 January 2019 - 03:02 PM

Just to recap, once I write the complex case I'm breaking up the problem to sub problems, so in the first call I have "12345" and once it will go to the complex case, what I do is (( "1" + "2345" )) but because of math's combinatorics the possibility of "1" is not adding it, I must multiply it for getting the total possibilities .. right?

for example if there're too many possibilities to "1" concatenated with "2345", lets assume "1" has 4 possibilities then I must do like this 4* Num_Way("2345") right?

This post has been edited by RyanMco: 10 January 2019 - 03:15 PM

### #4 modi123_1

• Suitor #2

Reputation: 14687
• Posts: 58,690
• Joined: 12-June 08

## Re: counting the permutations(subset) of sting

Posted 10 January 2019 - 03:23 PM

What? Did you review the links and actually do the math from them?

I would suggest drawing it out if you are unable to get the visualization down.

### #5 RyanMco

Reputation: -9
• Posts: 93
• Joined: 27-December 18

## Re: counting the permutations(subset) of sting

Posted 10 January 2019 - 03:34 PM

modi123_1, on 10 January 2019 - 10:23 PM, said:

What? Did you review the links and actually do the math from them?

I would suggest drawing it out if you are unable to get the visualization down.

I mean if the Num_Way("1") is 3 possibilities, then I must multiply it by Num_Way("2345") right?

### #6 modi123_1

• Suitor #2

Reputation: 14687
• Posts: 58,690
• Joined: 12-June 08

## Re: counting the permutations(subset) of sting

Posted 10 January 2019 - 03:36 PM

Why would there be three ways to combine a single item?

It's like you are trying to reinvent permutation math.. I don't get why.

### #7 RyanMco

Reputation: -9
• Posts: 93
• Joined: 27-December 18

## Re: counting the permutations(subset) of sting

Posted 10 January 2019 - 03:49 PM

I'm just assuming to see if my understanding is right or not !

for example for "12" I've two possibilities which "ab" and "l" but we didn't multiply Num_Ways("34") by 2. (( "12"+decode("34"))

### #8 modi123_1

• Suitor #2

Reputation: 14687
• Posts: 58,690
• Joined: 12-June 08

## Re: counting the permutations(subset) of sting

Posted 10 January 2019 - 03:52 PM

Quote

for example for "12" I've two possibilities which "ab" and "l"

What?

Two possibilities.. 1,2 or 2,1 .. No a,b or l.

I don't get why you keep trying to ram regular multiplication into this. It's matrix math. One of my links explained this.

### #9 RyanMco

Reputation: -9
• Posts: 93
• Joined: 27-December 18

## Re: counting the permutations(subset) of sting

Posted 10 January 2019 - 04:02 PM

modi123_1, on 10 January 2019 - 10:52 PM, said:

Quote

for example for "12" I've two possibilities which "ab" and "l"

What?

Two possibilities.. 1,2 or 2,1 .. No a,b or l.

I don't get why you keep trying to ram regular multiplication into this. It's matrix math. One of my links explained this.

Sir apparently you don't understand at all my question.

My question is for every digit there's a string from a-z that represents it so what are you talking about?!

### #10 modi123_1

• Suitor #2

Reputation: 14687
• Posts: 58,690
• Joined: 12-June 08

## Re: counting the permutations(subset) of sting

Posted 10 January 2019 - 04:10 PM

Apparently not understanding what you are writing.

### #11 RyanMco

Reputation: -9
• Posts: 93
• Joined: 27-December 18

## Re: counting the permutations(subset) of sting

Posted 10 January 2019 - 04:26 PM

I will explain again !

Let 1 represent ‘A’, 2 represents ‘B’, etc. Given a digit sequence, count the number of possible decodings of the given digit sequence.
Examples:

Input: digits[] = "121"
Output: 3
// The possible decodings are "ABA", "AU", "LA"

Input: digits[] = "1234"
Output: 3
// The possible decodings are "ABCD", "LCD", "AWD"

my question how to do that recursively?!!!

### #12 modi123_1

• Suitor #2

Reputation: 14687
• Posts: 58,690
• Joined: 12-June 08

## Re: counting the permutations(subset) of sting

Posted 10 January 2019 - 04:39 PM

Okeley dokely.. Does order matter?

In the case of '121' you can have:
1 : A
2 : B
1 : A
12 : L
21 : U
121 : ?

Can there be a 11 (K)?

### #13 RyanMco

Reputation: -9
• Posts: 93
• Joined: 27-December 18

## Re: counting the permutations(subset) of sting

Posted 10 January 2019 - 04:52 PM

no order doesn't matter

what's confusing me is, lets assume I have "121" then it's the same to say as :
decode("1") + decode("21") or decode ("12")+ decode("1" )

but why we are not taking the Num_Ways("1") within Num_Ways("121") ?!

I mean in the subproblem itself, we are not consider the "one digit" that we have split it ...why?

### #14 modi123_1

• Suitor #2

Reputation: 14687
• Posts: 58,690
• Joined: 12-June 08

## Re: counting the permutations(subset) of sting

Posted 10 January 2019 - 05:29 PM

So... 11? That doesn't matter?

### #15 MentalFloss

• .

Reputation: 613
• Posts: 1,580
• Joined: 02-September 09

## Re: counting the permutations(subset) of sting

Posted 10 January 2019 - 06:52 PM

This is so confusing.

You have some string of digits where a digit can be a letter of the alphabet, and two digits can be a letter of the alphabet. We have 26 letters in our alphabet, so there is no case where it can be three digits.

If you have "12345" for example, then you can have "1", "12", "23" and that's it. Anything further is too big.

However, if you can simply take any digit(s) in sequence, then you have "1","2","3","4","5","12","23" and that's it. "34" is too big.

So, let's take an uglier example: "121322"

"1", "2", "1", "3", "2", "2", "12", "21", "13", "22". We couldn't use "32", and as before no three digit value works.

Then, what did we do to solve this?

```Let S = "121322"
for C = S[0] to S.length-1
if C <= 26: add C to list
Let D = C concat C+1
if D <= 26: add D to list
Repeat
```

Beyond that, I don't think I understand the problem because you dance around the core issue way too much.

• (2 Pages)
• 1
• 2

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }