Как структурировать эту проблему удовлетворения ограничений?

Question

Это продолжение моего вопроса здесь: https://math.stackexchange.com/questions/3278359/figuring-out-the-underlying-construction-of-a-final-set

Чтобы повторно опубликовать вопрос более CS-способом, как бы вы нашли A, если бы только дали B?

$ A = [ 1, 5, 10 ]
$ B = f(A)
$ B == [ 1, 5, 6, 10, 11, 15, 16 ]
(true)
$ B == { 1, 5, 10, 5+1, 10+1, 10+5, 10+5+1 }
(true)
$ solve(B)
[ 1, 5, 10 ]

f() находит набор уникальных значений из всех непустых комбинаций.

Поскольку A всегда является подмножеством B, я предполагаю, что может быть грубая силаметод, в котором вы пытаетесь каждую комбинацию элементов в B (это не все элементы B,), пока вы не решите для всего набора.Но это было бы крайне неэффективно.(Я представляю что-то вроде факториала порядка N ...) Поскольку существует несколько решений, вам нужно либо вычислить весь набор, либо остановиться после определенного порога.

После некоторого обсуждения в комментарияхЯ считаю, что это проблема удовлетворения ограничений.Как это будет структурировано?(Псевдокод в порядке.)

Для мега бонусных очков: как это можно решить, если предположить, что A не подмножество B?

Например:

$ B = [15, 16, 15.5, .5, 10.5]
$ solve(B)
[.5, 1, 5, 10]

Другой способ сформулировать этот вопрос: как будет выглядеть алгоритм сжатия без потерь, который находит наименьший набор базовых значений?(Отображение между базовыми значениями и выходными данными можно игнорировать.)

Answer 1

Если номер элемента в A равен n, тогда номер элемента в B будет (2 ^ n) -1.
Это означает, что номер элемента в B равен числу всех возможных подмножеств A.

Например

если A = {a, b, c}
тогда B = {a, b, c, a + b, a + c, b + c, a + b + c}

Чтобы получить все элементы B, мы можем перебрать от 1 до (2 ^ n) -1.
Теперь из каждого числа будем вычислять разные элементы B.

Пусть
А = {а, Ь, с}. * +1014 * n = 3, номер элемента в A

   For each i from 1 to 2^n-1, we will check each bit(j) of i from 0 to n-1.
   if jth bit is 1, we will take jth element of A for finding ith element of B.
   Such way we will add some number from A for finding ith element such that
   their index's bit in i is 1.

Например,

1   001     B[0]=a
2   010     B[1]=b
3   011     B[2]=a+b
4   100     B[3]=c
5   101     B[4]=a+c
6   110     B[5]=b+c
7   111     B[6]=a+b+c

Таким образом, общая сложность будет n * 2 ^ n.

Псевдокод:

b=[]
for i in (from 1 to 2^n-1):
   ith=0
   for j in(from 0 to n-1)
       if(jth bit in i is 1)
           ith+=A[j]
   #inner_loop_end
   b.append(ith)