¿Cómo obtengo un juego de potencia en un orden específico?

Question

hay algunas soluciones para calcular un conjunto de potencia, pero estas que encontré en google no dan el poder establecido en el orden, que lo necesito. Por ejemplo, si quiero que el conjunto potencia de (1,2,3,4) algoritmos comunes proporcionarme un poder establecido en el siguiente orden:

() 
(1) 
(2) 
(1 2) 
(3) 
(1 3) 
(2 3) 
(1 2 3) 
(4) 
(1 4) 
(2 4) 
(1 2 4) 
(3 4) 
(1 3 4) 
(2 3 4) 
(1 2 3 4) 

Pero lo que necesito es el siguiente orden:

() 
(1) 
(2) 
(3) 
(4) 
(1,2) 
(1,3) 
(1,4) 
(2,3) 
(2,4) 
(3,4) 
(1,2,3) 
(1,2,4) 
(1,3,4) 
(2,3,4) 
(1,2,3,4) 

Debido el número de elementos puede ser bastante alto, no es posible calcular todo el conjunto de potencia y ordenarlo después.

¿Alguien tiene alguna idea?

Answer 1

¿Quieres las combinaciones con el fin de longitud. En Python se puede escribir:

import itertools 

def subsets(iterable): 
    "Generate the subsets of elements in the iterable, in order by length." 
    items = list(iterable) 
    for k in xrange(len(items) + 1): 
     for subset in itertools.combinations(items, k): 
      yield subset 

>>> list(subsets([1,2,3,4])) 
[(), (1,), (2,), (3,), (4,), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), 
(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (1, 2, 3, 4)] 

Ver this answer para una visión general de los algoritmos que generan combinaciones. (O puede consultar la implementación de Python de Raymond Hettinger, itertoolsmodule.c lines 2026f.)

Answer 2

(usted debe dar algunos detalles sobre los algoritmos que se encuentran en Google ...)

Pero se puede procesar de esta manera:

primera: crear una función que genere todos los juegos de poder de longitud n de un conjunto ordenado determinado:

aquí es un posible pseudo código para esta función:

set={a1, ...ap} //is an ordered set 
define f(set , n): 
    result = {} 
    count=1 
    for element in set : 
     set.pop(element) 
     result.append({ f(set,n-1).AppendtoAllInfirstPosition(element) }) // not sure if I write this well, but you process recursively, poping the sorted value one by one a1...ap and using f(popped set, n-1) you append the sets 
    if length(set)=n: 
     return set //you initialise the recurence. the above loop will stop when len(popped(set))=n-1 
    return result 

Segundo: Una vez que hecho esto simplemente determinada:

f(set,i) for i in range(len(set)) and you will get your ordered power set. 

la esperanza que esto funciona y ayuda

Answer 3

Si el conjunto inicial tiene N números, el conjunto de alimentación contendrá 2^N elementos. Sugiero lo siguiente

Algoritmo:
generan sequently todos los subconjuntos de juego de la inicial con el fin de aumentar su número de elementos. Esto se puede hacer, por ejemplo, considerando todas las permutaciones de una matriz, que consiste en k y n-k ceros (también se llama máscara). Cada máscara describe un subconjunto único: simplemente seleccionamos los elementos que se encuentran en las posiciones que están configuradas en 1. Con esto conseguiremos (imprimir, guardar o lo que sea necesario) todos los subconjuntos ordenados aumentando su tamaño, si es igual por orden de los elementos que aparecen en el conjunto inicial.

Complejidad:
iteración 2^N máscaras y mirando N posiciones en cada una nos llevará a O(N * 2^N) complejidad.

Implementación:
Aquí está mi aplicación en C++, utilizando std::next_permutation para generar todas las máscaras con número fijo de ones. Lee un conjunto de enteros de la entrada estándar y genera e imprime secuencialmente todos los subconjuntos a la salida estándar. Tenga en cuenta que esta solución no guarda los subconjuntos, si no es necesario:

#include <algorithm> 
#include <iostream> 
#include <vector> 

void calcPowerSet(const std::vector<int>& inputSet) 
{ 
    int n = inputSet.size(); 
    for(int ones = 0; ones <= n; ++ones) 
    { 
     std::vector<bool> mask(n, 0); 
     for(int i = 0; i < ones; ++i) 
      mask[ i ] = true;   // setting first 'ones' bits to '1' 
     do 
     { 
      // printing the subset described by current mask 
      std::cout << "("; 
      for(int i = 0; i < n; ++i) 
       if(mask[ i ]) 
        std::cout << ' ' << inputSet[ i ] << ' '; 
      std::cout << ")\n"; 
     } 
     while(std::next_permutation(mask.rbegin(), mask.rend())); // generating masks 
    } 
} 


int main() 
{ 
    int n; 
    std::cin >> n; 
    std::vector<int> inputSet(n); 
    for(int i = 0; i < n; ++i) 
     std::cin >> inputSet[ i ]; 
    calcPowerSet(inputSet); 
    return 0; 
}