Подсчет количества четверок целых чисел

Question

Я видел этот вопрос сегодня, где нам нужно посчитать количество четверок целых чисел (X1, X2, X3, X4)так, что Li ≤ Xi ≤ Ri для i = 1, 2, 3, 4 и X1 ≠ X2, X2 ≠ X3, X3 ≠ X4, X4 ≠ X1.

    input:
     Li Ri
     1  4 
     1  3 
     1  2 
     4  4

output:
8

1 2 1 4
1 3 1 4
1 3 2 4
2 1 2 4
2 3 1 4
2 3 2 4
3 1 2 4
3 2 1 4

Мои первые мысли были использованы

Принцип исключения включения

Мне удалось найти число, если число мест не ограничено, но я не могу понять, как мы можем найти оставшиеся условия для достижения окончательного решения. Также я узнал, что этот вопрос можно решить с помощью DFS .

Как мы можем сделать этот вопрос с включением исключения / DFS

Answer 1

Включение / Исключение даст вам количество четверок, но не даст сами четверки.

Пусть Ai - множество четверок, удовлетворяющих Lj<=Xj<=Rj для всех j, причем Xi=X(i+1) (где индексы циклические, поэтому X5 означает X1). В приведенном вами примере

A1 = { (1114), (1124), (2214), (2224), (3314), (3324) }
A2 = { (1114), (2114), (3114), (4114), (1224), (2224), (3224), (4224) }
A3 = { } (empty set)
A4 = { (4114), (4214), (4314), (4124), (4224), (4324) }

Нам также нужны пересечения пар множеств:

A1 cap A2 = { (1114), (2224) } (note first three numbers identical)
A1 cap A3 = { }
A1 cap A4 = { } (can't have X4=X1=X2)
A2 cap A3 = { }
A2 cap A4 = { (4114), (4224) }
A3 cap A4 = { }

Пересечения троек множеств:

A1 cap A2 cap A3 = { }
A1 cap A2 cap A4 = { }
A1 cap A3 cap A4 = { }
A2 cap A3 cap A4 = { }

И пересечение всех множеств:

A1 cap A2 cap A3 cap A4 = { }

Включение / исключение в его дополнительной форме говорит нам, что

|intersection of complements of Ai| = |unrestricted quadruples| 
- sum of |Ai| + sum of |Ai cap Aj| - sum of |Ai cap Aj cap Ak| 
+ sum of |Ai cap Aj cap Ak cap Al|

где ни один из индексов i,j,k,l не равен. В вашем примере

|intersection of complements of Ai| = 4x3x2x1 - (6+8+0+6) + (2+0+0+0+2+0) - (0+0+0+0) + 0 
= 24 - 20 + 4 - 0 + 0 = 8

Для того чтобы найти |Ai| и их пересечения, вы должны найти пересечения интервалов [Li,Ri] и умножить длины пересечений на длины неограниченных интервалов. Например,

|A1| = |[1234] cap [123]| x |[12]| x |[4]| = 3 x 2 x 1 = 6
|A2 cap A4| = |[123] cap [12]| x |[4] cap [1234]| = |[12]| x |[4]| = 2 x 1 = 2

Я не вижу, какой глубинный первый поиск связан с этим в этом подходе.

Answer 2

Это зависит от того, являются ли наборы непересекающимися или общими элементами. Для n = 4, то есть в четыре раза, как вы и просили, я думаю, что я сократил его от 1 до 4 итераций, если мы передадим концы четырем типам, описывающим x_1 является членом X2 а также x_4 член X3,

Пример с тремя итерациями:

input = {1,2,3}{1,2}{1,2,3}{3,4}

2 * (1)(12)(123)(3) = (1)(2)(1)(3) = 2 * 1          // x_1 ∈ X2, x_4 ∈ X3
2 * (1)(12)(123)(4) = (1)(2)(13)(4) = 2 * 2          // x_1 ∈ X2, x_4 ∉ X3
1 * (3)(12)(123)(4) = (3)(12)(12,3)(4) = 1 * (2 + 2)  // x_1 ∉ X2, x_4 ∉ X3
Total = 10

Пример с одной итерацией:

input = {1,2,3,4}{1,2,3,4}{1,2,3,4}{1,2,3,4}          // x_1 ∈ X2, x_4 ∈ X3

12 * (1)(1234)(1234)(2) = (1)(2,34)(134)(2) = 12 * (3 + 4)
Total = 84