algorithm - tiene - Algoritmo eficiente para encontrar todos los subconjuntos máximos
subconjuntos de 1 2 3 4 (4)
En la parte superior de mi cabeza hay un O (D * N * log (N)) donde D es el número de números únicos.
La función recursiva "ayudante" funciona de la siguiente manera: @arguments es conjuntos y dominio (número de números únicos en conjuntos): Casos base:
- Si el dominio está vacío, regrese
- Si los conjuntos están vacíos o los conjuntos tienen una longitud igual a 1, devuelve
Caso iterativo
- Eliminar todos los conjuntos vacíos de conjuntos
- Elige un elemento D en el dominio
- Eliminar D del dominio
- Separe los conjuntos en dos conjuntos (set1 y set2) en función de si el conjunto contiene D
- Retire D de cada conjunto en conjuntos
- Establecer resultado = unión (ayudante (set1, dominio), ayudante (set2, dominio))
- Para cada conjunto en set1 agregar D atrás
- resultado de retorno
Tenga en cuenta que el tiempo de ejecución depende de la implementación del conjunto utilizado. Si se utiliza una lista doblemente enlazada para almacenar el conjunto, entonces:
Los pasos 1-5,7 toman O (N) La unión del paso 6 es O (N * log (N)) al ordenar y luego fusionar
Por lo tanto, el algoritmo general es O (D * N * log (N))
Aquí está el código java para realizar lo siguiente
import java.util.*;
public class MyMain {
public static Set<Set<Integer>> eliminate_subsets(Set<Set<Integer>> sets) throws Exception {
Set<Integer> domain = new HashSet<Integer>();
for (Set<Integer> set : sets) {
for (Integer i : set) {
domain.add(i);
}
}
return helper(sets,domain);
}
public static Set<Set<Integer>> helper(Set<Set<Integer>> sets, Set<Integer> domain) throws Exception {
if (domain.isEmpty()) { return sets; }
if (sets.isEmpty()) { return sets; }
else if (sets.size() == 1) { return sets; }
sets.remove(new HashSet<Integer>());
// Pop some value from domain
Iterator<Integer> it = domain.iterator();
Integer splitNum = it.next();
it.remove();
Set<Set<Integer>> set1 = new HashSet<Set<Integer>>();
Set<Set<Integer>> set2 = new HashSet<Set<Integer>>();
for (Set<Integer> set : sets) {
if (set.contains(splitNum)) {
set.remove(splitNum);
set1.add(set);
}
else {
set2.add(set);
}
}
Set<Set<Integer>> ret = helper(set1,domain);
ret.addAll(helper(set2,domain));
for (Set<Integer> set : set1) {
set.add(splitNum);
}
return ret;
}
/**
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
Set<Set<Integer>> s=new HashSet<Set<Integer>>();
Set<Integer> tmp = new HashSet<Integer>();
tmp.add(new Integer(1)); tmp.add(new Integer(2)); tmp.add(new Integer(3));
s.add(tmp);
tmp = new HashSet<Integer>();
tmp.add(new Integer(1)); tmp.add(new Integer(2));
s.add(tmp);
tmp = new HashSet<Integer>();
tmp.add(new Integer(3)); tmp.add(new Integer(4));
s.add(tmp);
System.out.println(eliminate_subsets(s).toString());
}
}
* Los nuevos años son disruptivos
Tengo una colección de conjuntos únicos (representados como máscaras de bits) y me gustaría eliminar todos los elementos que sean subconjuntos adecuados de otro elemento. Por ejemplo:
input = [{1, 2, 3}, {1, 2}, {2, 3}, {2, 4}, {}]
output = [{1, 2, 3}, {2, 4}]
No he podido encontrar un algoritmo estándar para esto, ni siquiera un nombre para este problema, así que lo llamo "subconjuntos máximos" por falta de cualquier otra cosa. Aquí hay un algoritmo O (n ^ 2) (en Python por concreción), asumiendo que is_subset_func es O (1): 1
def eliminate_subsets(a, cardinality_func, is_subset_func):
out = []
for element in sorted(a, reverse=True, key=cardinality_func):
for existing in out:
if is_subset_func(element, existing):
break
else:
out.append(element)
return out
¿Existe un algoritmo más eficiente, con suerte O (n log n) o mejor?
1 Para máscaras de bits de tamaño constante, como es cierto en mi caso, is_subset_func es solo element & existing == element , que se ejecuta en tiempo constante.
Este problema ha sido estudiado en la literatura. Dado S_1, ..., S_k que son subconjuntos de {1, ..., n}, Yellin [1] dio un algoritmo para encontrar el subconjunto máximo de {S_1, ..., S_k} en el tiempo O (kdm) donde d es el tamaño promedio de S_i, y m es la cardinalidad del subconjunto máximo de {S_1, ..., S_k}. Yellin y Jutla [2] a O ((kd) ^ 2 / sqrt (log (kd))) mejoraron esto más tarde para cierto rango de parámetros. Se cree que no existe un algoritmo verdaderamente sub-cuadrático para este problema.
[1] Daniel M. Yellin: Algoritmos para pruebas de subconjuntos y búsqueda de conjuntos máximos. SODA 1992: 386-392.
[2] Daniel M. Yellin, Charanjit S. Jutla: Encontrando conjuntos extremos en menos de tiempo cuadrático. Inf. Proceso. Letón. 48 (1): 29-34 (1993).
Supongamos que etiqueta todos los conjuntos de entrada.
A={1, 2, 3}, B={1, 2}, C={2, 3}, D={2, 4}, E={}
Ahora cree conjuntos intermedios, uno por elemento en el universo, que contengan las etiquetas de los conjuntos donde aparece:
1={A,B}
2={A,B,C,D}
3={A,C}
4={D}
Ahora, para cada conjunto de entrada, calcule la intersección de todos los conjuntos de etiquetas de sus elementos:
For A, {A,B} intesect {A,B,C,D} intersect {A,C} = {A} (*)
Si la intersección contiene alguna otra etiqueta que no sea para el conjunto en sí, entonces es un subconjunto de ese conjunto. Aquí no hay otro elemento, entonces la respuesta es no. Pero,
For C, {A,B,C,D} intersect {A,C} = {A,C}, which means that it''s a subset of A.
El costo de este método depende de la implementación de conjuntos. Supongamos que los mapas de bits (como insinuó). Digamos que hay n conjuntos de entrada de tamaño máximo m y | U | Elementos en el universo. Entonces la construcción del conjunto intermedio produce | U | conjuntos de tamaño n bits, por lo que hay tiempo O (| U | n) para inicializarlos. La configuración de los bits requiere tiempo O (nm). Calcular cada intersección como en (*) arriba requiere O (mn); O (mn ^ 2) para todos.
Poniendo todos estos elementos juntos, tenemos O (| U | n) + O (nm) + O (mn ^ 2) = O (| U | n + mn ^ 2). Usando las mismas convenciones, su algoritmo de "todos los pares" es O (| U | ^ 2 n ^ 2). Como m <= | U |, este algoritmo es asintóticamente más rápido. También es probable que sea más rápido en la práctica porque no hay una contabilidad elaborada para agregar factores constantes.
Adición: versión en línea
El OP preguntó si hay una versión en línea de este algoritmo, es decir, una en la que el conjunto de conjuntos máximos se pueda mantener incrementalmente a medida que los conjuntos de entrada llegan uno por uno. La respuesta parece ser que sí. Los conjuntos intermedios nos dicen rápidamente si un nuevo conjunto es un subconjunto de uno ya visto. ¿Pero cómo saber rápidamente si es un superconjunto ? Y, en caso afirmativo, ¿de qué conjuntos máximos existentes? En este caso, esos conjuntos máximos ya no son máximos y deben ser reemplazados por uno nuevo.
La clave es tener en cuenta que A es un superconjunto de B si A'' es un subconjunto de B'' (la marca ''indica el complemento del conjunto).
Siguiendo esta inspiración, mantenemos el conjunto intermedio como antes. Cuando llegue un nuevo conjunto de entrada S , realice la misma prueba que se describió anteriormente: Sea I(e) el conjunto intermedio para el elemento de entrada e . Entonces esta prueba es
For X = /intersect_{e /in S} . I(e), |X| > 0
(En este caso, es mayor que cero en lugar de uno como el anterior porque S aún no está en I ). Si la prueba tiene éxito, entonces el nuevo conjunto es un subconjunto (posiblemente impropio) de un conjunto máximo existente, por lo que se puede descartar.
De lo contrario, debemos agregar S como un nuevo conjunto máximo, pero antes de hacer esto, calcule:
Y = /intersect_{e /in S''} . I''(e) = ( /union_{e /in S''} . I(e) )''
Donde de nuevo la garrapata se establece como complemento. La forma de unión puede ser un poco más rápida de calcular. Y contiene los conjuntos máximos que han sido reemplazados por S Deben ser retirados de la colección máxima y de I Finalmente, agregue S como conjunto máximo y actualice I con los elementos de S.
Trabajemos a través de nuestro ejemplo. Cuando llega A , lo añadimos a I y tenemos
1={A} 2={A} 3={A}
Cuando B llega, encontramos que X = {A} intersect {A} = {A} , así que tira B y continúa. Lo mismo sucede con C Cuando llega D , encontramos que X = {A} intersect {} = {} , así que continúe con Y = I''(1) intersect I''(3) = {} intersect {} . Esto nos indica correctamente que el conjunto máximo A no está contenido en D , por lo que no hay nada que eliminar. Pero debe agregarse como un nuevo conjunto máximo, y I convierto en
1={A} 2={A,D} 3={A} 4={D}
La llegada de E no causa cambio. Indique la llegada entonces de un nuevo conjunto F={2, 3, 4, 5} . Encontramos
X = {A} isect {A,D} isect {A} isect {D} isect {}
así que no podemos tirar F lejos. Continua con
Y = /intersect_{e in {1}} I''(e) = I''(1) = {D}
Esto nos dice que D es un subconjunto de F , por lo que debe descartarse mientras se agrega F , dejando
1={A} 2={A,F} 3={A,F} 4={F} 5={F}
El cálculo de los complementos es complicado y agradable debido a la naturaleza en línea del algoritmo. El universo para complementos de entrada solo necesita incluir elementos de entrada vistos hasta ahora. El universo para conjuntos intermedios consiste solo en etiquetas de conjuntos en la colección máxima actual. Para muchos flujos de entrada, el tamaño de este conjunto se estabilizará o disminuirá con el tiempo.
Espero que esto sea útil.
Resumen
El principio general que funciona aquí es una idea poderosa que a menudo se usa en el diseño de algoritmos. Es el mapa inverso. Cuando te encuentres haciendo una búsqueda lineal para encontrar un elemento con un atributo determinado, considera la posibilidad de crear un mapa desde el atributo hasta el elemento. A menudo es barato construir este mapa y reduce considerablemente el tiempo de búsqueda. El primer ejemplo es un mapa de permutación p[i] que te dice qué posición ocupará el elemento i ''th después de que se permuta una matriz. Si necesita buscar el elemento que termina en una ubicación dada a , debe buscar p para a operación de tiempo lineal. Por otro lado, un mapa inverso pi tal que pi[p[i]] == i no requiere más tiempo para calcular que p (por lo que su costo está "oculto"), pero pi[a] produce el resultado deseado en constante hora.
Implementación por Póster Original
import collections
import operator
def is_power_of_two(n):
"""Returns True iff n is a power of two. Assumes n > 0."""
return (n & (n - 1)) == 0
def eliminate_subsets(sequence_of_sets):
"""Return a list of the elements of `sequence_of_sets`, removing all
elements that are subsets of other elements. Assumes that each
element is a set or frozenset and that no element is repeated."""
# The code below does not handle the case of a sequence containing
# only the empty set, so let''s just handle all easy cases now.
if len(sequence_of_sets) <= 1:
return list(sequence_of_sets)
# We need an indexable sequence so that we can use a bitmap to
# represent each set.
if not isinstance(sequence_of_sets, collections.Sequence):
sequence_of_sets = list(sequence_of_sets)
# For each element, construct the list of all sets containing that
# element.
sets_containing_element = {}
for i, s in enumerate(sequence_of_sets):
for element in s:
try:
sets_containing_element[element] |= 1 << i
except KeyError:
sets_containing_element[element] = 1 << i
# For each set, if the intersection of all of the lists in which it is
# contained has length != 1, this set can be eliminated.
out = [s for s in sequence_of_sets
if s and is_power_of_two(reduce(
operator.and_, (sets_containing_element[x] for x in s)))]
return out
Supuestos previos al proceso:
Enfoque # 2 - Utilice un enfoque de cubo
Las mismas suposiciones. ¿Se puede asumir la singularidad? (es decir, no hay {1,4,6}, {1,4,6}) De lo contrario, tendría que verificar la distinción en algún momento, probablemente una vez que se hayan creado los grupos.
semi psuedo
List<Set> Sets;//input
List<Set> Output;
List<List<Set>> Buckets;
int length = Sets[0].length;//"by descending lengths"
List<Set> Bucket = new List<Set>();//current bucket
//Place each set with shared length in its own bucket
for( Set set in Sets )
{
if( set.length == length )//current Bucket
{
Bucket.add(set);
}else//new Bucket
{
length = set.length;
Buckets.Add(Bucket);
Bucket = new Bucket();
Bucket.Add(set);
}
}
Buckets.add(Bucket);
//Based on the assumption of uniqueness, everything in the first bucket is
//larger than every other set and since it is unique, they are not proper subsets
Output.AddRange(Buckets[0]);
//Iterate through the buckets
for( int i = 1; i < Buckets.length; i++ )
{
List<Set> currentBucket = Buckets[i];
//Iterate through the sets in the current bucket
for( int a = 0; a < currentBucket.length; a++ )
{
Set currentSet = currentBucket[a];
bool addSet = true;
//Iterate through buckets with greater length
for( int b = 0; b < i; b++ )
{
List<Set> testBucket = Buckets[b];
//Iterate through the sets in testBucket
for( int c = 0; c < testBucket.length; c++ )
{
Set testSet = testBucket[c];
int testMatches = 0;
//Iterate through the values in the current set
for( int d = 0; d < currentSet.length; d++ )
{
int testIndex = 0;
//Iterate through the values in the test set
for( ; testIndex < testSet.length; testIndex++ )
{
if( currentSet[d] < testSet[testIndex] )
{
setClear = true;
break;
}
if( currentSet[d] == testSet[testIndex] )
{
testMatches++;
if( testMatches == currentSet.length )
{
addSet = false;
setClear = true;
break;
}
}
}//testIndex
if( setClear ) break;
}//d
if( !addSet ) break;
}//c
if( !addSet ) break;
}//b
if( addSet ) Output.Add( currentSet );
}//a
}//i
Enfoque # 1 ( O( n(n+1)/2 ) ) ... no lo suficientemente eficiente
semi psuedo
//input Sets
List<Set> results;
for( int current = 0; current < Sets.length; current++ )
{
bool addCurrent = true;
Set currentSet = Sets[current];
for( int other = 0; other < current; other++)
{
Set otherSet = Sets[other];
//is current a subset of other?
if( currentSet.total > otherSet.total
|| currentSet.length >= otherSet.length) continue;
int max = currentSet.length;
int matches = 0;
int otherIndex = 0, len = otherSet.length;
for( int i = 0; i < max; i++ )
{
for( ; otherIndex < len; otherIndex++ )
{
if( currentSet[i] == otherSet[otherInex] )
{
matches++;
break;
}
}
if( matches == max )
{
addCurrent = false;
break;
}
}
if( addCurrent ) results.Add(currentSet);
}
}
Esto tomará el conjunto de conjuntos e iterará a través de cada uno. Con cada uno, se repetirá de nuevo a través de cada conjunto en el conjunto. A medida que se lleva a cabo la iteración anidada, se comparará si el conjunto externo es el mismo que el conjunto anidado (de la iteración interna) (si lo son, no se realiza ninguna comprobación), también se comparará si el conjunto externo tiene un total mayor que el conjunto anidado (si el total es mayor, entonces el conjunto externo no puede ser un subconjunto adecuado), luego comparará si el conjunto externo tiene una cantidad menor de elementos que el conjunto anidado.
Una vez que se completan esas comprobaciones, comienza con el primer elemento del conjunto externo y lo compara con el primer elemento del conjunto anidado. Si no son iguales, verificará el siguiente elemento del conjunto anidado. Si son iguales, entonces agrega uno a un contador, y luego comparará el siguiente elemento del conjunto externo con el lugar donde se quedó en el conjunto interno.
Si alcanza un punto en el que la cantidad de comparaciones emparejadas es igual al número de elementos en el conjunto externo, se ha encontrado que el conjunto externo es un subconjunto adecuado del conjunto interno. Está marcado para ser excluido, y las comparaciones se detienen.