Unique numbers with missing digits

user_13978265 0
Viewed 89

I have this problem that I must solve in time that is polynomial in N, K and D given below:

Let N, K be some natural numbers. Then a, b, c ... are N numbers of exactly K digits each.

a, b, c ... contain only the digits 1 and 2 in some order given by the input.

Although, there have only D digits that are visible, the rest of them being hidden (the hidden digits will be noted with the character "?").

There may be different numbers such that one or more of a, b, c ... are generalizations of the said number:

e.g.

  • 2?122 is a generalization for 21122 and 22122
  • 2?122 is not a generalization for 11111
  • 12??? and ?21?? are both generalizations for 12112
  • ???22 and ???11 cannot be generalizations of the same number

Basically, some number is a generalization of the other if the latter can be one of the "unhidden" versions of the former.

Question:

How many different numbers there are such that at least one of a, b, c or ... is their generalization?***

Quick Reminder:

  • N = nº of numbers

  • K = nº of digits in each number

  • D = nº of visible digits in each number

Conditions & Limitations:

  • N, K, D are natural numbers

  • 1 ≤ N

  • 1 ≤ D < K

Input / Output snippets for verification of the algorithm:

  • Input:
    N = 3, K = 5, D = 3
    
    112??
    ?122?
    1?2?1
  • Output:
    8

  • Explanation:

    The numbers are 11211, 11212, 11221, 11222, 12211, 12221, 21221, 21222, which are 8 numbers.

    • 11211, 11212, 11221, 11222 are the generalizations of 112??
    • 11221, 11222, 21221, 21222 are the generalizations of ?122?
    • 11211, 11221, 12211, 12221 are the generalizations of 1?2?1

  • Input:

    N = 2, K = 3, D = 1

    1??
    ?2?
  • Output:
    6

  • Explanation:

    The numbers are 111, 112, 121, 122, 221, 222, which are 6 numbers.

From my calculations, I found out that there are 2^(K-D) possible numbers in total that have a as their generalization, 2^(K-D) possible numbers in total that have b as their generalization etc., leaving me with N*2^(K-D) numbers.

My big problem is that I found cases where a number has multiple generalizations and therefore it repeats inside N*2^(K-D), so the real nº of different numbers will be, in this case, something smaller than N*2^(K-D).

I don't know how to find only the different numbers and I need your help.

Thank you very much!

EDIT: Answer to «n. 1.8e9-where's-my-share m.»'s question from the comments:

If you have two generalisations, can you find out how many numbers they both generalise?

For two given general numbers a and b (general meaning that they both contain "?"), it is possible to find nº of numbers generalised by both a and b in polynomial time by using the following logic:

1 - we declare some variable q = 1

2 - we start "scanning" the digits of the two numbers simultaneously from left to right:

2.1 - if we find two unhidden digits and they are different, then no numbers are generalized by both a and b and we return 0

2.2 - if we find two hidden digits, then we multiply q by 2, since of the two general numbers result to both generalize some number, that number can have 1 or 2 in place of "?", therefore for each "?" we double the numbers that can be generalized from both a and b as long as step 2.1 is never true.

3 - if scanned all the digits and step 2.1 was never true, then we return 2^q

Therefore, the nº of numbers both a and b generalize is 0 or 2^q, according to the cases presented above.

bit-manipulation complexity-theory time-complexity algorithm string
1 Answers

Unfortunately, this is impossible to do in polynomial time (unless P=NP, and maybe not even then.) Your problem is equivalent to the problem of counting satisfying assignments to a formula in Disjunctive Normal Form, called the DNF counting problem. DNF counting is Sharp-P-hard, so a polynomial time solution could be used to solve all problems in NP in polynomial time too (and more).

To see the relationship, note that each pattern is equivalent to an AND of several literals. If you take '1' in a position to be a literal, and '2' in that position to be that literal negated, you can convert it to a disjunctive clause.

For example:

1 1 2 ? ?
becomes
(x_1 ∧ x_2 ∧ ¬x_3)

? 1 2 2 ?
becomes
(x_2 ∧ ¬x_3 ∧ ¬x_4)

1 ? 2 ? 1
becomes
(x_1 ∧ ¬x_3 ∧ x_5)

The question of how many numbers satisfy at least one of these patterns is exactly the question of how many assignments satisfy at least one of the equivalent clauses.

user_167571740
Related