Каков эффективный алгоритм определения образующих множеств, произведение которых содержит все необходимые перестановки?
Рассмотрим список перестановок (релевантных для заказа комбинаций) в форме:
(1 2 3)
(1 2 4)
(5 2 3)
(5 2 4)
Мне нужно найти наименьшее количество генерирующих множеств для этой группы перестановок. Например, учитывая приведенные выше перестановки,
(1 2 3,4)
(5 2 3,4)
Это не оптимальное решение. Оптимальным решением является (1,5 2 3,4).
Вы заметите, что это решение содержит множества A={1, 5} B={2} и C={3,4} Исходный список перестановок - это упорядоченное декартово произведение этих множеств: A X B X C.
Я хотел бы разделить список перестановок на наименьшее количество возможных групп, выраженных в виде множеств A, B и C, произведение которых содержит все перестановки в списке. Окончательным ответом обычно является, но не всегда, список списка наборов, поскольку не всегда возможно сократить список перестановок до единого списка генерирующих наборов. То есть обычно это тот случай, когда произведение наборов A, B и C учитывает некоторые перестановки в списке, но наборы D, E и F необходимы для учета других перестановок в списке и т. Д.,
Моя грубая попытка решить эту проблему состояла в том, чтобы проверить, совпадал ли я с любым из двух слотов перестановок в списке, и рекурсивно объединить их. Если это так, я объединил эти две комбинации, т.е.
(1 2 3)
(1 2 4)
производить
(1 2 3,4)
К сожалению, порядок объединения таких комбинаций не является ассоциативным. Идеальным решением было бы объединить эти комбинации таким образом, чтобы окончательный список множеств включал максимально возможное число перестановок.
Чтобы продемонстрировать проблему с ассоциативностью, возьмем этот пример, который не может быть сокращен до двух списков генерирующих наборов:
(1 2 4)
(1 2 3)
(1 2 5)
(5 2 3)
(5 2 4)
Предположим, вы должны были рекурсивно объединить их в соответствии со следующим правилом: "Если какие-либо два столбца совпадают, я объединяю, сохраняя эти столбцы как есть. Затем я объединяю два набора в третьем столбце, чтобы создать новый набор. После слияния этих двух строк я выбрасываю две исходные строки, чтобы они не были повторно объединены или не пересчитаны дважды ". Порядок этих слияний имеет большое значение. Учитывая приведенный выше список перестановок, если я объединю (1 2 3) и (1 2 4), я получу (1 2 3,4). Теперь, как мне провести следующее слияние для оптимизации генераторной установки? Предположим, я смотрю на (1 2 5) и вижу, что он совпадает с (1 2 3,4) в двух столбцах, я выполняю слияние и получаю (1 2 3,4,5). Кажется, все хорошо. Однако затем я объединяю (5 2 3) и (5 2 4), что приводит к (5 2 3,4). Я сравниваю (5 2 3,4) и (1 2 3,4,5). У меня нет совпадения с двумя столбцами, поэтому я прекращаю слияние. Я бы сократил выходной сигнал до (5 2 3,4) и (1 2 3,4,5).
Теперь предположим, что я слился в другом порядке. Я объединяю (1 2 3) и (1 2 4) для получения (1 2 3,4). Затем я объединяю (5 2 3) и (5 2 4) для получения (5 2 3,4). Я вижу, что у меня есть совпадение между этими двумя продуктами. Затем я объединяю (1 2 3,4) и (5 2 3,4) для получения (1,5 2 3,4). Окончательный список генераторных установок (1,5 2 3,4) и (1 2 5). Итак, вы видите, что порядок объединения дал два разных ответа: (1,5 2 3,4) и (1 2 5) против (5 2 3,4) и (1 2 3,4,5).
В этом случае я, вероятно, согласился бы с любым ответом, поскольку в каждом ответе встречается одинаковое количество (2) списков образующих множеств. Однако (1,5 2 3,4) и (1 2 5) несколько предпочтительнее, поскольку (1,5 2 3,4) включает наибольшее возможное количество комбинаций. Предположим, однако, что у нас есть список из 900 комбинаций. Порядок слияния восходящего решения проблемы приведет к неоптимальному уменьшению проблемы, когда оптимизация - это наименьшее возможное число в списке списка наборов. Трудно понять, что такое порядок слияния, не просматривая все возможные пути слияния, который не более эффективен, чем метод грубой силы поиска совпадений, который я также попробовал.
Я также попробовал метод грубой силы. Почему эффективность метода грубой силы недопустима? Этот метод сначала находит список уникальных целых чисел во всех столбцах. Затем он генерирует набор мощности каждой возможной комбинации этих целых чисел. Это делается для столбца / набора A, столбца / набора B и столбца / набора C. Затем он упорядочивает эти наборы по размеру (от наибольшего к наименьшему), вычисляет декартово произведение каждого набора по каждому другому набору в других столбцах, затем проходит по этим декартовым произведениям, которые определяются их генерирующими наборами, чтобы проверить, соответствует ли декартово произведение списку перестановок из входных данных. Это примерно O(n^3), где n= количество комбинаций в списке ввода. Если бы я мог сделать это даже за O(n^2), это было бы победой по сравнению с тем, что есть сейчас.
Что касается соображений памяти. Предположим, что доменом для каждого слота являются целые числа 1-12. Количество различных комбинаций в трех слотах составляет 12!/3! Вы просматриваете более 79 миллионов необработанных комбинаций. Это еще до того, как они были разделены на наборы API Google Guava Collection (который я настоятельно рекомендую, кстати). Возможно, мы могли бы как-то сгенерировать набор лениво, и я чувствую, что Google это делает, но ограничения памяти все еще велики.
Я действительно ищу алгоритм для решения этой проблемы. Однако, если есть библиотека или метод Java, которые позаботятся об этом с минимальными трудностями, я тоже за это. Благодарю.
1 ответ
Спасибо всем за ваши идеи и ответы. Я хотел бы выразить благодарность за этот ответ Джону Колену ( http://www.johnfkolen.com/), который представил следующее возможное решение:
Жадный алгоритм максимального покрытия троек
Входные данные: набор с подмножествами A x B x C троек, где A, B и C - наборы целых чисел.
Вывод: набор из n троек (A_i, B_i, C_i), где A_i в A, B_i в B и C_i в C, и Union_i A_i x B_i x C_i = X и пересечение_i A_i x B_i x C_i = пусто.
Алгоритм
Алгоритм можно разбить на три части: поиск парных покрытий, поиск тройных покрытий и, наконец, построение полного покрытия.
Поиск покрытий пар из подмножества B x C включает построение карты из элементов B в наборы C. По сути, это небольшое дерево префиксов, или три, эта структура данных позволяет легко найти максимальное покрытие набора префиксов. Например, если b_1->C_1 и b_2->C_2, то максимальное покрытие с участием b_1 и b_2 будет <[b_1, b_2], пересечение C_1 C_2>.
Как только мы сможем найти максимальные пары, то можно построить максимальные тройки. Однако на этот раз префикс (A) отображается на набор пар (BxC). Используя предыдущий метод, можно найти исследовать все подмножества A и охват их совпадающих пар над суффиксами.
Жадный подход находит лучшее локальное покрытие и добавляет его в набор решений. Тройки, захваченные текущей обложкой, снимаются с рассмотрения, и процесс продолжается до тех пор, пока местная лучшая обложка не станет одиночной. Оставшиеся тройки добавляются к решению.
Соответствующий код прилагается.
import java.io.IOException;
import java.io.FileReader;
import java.io.BufferedReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.Arrays;
class Triples {
private ArrayList<int[]> _data;
private HashMap<Integer,HashSet<Integer>> _tree;
/**
* Instantiates a container of triples read from the provided file.
* <p>
* File should contain lines of the form '[#,#,#]', where # is an
* integer. Spaces are ignored.
*
* @param filename a path to a file containing triples
*/
public Triples(String filename) {
_data = new ArrayList<int[]>();
_tree = new HashMap<Integer, HashSet<Integer>>();
readfile(filename);
}
/**
* Returns the number of triples.
*
* @return the number of triples.
*/
int size() {
return _data.size();
}
/**
* Returns a set of encoded pairs (b,c) where (first, b, c) is in the
* set of triples. The pairs are encoded as integers using b * 255 + c.
*
* @param first the first value of a triple
* @return a set of pair encondig
*/
HashSet<Integer> tree(int first) {
return _tree.get(first);
}
public class PairCover
{
public ArrayList<Integer> a;
public ArrayList<Integer> b;
PairCover()
{
a = b = null;
}
PairCover(ArrayList<Integer> ax, ArrayList<Integer> bx)
{
a = ax;
b = bx;
}
/**
* Returns the number of pairs covered by this cover.
*
* @return the number of pairs covered by this cover.
*/
public int score()
{
if (a != null && b != null)
return a.size() * b.size();
else
return 0;
}
public String toString() {
return "<"+a+","+b+">";
}
}
/**
* Compute the maximal pair covering (B,C) for a set of suffix pairs.
*
* @return pair covering where |BxC| is maximized.
*/
public PairCover maxPairCover(HashSet<Integer> set) {
// unpack the pairs
HashMap<Integer,NSet> pairs = new HashMap<Integer,NSet>();
for(Integer value : set) {
Integer a = value / 256;
Integer b = value & 255;
if (!pairs.containsKey(a))
pairs.put(a, new NSet());
pairs.get(a).add(b);
}
_mpc_best = new PairCover();
Integer[] remain_ary = pairs.keySet().toArray(new Integer[0]);
// recursively examine all subsets pair first values and find matching
// second value groups.
maxPairCoverRec(pairs,
new ArrayList<Integer>(),
new ArrayList<Integer>(Arrays.asList(remain_ary)),
null);
return _mpc_best;
}
/**
* Recursively compute the maximal pair covering (B,C) for a set of
* suffix pairs from a set of active prefixes by combining all possible
* subsets of the remaining prefixes.
* <p>
* Stores the best pair cover in _mpc_best. This "global" variable makes it
* easy to prune search.
*
* @param pairs tree-compressed set of pairs
* @param active currently active pair prefixes
* @param remain set of pair prefixes to explore
* @param set the pair suffixes shared by all the active prefixes
* @return pair covering where |BxC| is maximized.
*/
void maxPairCoverRec(HashMap<Integer,NSet> pairs,
ArrayList<Integer> active,
ArrayList<Integer> remain,
NSet set)
{
if (set != null) {
// Prune search if suffix set is empty or that there is no way
// to generate a better pair cover than the current cover.
if (set.isEmpty() ||
(active.size() + remain.size()) * set.size()
<= _mpc_best.score())
return ;
}
if (remain.isEmpty()) {
if (active.size() > 0) {
// Save the current pair cover if it's better than the current
// cover.
if (_mpc_best.score() < set.size() * active.size()) {
_mpc_best.a = (ArrayList<Integer>)(active.clone());
_mpc_best.b = (ArrayList<Integer>)(set.to_array_list());
}
}
return;
}
ArrayList<Integer> active_r = (ArrayList<Integer>)(active.clone());
ArrayList<Integer> remain_r = (ArrayList<Integer>)(remain.clone());
Integer a = remain_r.remove(0);
// Explore active sets without element a.
maxPairCoverRec(pairs, active_r, remain_r, set);
// Explore active sets with element a. Perform intersection of
// current suffix set with suffixes of a.
if (set == null) {
set = pairs.get(a);
}
else {
set = set.intersection(pairs.get(a));
}
active_r.add(a);
maxPairCoverRec(pairs, active_r, remain_r, set);
}
public class TripleCover
{
public ArrayList<Integer> a;
public ArrayList<Integer> b;
public ArrayList<Integer> c;
TripleCover()
{
a = b = c = null;
}
TripleCover(ArrayList<Integer> ax,
ArrayList<Integer> bx,
ArrayList<Integer> cx)
{
a = ax;
b = bx;
c = cx;
}
TripleCover(int ax,
int bx,
int cx)
{
a = new ArrayList<Integer>();
a.add(ax);
b = new ArrayList<Integer>();
b.add(bx);
c = new ArrayList<Integer>();
c.add(cx);
}
/**
* Returns the number of pairs covered by this cover.
*
* @return the number of pairs covered by this cover.
*/
public int score()
{
if (a != null && b != null && c != null)
return a.size() * b.size() * c.size();
else
return 0;
}
public String toString() {
return "<"+a+","+b+","+c+">";
}
}
/**
* Compute the maximal triple cover for the pairs currently stored
* in _tree.
*
* @return a triple cover with |AxBxC| maximized
*/
TripleCover maxTripleCover() {
_mtc_best = new TripleCover();
Integer[] remain_ary = _tree.keySet().toArray(new Integer[0]);
ArrayList<Integer> remain =
new ArrayList<Integer>(Arrays.asList(remain_ary));
maxTripleCoverRec(new ArrayList<Integer>(),
remain,
null);
return _mtc_best;
}
/**
* Recursively explore all subsets of values in first position and
* find the largest cover for the second and third positions.
* <p>
* Stores the best triple cover in _mtc_best. This "global" variable
* makes it easy to prune search.
*
* @param active the active values of the first position
* @param remain the additional values of the first position to explore
* @param set the current set of second/third position pairs that are shared by the active values
*/
void maxTripleCoverRec(ArrayList<Integer> active,
ArrayList<Integer> remain,
HashSet<Integer> set) {
if (set != null &&
(set.isEmpty() ||
(remain.size()>0 &&
(active.size() + remain.size()) * set.size()
<= _mtc_best.score()))){
return;
}
if (remain.isEmpty()) {
if (active.size() > 0) {
PairCover mpc = maxPairCover(set);
if (_mtc_best.score() < mpc.score() * active.size()) {
_mtc_best.a = (ArrayList<Integer>)(active.clone());
_mtc_best.b = mpc.a;
_mtc_best.c = mpc.b;
}
}
return;
}
ArrayList<Integer> active_r = (ArrayList<Integer>)(active.clone());
ArrayList<Integer> remain_r = (ArrayList<Integer>)(remain.clone());
Integer a = remain_r.remove(0);
maxTripleCoverRec(active_r, remain_r, set);
if (set == null) {
set = (HashSet<Integer>)(_tree.get(a).clone());
}
else {
set = (HashSet<Integer>)(set.clone());
set.retainAll(_tree.get(a));
}
active_r.add(a);
maxTripleCoverRec(active_r, remain_r, set);
}
/**
* Finds a covering set for the triples using a greedy approach.
* The largest cover of the current triples is found, recorded, and
* the affected triples are removed from consideration. This process
* continues until singleton covers are left.
*
* @return a list of covers
*/
ArrayList<TripleCover> greedy() {
// Since the prefix tree is modified as new covers are found,
// we make a copy
HashMap<Integer,HashSet<Integer>> old_tree = _tree;
_tree = (HashMap<Integer,HashSet<Integer>>)(_tree.clone());
ArrayList<TripleCover> solution = new ArrayList<TripleCover>();
TripleCover cover;
do {
cover = maxTripleCover(); // find best
solution.add(cover); // record it
remove(cover); // remove covered triples from tree
System.out.println("" + cover + " ==> " + cover.score());
} while (cover.score() > 1);
// Nothing left but singletons, so add them to solution
for(Integer a : _tree.keySet()) {
for(Integer pair : _tree.get(a)) {
int b = pair / 256;
int c = pair & 255;
solution.add(new TripleCover(a,b,c));
}
}
// restore prefix tree
_tree = old_tree;
return solution;
}
//************************************************************
private PairCover _mpc_best;
private TripleCover _mtc_best;
/**
* Reads triples from the specified file. Will exit if file does not
* exist.
*
* @param filename a path to a file containing triples
*/
private void readfile(String filename) {
try {
FileReader fr = new FileReader(filename);
BufferedReader reader = new BufferedReader(fr);
String line = null;
while ((line = reader.readLine()) != null) {
line = line.replace("[","").replace("]","").replace(" ","");
String[] svalues = line.split(",");
int[] values = new int[3];
values[0] = Integer.parseInt(svalues[0]);
values[1] = Integer.parseInt(svalues[1]);
values[2] = Integer.parseInt(svalues[2]);
_data.add(values);
Integer key = new Integer(values[0]);
if (!_tree.containsKey(key)) {
_tree.put(key, new HashSet<Integer>());
}
_tree.get(key).add(values[1] * 256 + values[2]);
}
} catch (IOException e) {
System.out.println("Could not open " + filename);
System.exit(1);
}
}
/**
* Removes covered triples from the prefix tree
*
* @param tc a covering
*/
private void remove(TripleCover tc) {
for(Integer a : tc.a) {
HashSet<Integer> set = _tree.get(a);
for(Integer b : tc.b) {
for(Integer c : tc.c) {
set.remove(b * 256 + c);
}
}
if (set.isEmpty()) {
_tree.remove(a);
}
}
}
}