counting the permutations(subset) of sting

  • (2 Pages)
  • +
  • 1
  • 2

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

#1 RyanMco   User is offline

  • D.I.C Head

Reputation: -9
  • View blog
  • 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   User is offline

  • Suitor #2
  • member icon



Reputation: 14687
  • View blog
  • 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.

Posted Image

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
Was This Post Helpful? 4
  • +
  • -

#3 RyanMco   User is offline

  • D.I.C Head

Reputation: -9
  • View blog
  • 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

Was This Post Helpful? 0
  • +
  • -

#4 modi123_1   User is offline

  • Suitor #2
  • member icon



Reputation: 14687
  • View blog
  • 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.
Was This Post Helpful? 2
  • +
  • -

#5 RyanMco   User is offline

  • D.I.C Head

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

Re: counting the permutations(subset) of sting

Posted 10 January 2019 - 03:34 PM

View Postmodi123_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?
Was This Post Helpful? 0
  • +
  • -

#6 modi123_1   User is offline

  • Suitor #2
  • member icon



Reputation: 14687
  • View blog
  • 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.
Was This Post Helpful? 2
  • +
  • -

#7 RyanMco   User is offline

  • D.I.C Head

Reputation: -9
  • View blog
  • 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"))
Was This Post Helpful? 0
  • +
  • -

#8 modi123_1   User is offline

  • Suitor #2
  • member icon



Reputation: 14687
  • View blog
  • 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.
Was This Post Helpful? 1
  • +
  • -

#9 RyanMco   User is offline

  • D.I.C Head

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

Re: counting the permutations(subset) of sting

Posted 10 January 2019 - 04:02 PM

View Postmodi123_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?!
Was This Post Helpful? 0
  • +
  • -

#10 modi123_1   User is offline

  • Suitor #2
  • member icon



Reputation: 14687
  • View blog
  • 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.
Was This Post Helpful? 1
  • +
  • -

#11 RyanMco   User is offline

  • D.I.C Head

Reputation: -9
  • View blog
  • 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?!!!
Was This Post Helpful? 0
  • +
  • -

#12 modi123_1   User is offline

  • Suitor #2
  • member icon



Reputation: 14687
  • View blog
  • 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)?
Was This Post Helpful? 0
  • +
  • -

#13 RyanMco   User is offline

  • D.I.C Head

Reputation: -9
  • View blog
  • 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?
Was This Post Helpful? 0
  • +
  • -

#14 modi123_1   User is offline

  • Suitor #2
  • member icon



Reputation: 14687
  • View blog
  • 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?
Was This Post Helpful? 0
  • +
  • -

#15 MentalFloss   User is offline

  • .
  • member icon

Reputation: 613
  • View blog
  • 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.
Was This Post Helpful? 1
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2