Обеспечение применения только одной формулы к 4 случайным элементам

Question

У меня есть список формул для объединения элементов:

A + B + C = X
D + E + F = Y
G + H + I = Z

Я хочу убедиться, что при любых случайных 4 элементах никогда не будет более 1 применимой формулы.Например, приведенные ниже формулы не должны быть разрешены, как если бы я получил элементы A, B, C и D, тогда применимы оба:

A + B + C = X
B + C + D = Y

Каждая формула будет состоять из 3 элементов в LHS, и это LHS, которыйЯ хочу применить правило на.Элементы могут быть отсортированы, если это поможет.

---

Альтернативная, эквивалентная проблема:

У меня есть список массива из 3 элементов: List<Element[3]> Как мне убедиться, что нет2 элемента появляются в более чем одном массиве.

---

Каков был бы достаточно эффективный (быстродействующий) способ сделать это для большого количества элементов и большого количества для формул (кроме грубой форсировки)?

Answer 1

По сути, это сводится к проблеме исключения: из ваших примеров данных,

• , первая формула работает на множестве (A, B, C, X) или, возможно, (A, B, C) если X является константой
• , вторая формула работает с (D, E, F, Y) или (D, E, F)
• и т. д.

и вы хотите убедиться, что любая новая запись в списке

• не работает с набором, уже имеющимся в списке (например, (A, B, C [, X]))
• Не работает с подмножеством записи, уже имеющейся в списке (например, (A, B)), так как в этом случае входной кортеж (A, B, C [, X]) будет работать на ужесуществующая формула И новая

В зависимости от размера кортежей создание исчерпывающего списка подмножеств может быть дорогим или не очень

Это должно работать на небольших наборах (дешевый списокподмножества)

Keep dictionary of formulas
On new formula
  Normalize variable list (e.g. (D,A,c)=>"ACD")
  Check if normalized variable list exists in dictionary
  If it exists, reject new formula and break
  For all subsets of variable list
    Check if normalized variable list of subset exists in dictionary
    If it exists, reject new formula and break
  End For
End On

Answer 2

Это решение основано на решении Майкла Дж. Барбера.

1. Инициализация хеш-таблицы

2. Если у вас есть уравнение с M переменными, добавьте все комбинации с размером M-1 в хеш-таблицу. Например: для A + B + C + D = Z добавьте (A, B, C), (A, B, D), (A, C, D) и (B, C, D)

3. Если вы хотите проверить возможность нового уравнения с M переменными, проверьте, все ли подмножества M-1 НЕ включены в хеш.

Сложность: O (mnlog (mn)).

Answer 3

Вы можете представить ограничения на систему уравнений в виде графика.Вершины - это элементы с n[i] элементами в уравнении i.Таким образом, для уравнения i существует n[i]*(n[i]-1)/2 пары элементов;они становятся краями.Перебирайте уравнения, добавляя ребра на график.В любое время, когда вы захотите добавить ребро, которое уже присутствует, вы обнаружите конфликт.

Для каждого ребра вы можете хранить набор чисел уравнений, которые будут генерировать ребро;это позволяет идентифицировать конкретные конфликты, а не только наличие конфликтов.

Пусть N - количество уравнений, а M - количество элементов в уравнении с наибольшим количеством элементов.Временная сложность равна O(M^2*N), как и сложность пространства.Если все уравнения имеют фиксированное число элементов, использование времени и пространства будет, таким образом, O(N).

Answer 4

Возможно, вы могли бы использовать некоторые из операций набора LINQ.Поскольку вы описали свою проблему как наличие списка списков, желая «обеспечить, чтобы не было 2 элементов в более чем одном списке», , это также не может быть описано как проверка, существует ли пересечение между какими-либоиз списков?Или я немного ушел?

У Джеймса Майкла Хэра есть хорошая статья о различных операциях над множествами , доступных в LINQ.Вы могли бы начать, посмотрев туда: -)

Answer 5

Сохраните ваши значения в матрице и убедитесь, что matrix [i] [j]! = Matrix [k] [j] с i! = K.

Обновление:

Этот подход часто используется при решении задач линейных уравнений. Элементы в матрице представляют собой коэффициенты полиномиальных функций. Затем вы можете работать между строками, чтобы преобразовать матрицу в специальные формы.

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

Преимущество этого подхода в том, что он наиболее эффективен, но вам необходимо правильно обрабатывать начальный размер и стратегию изменения размера.

Обновление 2:

A + B + C = X
B + C + D = Y

m[0][1] = B
m[1][0] = B

Этот пример разбивает матрицу правил [i] [j]! = Matrix [k] [j] на i! = K

Тогда вы не можете использовать формулы B + C + D = Y из-за A + B + C = X.

Answer 6

Вы можете определить эту проблему с другой стороны: нет пары формул, в которой объединение элементов содержит менее 5 элементов. Что указывает на алгоритм, который сравнивает каждую пару формул, если они проходят этот тест. Я знаю, что это грубая сила, но я не могу себе представить ничего лучшего, атм.