Cómo elegir a 5 de mis amigos de Twitter de una manera que maximice la cantidad de seguidores distintos que tienen

Supongo que la mayor cantidad de seguidores únicos significa la menor cantidad de seguidores compartidos de todos los seguidores de tus amigos. Si eso no es lo que quiere decir con único, entonces reformule para aclarar.

Así es como lo resolvería de la nada en pseudocódigo de mierda / Java / lo que sea.

Una explicación detallada a continuación.

Seguidores es una matriz 2D que contiene tus amigos y sus seguidores.

func mostUnique (int [] [] seguidores) {

int [] uniqueFollowers = int [seguidores.length];

Hashmap uniqueTable = new Hashmap (); // sin embargo, esto se hace

for (int i = 0; i <seguidores.length; i ++) {

for (int j = 0; j <seguidores [i] .length; j ++) {

if (seguidores [i] [j] está en UniqueTable &&
uniqueTable.get (seguidores [i] [j])! = -1) {

uniqueFollowers [uniqueTable.get (seguidores [i] [j])] -;

uniqueTable.set (seguidores [i] [j], -1);

} else if (seguidores [i] [j] no está en UniqueTable) {

uniqueTable.add (seguidores [i] [j], i);

uniqueFollowers [i] ++;

}

}

}

devuelve los índices de los 5 valores más altos de uniqueFollowers;

}

Puede que haya cometido un error o algo así, no estoy seguro.

En realidad es un problema genial. Pasa por el seguidor de cada seguidor, ya que debes verificarlos a todos. Mantiene una matriz con el número de seguidores únicos.

Básicamente, lo que quieres hacer es saber si algo es único. Pero no quería tener que hacer más pases sobre todo el asunto, lo que creo que lo haría tal vez O (N ^ 4) en lugar de O (N ^ 2), pero no me cite al respecto.

Por lo tanto, tengo que usar un hashmap que puede desmarcar retroactivamente a un seguidor como único si descubre al mismo seguidor más adelante en la lista de amigos.

Más allá de eso, solo necesita saber si está en la lista, por lo que lo establece en -1 para que no disminuya el duplicado original demasiadas veces; solo necesitas deshacerte de él una vez.

Entonces obviamente lo agrega; si no está en el mapa, solo agrégalo al hashmap por primera vez e incrementa el número de seguidores únicos.

No hice nada lujoso para obtener los 5 primeros, pero como se agregan uno a la vez, probablemente podría resolver algo al administrar otra lista y agregarlos a un extremo u otro para ser más eficientes y no requerir un ordenar.

Que te diviertas.

Este problema es difícil de resolver de manera eficiente, pero puede usar un algoritmo codicioso para encontrar una solución aproximada. La aproximación te dará un conjunto de 5 amigos que colectivamente tienen al menos el 63% de los seguidores que tendría el conjunto ideal. Esto no parece mucho, pero en la práctica es bastante bueno, y no existen algoritmos de aproximación eficientes que brinden mejores garantías.

En general, suponga que tiene conjuntos [matemáticos] n [/ matemáticos], posiblemente superpuestos, y desea elegir los conjuntos [matemáticos] m [/ matemáticos] que tienen la unión más grande. (Cada conjunto correspondería a los seguidores de un usuario). Luego, debe seleccionar los conjuntos uno a la vez, en cada paso, elija el conjunto que agregue la mayor cantidad de elementos a la unión. La colección resultante tendrá al menos [math] (1 – 1 / e) [/ math] veces el número de elementos que podría obtener si elige sus conjuntos de manera óptima.


¿Porqué es eso?

Sea [math] A ^ * = s_1 \ cup \ dots \ cup s_m [/ math] la colección óptima de conjuntos. Deje que [math] A_1, A_2, \ dots [/ math] sean las colecciones de conjuntos que hemos elegido hasta ahora en cada paso (donde [math] A_m [/ math] es la salida del algoritmo codicioso y [math] A_1 \ subseteq A_2 \ subseteq A_3 \ subseteq \ dots [/ math]).

Considere el paso [math] k [/ math] del algoritmo codicioso. Observa eso

[matemáticas] | A ^ * | \ leq | A_k \ cup A ^ * | [/ math]

[matemáticas] = (| A_k \ cup s_1 \ cup \ dots \ cup s_k | – | A_k \ cup s_1 \ cup \ dots \ cup s_ {k – 1} |) + (| A_k \ cup s_1 \ cup \ dots \ cup s_ {k – 1} | – \ dots – | A_k \ cup s_1 |) + (| A_k \ cup s_1 | – | A_k |) + | A_k | [/ math]

[matemáticas] = | A_k | + \ sum_ {i = 1} ^ {k} | (A_k \ cup s_1 \ cup \ dots \ cup s_ {i – 1}) \ cup s_i | – | A_k \ cup s_1 \ cup \ dots \ cup s_ {i – 1} | [/ math]

Ahora, una propiedad interesante de los conjuntos es que si agrega un conjunto a un conjunto pequeño, probablemente agregará más elementos que si lo hubiera agregado a un conjunto más grande, porque con conjuntos grandes existe el riesgo de que algunos de los elementos nuevos tengan ya apareció en el set, y no debería contarse dos veces. Formalmente, si [math] T \ subseteq T ‘[/ math], entonces [math] | T \ cup S | – | T | \ geq | T ‘\ cup S | – | T ‘| [/ matemáticas].

Sabiendo esto, podemos simplificar nuestra desigualdad a

[matemáticas] \ leq | A_k | + \ sum_ {i = 1} ^ k | A_k \ cup s_i | – | A_k | [/ matemáticas]

Ahora recuerde que estamos usando el algoritmo codicioso, por lo que el conjunto [math] A_ {k + 1} [/ math] serán los elementos del conjunto [math] A_k [/ math], más el conjunto que introduciría el La mayoría de los elementos nuevos. Entonces [matemáticas] | A_k \ cup s_i | – | A_k | [/ math] siempre es [math] \ leq | A_ {k + 1} | – | A_k | [/ matemáticas].

Entonces ahora tenemos [matemáticas] | A ^ * | \ leq | A_k | + k (| A_ {k + 1} | – | A_k |) \ leq | A_k | + m (| A_ {k + 1} | – | A_k |) [/ matemáticas]. Con algo de álgebra, esta desigualdad se puede escribir como

[matemáticas] | A ^ * | – | A_ {k + 1} | \ leq (1 – 1 / m) (| A ^ * | – | A_k |) [/ matemáticas]

[matemáticas] \ leq e ^ {- 1 / m} (| A ^ * | – | A_k |) [/ matemáticas]

Entonces obtenemos [matemáticas] | A ^ * | – | A_ {m} | \ leq e ^ {- m / m} (| A ^ * | – | A_0 |) [/ math] y [math] | A_m | \ geq | A ^ * | (1 – \ frac {1} {e}) [/ math], lo que significa que la salida del algoritmo codicioso garantiza al menos [math] 1 – 1 / e [/ math] de El valor óptimo.


Referencias

[1] Cuando los algoritmos codiciosos son lo suficientemente buenos: submodularidad y la aproximación (1 – 1 / e)

Sí, la versión generalizada del problema se denomina problema de cobertura máxima. A saber, dada una colección de N conjuntos, encuentre los conjuntos K cuya unión, constituyen el subconjunto más grande de la unión de todos los conjuntos N.

Este es un problema NP-Hard, por lo que es mejor tratar de encontrar una solución aproximada. Dicho esto, si necesita una solución exacta, es de esperar que no tenga demasiados “amigos” de Twitter.