Combinaciones de vectores de computación eficiente

Question

Estoy trabajando en un problema de investigación por curiosidad, y no sé cómo programar la lógica que tengo en mente. Déjame que te lo explique:

tengo cuatro vectores, digamos por ejemplo,

v1 = 1 1 1 1 
v2 = 2 2 2 2 
v3 = 3 3 3 3 
v4 = 4 4 4 4 

Ahora lo que quiero hacer es agregarlos combinación sabia, es decir,

v12 = v1+v2 
v13 = v1+v3 
v14 = v1+v4 
v23 = v2+v3 
v24 = v2+v4 
v34 = v3+v4 

Hasta este paso, está bien. El problema ahora es que quiero agregar cada uno de estos vectores un vector de v1, v2, v3, v4 que no ha agregado antes. Por ejemplo:

v3 y v4 no se ha agregado a v12, por lo que quiero crear v123 y v124. De manera similar para todos los vectores como,

v12 should become: 
v123 = v12+v3 
v124 = v12+v4 

v13 should become: 
v132 // This should not occur because I already have v123 
v134 

v14 should become: 
v142 // Cannot occur because I've v124 already 
v143 // Cannot occur 

v23 should become: 
v231 // Cannot occur 
v234 ... and so on. 

Es importante que no haga todo de una vez al principio. Como por ejemplo, puedo hacer (4 elijo 3) 4C3 y terminarlo, pero quiero hacerlo paso a paso en cada iteración.

¿Cómo programo esto?

P.S .: Estoy tratando de trabajar en una versión modificada de un algoritmo apriori en la extracción de datos.

Answer 1

En C++, dada la siguiente rutina:

template <typename Iterator> 
inline bool next_combination(const Iterator first, 
            Iterator k, 
          const Iterator last) 
{ 
    /* Credits: Thomas Draper */ 
    if ((first == last) || (first == k) || (last == k)) 
     return false; 
    Iterator itr1 = first; 
    Iterator itr2 = last; 
    ++itr1; 
    if (last == itr1) 
     return false; 
    itr1 = last; 
    --itr1; 
    itr1 = k; 
    --itr2; 
    while (first != itr1) 
    { 
     if (*--itr1 < *itr2) 
     { 
     Iterator j = k; 
     while (!(*itr1 < *j)) ++j; 
     std::iter_swap(itr1,j); 
     ++itr1; 
     ++j; 
     itr2 = k; 
     std::rotate(itr1,j,last); 
     while (last != j) 
     { 
      ++j; 
      ++itr2; 
     } 
     std::rotate(k,itr2,last); 
     return true; 
     } 
    } 
    std::rotate(first,k,last); 
    return false; 
} 

entonces puede proceder a hacer lo siguiente:

int main() 
{ 
    unsigned int vec_idx[] = {0,1,2,3,4}; 

    const std::size_t vec_idx_size = sizeof(vec_idx)/sizeof(unsigned int); 

    { 
     // All unique combinations of two vectors, for example, 5C2 
     std::size_t k = 2; 
     do 
     { 
     std::cout << "Vector Indicies: "; 
     for (std::size_t i = 0; i < k; ++i) 
     { 
      std::cout << vec_idx[i] << " "; 
     } 
     } 
     while (next_combination(vec_idx, 
           vec_idx + k, 
           vec_idx + vec_idx_size)); 
    } 

    std::sort(vec_idx,vec_idx + vec_idx_size); 

    { 
     // All unique combinations of three vectors, for example, 5C3 
     std::size_t k = 3; 
     do 
     { 
     std::cout << "Vector Indicies: "; 
     for (std::size_t i = 0; i < k; ++i) 
     { 
      std::cout << vec_idx[i] << " "; 
     } 
     } 
     while (next_combination(vec_idx, 
           vec_idx + k, 
           vec_idx + vec_idx_size)); 
    } 

    return 0; 
} 

** Nota 1: * Debido a la interfaz orientada a iterador para el next_combination de rutina, cualquier contenedor STL que admita la iteración directa a través de iteradores también se puede usar, como std::vector, std::deque y std::list por nombrar solo algunos.

Nota 2: Este problema es muy adecuado para la aplicación de técnicas de memorización. En este problema, puede crear un mapa y completarlo con sumas vectoriales de combinaciones determinadas. Antes de calcular la suma de un conjunto dado de vectores, puede buscar si ya se ha calculado algún subconjunto de las sumas y usar esos resultados.Aunque está realizando una suma que es bastante barata y rápida, si el cálculo que estaba realizando fuera mucho más complejo y lento, esta técnica definitivamente ayudaría a lograr algunas mejoras importantes en el rendimiento.

Answer 2

