0
$\begingroup$

There's a list of (unknown) integers, in [0...20]. They are generated from a uniform distribution via a RNG.

The input is observations of the form:

  • in a subrange [i,j) of the list, and some given threshold T in [0...20], how many sextuples exist (not necessarily of consecutive numbers) consisting of numbers that are less than T.

Example: [0..12), there are 0 sextuples of numbers < 2 This means that for the 12 first numbers of the list, there don't exist 6 numbers which are all less than 2. Another way to view this would be that there exist at least 7 numbers in this range that are >= 2.

Another example: [0..18), there are 1 sextuples of numbers < 7

For the 18 first numbers of the list, there exists one sextuple of numbers that are less than 7 (there could be up to 11 such numbers, but not 12, otherwise there would be two sextuples). Another way to state this would be that, for this range, there exist at least 7 numbers which are >= 7.

Here's an example input, describing known facts about a list of 102 unknown numbers in [0..20] [0..12), there are 0 sextuples of numbers < 2 [0..60), there are 1 sextuples of numbers < 2 [0..18), there are 1 sextuples of numbers < 7 [0..36), there are 2 sextuples of numbers < 7 [0..30), there are 1 sextuples of numbers < 8 [0..36), there are 2 sextuples of numbers < 8 [0..60), there are 3 sextuples of numbers < 8 [0..18), there are 1 sextuples of numbers < 9 [0..42), there are 3 sextuples of numbers < 9 [0..30), there are 2 sextuples of numbers < 10 [0..36), there are 2 sextuples of numbers < 10 [0..60), there are 4 sextuples of numbers < 10 [0..42), there are 4 sextuples of numbers < 13 [0..60), there are 5 sextuples of numbers < 13 [12..72), there are 6 sextuples of numbers < 14 [18..42), there are 1 sextuples of numbers < 10 [18..42), there are 2 sextuples of numbers < 12 [30..60), there are 1 sextuples of numbers < 8 [30..60), there are 2 sextuples of numbers < 11 [36..66), there are 2 sextuples of numbers < 8 [36..66), there are 3 sextuples of numbers < 11 [36..66), there are 3 sextuples of numbers < 12 [42..102), there are 1 sextuples of numbers < 2 [42..102), there are 1 sextuples of numbers < 2 [42..66), there are 1 sextuples of numbers < 7 [42..78), there are 2 sextuples of numbers < 7 [42..102), there are 3 sextuples of numbers < 7 [42..78), there are 2 sextuples of numbers < 8 [42..66), there are 2 sextuples of numbers < 10 [42..72), there are 2 sextuples of numbers < 10 [42..78), there are 3 sextuples of numbers < 10 [42..84), there are 3 sextuples of numbers < 10 [42..102), there are 5 sextuples of numbers < 10 [42..102), there are 6 sextuples of numbers < 13 [60..72), there are 0 sextuples of numbers < 2 [60..78), there are 1 sextuples of numbers < 7 [60..90), there are 2 sextuples of numbers < 8 [60..78), there are 1 sextuples of numbers < 9 [60..90), there are 2 sextuples of numbers < 11 [60..102), there are 4 sextuples of numbers < 11 [60..102), there are 4 sextuples of numbers < 13 [72..102), there are 1 sextuples of numbers < 8 [78..102), there are 1 sextuples of numbers < 10 [78..108), there are 2 sextuples of numbers < 11 [78..102), there are 2 sextuples of numbers < 12 [84..102), there are 0 sextuples of numbers < 7

The question is, how do I infer as much info as possible for the unknown numbers. The problem may be under-specified. But still, when two subranges overlap (or especially when one is a prefix or suffix of another), then it becomes possible to infer something new, and with enough observations, the unknown numbers could be narrowed down to small margins.

Examples:

[0..18), there are 1 sextuples of numbers < 7 [0..18), there are 1 sextuples of numbers < 9

Here, the second observation can be dropped, the first is more restrictive.

[0..30), there are 1 sextuples of numbers < 8 [0..36), there are 2 sextuples of numbers < 8 Here, the first is a prefix of the second. And both observations are for the same threshold, 8. All numbers of the first range exist in the second range. Hence, we can infer that there exist at least one number in [30..36) which is < 8 (it could be all 6 of them).

