1
$\begingroup$

Can you help me design an algorithm to solve the following problem in polynomial time?

Let n be a given natural number. We define an input series of length n to be a string of length n which is built by using only the characters F, S and - (hyphen).

At least one F or S is guaranteed to appear in each valid input series.

e.g. For n = 7:

FF---SF is valid

-F-S-FS is valid

SSSFFSS is valid

------- is not valid (only -)

FS-F    is not valid (length)

ABCD--- is not valid (characters)

Any valid input series can be developed by enumerating all the input series of same length, n, such that each "-" (hyphen) of the initial input string changes into either F or S.

e.g. For n = 5,
"FS--F" is developed into:
FSFFF
FSFSF
FSSFF
FSSSF

Each of the above series obtained, through developing the initial serie, will be called a result serie.

Question: given two natural non-zero numbers (n and k) and k valid input series of length n, how many duplicate result series can be found in total?

e.g. 

Input:
k=2, n=4 and the series:
FS-F
FSF-

Output:
1

Explanation: The first serie develops into FSFF and FSSF.

The second serie develops into FSFF and FSFS.

Since FSFF is repeated, the output answer to this exact problem instance will be 1 (since there is only 1 duplicate to an already existing result series).

Point I thought one might consider when designing the poly algorithm:

  • the problem asks for the number of duplicate result series and not for their actual content or value

Do you have any strategy that could determine the duplicate number avoid some weird brute force approach?

Thank you for your help!

$\endgroup$
2
  • $\begingroup$ I don't understand the problem statement. I don't know what you mean by "how many duplicate result series can be found in total". Where did you encounter this task? Can you credit the original source? I notice that you got comments on Stack Overflow; I encourage you to revise your question based on that feedback. $\endgroup$
    – D.W.
    Feb 5, 2022 at 3:01
  • $\begingroup$ By duplicate result series I mean any string of length n, for given n, that is a result serie for two or more input series given beforehand. In this case, if Q duplicate result series are encountered, only 1 is supposed to be counted. The origin of the task has no justified importance as this could be a problem like any other. In contrast of your healthy feedback, "Brute force wordle" and "why is this problem tagged like this in SO" doesn't seem to be a feedback I can actually make use of, unfortunately. Thank you for your question and waiting for any idea you encounter based on my response :D $\endgroup$
    – coolest 10
    Feb 5, 2022 at 9:59

2 Answers 2

0
$\begingroup$

When $k = 2$, we can proceed as follows.

If the two given inputs disagree on one of the positions (one of them contains F and the other contains S), then there will be no intersection.

Otherwise, the answer is $2^m$, where $m$ is the number of positions in which both inputs have $-$.

$\endgroup$
0
$\begingroup$

No polynomial-time algorithm is possible unless $P = \sharp P$.

I reduce the $\sharp P$-complete problem of counting the number of variable assignments satisfying a DNF formula.

Let $n$ be the number of variables. For a conjunctive clause, compute a pattern of length $n$. The $i$'th character of the pattern is "F" if the clause contains variable $i$ as a positive literal, "S" if for a negative literal, "-" otherwise.

A string is associated with a variable assignment. Set true for "F", false for "S". A pattern computed from a conjunctive clause develops to a string if and only the variable assignment satisfies the clause.

In addition to the computed patterns for the set of conjunctive clauses, a "-"-only pattern of length $n$ is added.

The "-"-only pattern develops every string. Thus, a string is a duplicate if and only if the corresponding variable assignment satisfies the DNF formula.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.