1. Mantenga una lista de todas para elegir dos valores.
2. Crea un vector de conjuntos de modo que el conjunto esté formado por elementos del vector original con los elementos 4C2. Itere sobre los vectores originales y para cada uno, agregue/cree un conjunto con elementos del paso 1. Mantenga un vector de conjuntos y solo si el conjunto no está presente, agregue el resultado al vector.
3. resumir el vector de juegos que obtuvo en el paso 2.

Pero como usted ha indicado, el más fácil es 4C3.

Aquí hay algo escrito en Python. Usted puede adoptar en C++

import itertools 

l1 = ['v1','v2','v3','v4'] 
res = [] 
for e in itertools.combinations(l1,2): 
    res.append(e) 

fin = [] 
for e in res: 
    for l in l1: 
     aset = set((e[0],e[1],l)) 
     if aset not in fin and len(aset) == 3: 
      fin.append(aset) 
print fin 

Esto daría como resultado:

[set(['v1', 'v2', 'v3']), set(['v1', 'v2', 'v4']), set(['v1', 'v3', 'v4']), set(['v2', 'v3', 'v4'])] 

Este es el mismo resultado que 4C3.

Answer 3

Tal vez estoy malentendido, pero ¿no es esto equivalente a generar todos los subconjuntos (conjunto de potencia) de 1, 2, 3, 4 y luego para cada elemento del conjunto de potencia, sumando el vector? Por ejemplo:

//This is pseudo C++ since I'm too lazy to type everything 
//push back the vectors or pointers to vectors, etc. 
vector< vector<int> > v = v1..v4; 

//Populate a vector with 1 to 4 
vector<int> n = 1..4 

//Function that generates the power set {nil, 1, (1,2), (1,3), (1,4), (1,2,3), etc. 
vector< vector <int> > power_vec = generate_power_set(n); 

//One might want to make a string key by doing a Perl-style join of the subset together by a comma or something... 
map< vector <int>,vector<int> > results; 
//For each subset, we sum the original vectors together 
for subset_iter over power_vec{ 
    vector<int> result; 
    //Assumes all the vecors same length, can be modified carefully if not. 
    result.reserve(length(v1)); 
    for ii=0 to length(v1){ 
     for iter over subset from subset_iter{ 
      result[ii]+=v[iter][ii]; 
     } 
    } 
    results[*subset_iter] = result; 
} 

Si esa es la idea que tenía en mente, todavía se necesita una función de ajuste de potencia, pero que el código es fácil de encontrar si usted busca para poder establecido. Por ejemplo, Obtaining a powerset of a set in Java.

Answer 4

Creo que este problema se puede resolver marcando qué combinación se produjo.

Mi primer pensamiento es que puede usar una matriz tridimensional para marcar qué combinación ha sucedido. Pero eso no es muy bueno.

¿Qué tal una matriz de bits (como un entero) para marcar? Tales como:

Num 1 = 2^0 for vector 1 
Num 2 = 2^1 for vector 2 
Num 4 = 2^2 for vector 3 
Num 8 = 2^3 for vector 4 

Cuando haga una redacción, solo agregue todos los números representativos. Por ejemplo, el vector 124 tendrá el valor: 1 + 2 + 8 = 11. Este valor es único para cada combinación.

Esto es solo mi pensamiento. Espero que te ayude de alguna manera.

EDIT: Tal vez no soy lo suficientemente claro acerca de mi idea. Trataré de explicarlo un poco más claro:

1) Asigne a cada vector un número representativo. Este número es el id de un vector, y es único. Además, la suma de cada subconjunto de esos números es única, significa que si tenemos suma de k el número representativo es M; podemos saber fácilmente qué vectores participan en la suma.

Lo hacemos asignando: 2^0 para el vector 1; 2^1 para el vector 2; 2^2 para el vector 3, y así sucesivamente ...

Con cada M = suma (2^x + 2^y + 2^z + ...) = (2^x O 2^Y o 2^z O ...). Sabemos que el vector (x + 1), (y + 1), (z +1) ... forman parte de la suma. Esto se puede verificar fácilmente expresando el número en modo binario.

Por ejemplo, sabemos que:

2^0 = 1 (binario) 2^1 = 10 (binario) 2^2 = 100 (binario) ...

Así que si tenemos la suma es 10010 (binario), sabemos que el vector (número: 10) y el vector (número: 10000) se unen en la suma.

Y para el mejor, la suma aquí se puede calcular por el operador "OR", que también se entiende fácilmente si se expresa el número en binario.

2) Utilizando los hechos anteriores, cada vez antes de contar la suma de su vector, puede agregar/O su número de representante primero. Y puede seguirlos en algo así como una matriz de búsqueda. Si la suma ya existe en la matriz de búsqueda, puede omitirla. Por eso puedes resolver el problema.