[0..12), there are 0 sextuples of numbers < 2 [0..60), there are 1 sextuples of numbers < 2 A similar example. From these two, we can infer that in the range [12..60), there exist {1..6} numbers that are < 2.


Any advice on how I should approach this? I wonder if coding such heuristics will get me anywhere, or I need some more generalized algorithm to help me. This is likely not a polynomial problem, though with enough observations about small subranges (these seem to be the most useful), this may be tractable. But no appropriate algorithm comes to mind. Thanks for any suggestion!

$\endgroup$
  • 1
    $\begingroup$ What's the context where you encountered this problem? Can you credit the source in your question? $\endgroup$ – D.W. Jun 11 '18 at 22:37
  • 1
    $\begingroup$ What does it mean to have 102 unknown numbers in [0..20]? Do you mean that you have a list of length 102, and each item of the list is a number in the range [0..20]? Or something different? $\endgroup$ – D.W. Jun 11 '18 at 22:38
  • 2
    $\begingroup$ When you say "a sextuple of numbers", do you mean six consecutive elements of the array? If so, is twelve consecutive 1s two sextuples or seven? $\endgroup$ – David Richerby Jun 11 '18 at 23:47
  • $\begingroup$ Does a sextuple of numbers have to represent consecutive elements in the list? Can you provide a careful definition of what you mean by "sextuple" and what you mean by "the number of sextuples"? $\endgroup$ – D.W. Jun 12 '18 at 4:43
  • 1
    $\begingroup$ @DimitrisAndreou I guess you mean a multiset rather than a set, since otherwise, there can't be a "sextuple of numbers <2". But now it's impossible to have just two sextuples: e.g., the sequence 1,2,3,4,5,6,7 contains seven sextuples <8 under this definition. So I'm still confused about what the actual setup is. $\endgroup$ – David Richerby Jun 12 '18 at 11:56
1
$\begingroup$

Hint: If you know that there are $n$ sextuples of numbers less than $T$ among the numbers $x_i,\dots,x_j$, you can infer how many numbers less than $T$ there are among $x_i,\dots,x_j$. See if you can figure out how.

That sounds like a very useful first step for your algorithm.

After that, you could apply integer linear programming.

There is not likely to be any polynomial-time algorithm; you can show a reduction from 3SAT with a little creativity.

$\endgroup$
  • $\begingroup$ Sure, that's easy: [0..12), there are 0 sextuples of numbers < 2 --> there are {0..5} numbers < 2, and {7..12} numbers >= 2 [0..60), there are 1 sextuples of numbers < 2 --> there are {6..11} numbers < 2, and {13..54} numbers >= 2 and so on. Thanks for the integer linear programming suggestion, I'll see if I can translate this somehow $\endgroup$ – Dimitris Andreou Jun 12 '18 at 9:15
0
$\begingroup$

I'll use Constraint Programming, via this library: google/or-tools/constraint_solver.h

Given that the ordering of numbers in the sextuples doesn't matter, I'll model it as follows:

S(i,j), a subrange of 6 numbers (starting at a multiple of 6). * i is the index of the range, e.g. S(5) would be subrange [30..36) * j is how many numbers in this range are equal to j

Hence S(0,20) would be "how many 20s exist in the [0..6)".

Obviously 0 <= S(i,j) <= 6, each number can appear at most 6 times in a range of length 6.

Also: Σ(S(i,j)) = 6 for some i, and for j=1..20, i.e. there are exactly 6 numbers in every range of length 6.

Then, given an observation of the form:

In the range [0..12), there is exactly 1 sextuple of numbers < 3 I add a constraint that looks like this:

6 <= S(0,0) + S(0, 1) + S(0, 2) + S(1,1) + S(1, 0) + S(0, 2) < 12 I.e. "if there are 6 numbers in [0..12) that are less than 3, then there have to be at least 6 numbers that are either {0,1,2} in the subranges [0..6) and [6..12). But there can't be 12 such numbers there.

I'm using subranges of length 6 since this is the minimum resolution I can get observations for, and it doesn't make sense to model the problem as if I'm trying to locate the exact ordering of numbers in these subranges, this is always impossible.

The library apparently lets me find multiple solutions iteratively, hopefully I'll get some useful output out of it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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