NP or P problem?
Author
Hi,
I am trying to write an algorithm and I can't find a solution.
I am gonna give you an exemple it will be easier to understand, the input is just a number. The output is a list of list of numbers.
in:2
out:
11
2
in:3
out:
111
21
12
3
in:4
out:
1111
211
112
22
31
13
4
in:5
out:
11111
2111
1211
1121
1112
221
212
122
311
131
113
23
32
41
14
5
I think there are not polynomial solutions. Am I right? How can I resolve this kind of problem?
Thanks,
Quote:Original post by smallGameTrying to match a number pattern reeks of a badly-written homework problem. It appears you are trying to do permuations, but that isn't likely to be something you'll actually use in the world.
I am trying to write an algorithm and I can't find a solution.
What is the actual problem you are trying to solve with this algorithm?
Author
Yes you right, I just try to prepare myself to job interviews. I feel like it's shame on me to not resolve this kind of staff.
I had a technical test to do and I gave up. So I don't know if it's good to give the test; even if it's over for me. So I give just an exemple:
input: string of digits, result
output string of digits with operator to get the result
"1231231234",11353 -> "12*3+1+23*123*4"
I had a technical test to do and I gave up. So I don't know if it's good to give the test; even if it's over for me. So I give just an exemple:
input: string of digits, result
output string of digits with operator to get the result
"1231231234",11353 -> "12*3+1+23*123*4"
Quote:Original post by smallGame
input: string of digits, result
output string of digits with operator to get the result
"1231231234",11353 -> "12*3+1+23*123*4"
This.
For the original problem, if you imagine 5 elements in a row, there are 4 spaces between them. Now we'll put dividers in some of those spaces. For instance this is a possible configuration:
O|O O|O O => 1 2 2
There are 2^4 possible selections of which spaces have dividers in them (all 4-bit numbers), which gives you an easy way to enumerate the possibilities.
If you start with n elements, there are 2^(n-1) lines in the output. This is neither P nor NP.
O|O O|O O => 1 2 2
There are 2^4 possible selections of which spaces have dividers in them (all 4-bit numbers), which gives you an easy way to enumerate the possibilities.
If you start with n elements, there are 2^(n-1) lines in the output. This is neither P nor NP.
Quote:Original post by alvaro
If you start with n elements, there are 2^(n-1) lines in the output. This is neither P nor NP.
Er, O(2^n) problems surely are NP...
But yeah, the outputs for N are recursively the outputs for (N-1) with a 1 prepended to them, as well as the outputs for (N-1) with 1 added to the first value.
Quote:Original post by ZahlmanQuote:Original post by alvaro
If you start with n elements, there are 2^(n-1) lines in the output. This is neither P nor NP.
Er, O(2^n) problems surely are NP...
That's not how it works. For a problem to be in NP you need to be able to verify that the answer is correct in polynomial time, which is not the case if the length of the output is exponential.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
