Как получить набор мощности в определенном порядке?

Question

Есть некоторые решения для расчета набора мощности, но они, которые я нашел в Google, не дают набор мощности в том порядке, в котором он мне нужен.Например, если я хочу, чтобы набор мощности из (1,2,3,4) общих алгоритмов предоставлял мне набор мощности в следующем порядке:

()
(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)

Но мне нужен следующий порядок:

()
(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)

Поскольку количество элементов может быть довольно большим, невозможно рассчитать весь набор мощности и упорядочить его впоследствии.

У кого-нибудь есть идеи?

Answer 1

Вы хотите, чтобы комбинации в порядке по длине.В Python вы можете написать:

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)]

См. этот ответ для обзора алгоритмов, которые генерируют комбинации.(Или вы можете посмотреть на реализацию Python Рэймонда Хеттингера, itertoolsmodule.c lines 2026f .)

Answer 2

(Вы должны дать некоторые подробности об алгоритмах, которые вы нашли в Google ...)

Но вы можете обработать это так:

first: Создать функцию, которая генерирует все наборы мощности длины 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 

Секунда: Как только вы это сделаете, вы просто определитесь:

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

Надеюсь, что это работает, и это помогает

Answer 3

Если исходный набор имеет N номеров, набор мощности будет содержать 2 ^ N элементов.Я предлагаю следующее

Алгоритм: Последовательно генерировать все подмножества начального набора в порядке увеличения их количества элементов.Это можно сделать, например, с учетом всех перестановок массива, состоящего из k единиц и n-k нулей (это также называется mask ).Каждая маска описывает уникальное подмножество - мы просто выбираем элементы, стоящие на позициях, которые установлены на 1.Таким образом, мы получим (распечатать, сохранить или все, что нужно) все подмножества, упорядоченные по увеличению их размера, если они равны, то по порядку элементов, появляющихся в начальном наборе.

Сложность: Итерация масок 2^N и просмотр N позиций в каждой приведут нас к сложности O( N * 2^N ).

Реализация: Вот моя реализация на C ++, использующая std::next_permutation для генерации всех масок с фиксированным числом ones.Он читает набор целых чисел из стандартного ввода и последовательно генерирует и печатает все подмножества в стандартный вывод.Обратите внимание, что это решение не сохраняет подмножеств, если в этом нет необходимости:

#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;
}