Làm cách nào để có được bộ nguồn theo một thứ tự cụ thể?

Question

có một số giải pháp để tính toán bộ nguồn, nhưng chúng tôi tìm thấy trên google không cấp nguồn theo thứ tự mà tôi cần. Ví dụ, nếu tôi muốn tập sức mạnh của (1,2,3,4) thuật toán phổ biến cung cấp cho tôi với một sức mạnh thiết lập trong theo trình tự sau:

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

Nhưng những gì tôi cần là trình tự sau:

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

Vì số lượng các phần tử có thể khá cao, không thể tính toán toàn bộ bộ nguồn và đặt nó sau đó.

Có ai đó có ý tưởng nào không?

Answer 1

Bạn muốn kết hợp theo thứ tự theo chiều dài. Trong Python bạn có thể viết:

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

Xem this answer để biết tổng quan về thuật toán tạo kết hợp. (Hoặc bạn có thể xem xét triển khai Python của Raymond Hettinger, itertoolsmodule.c lines 2026f.)

Answer 2

(Bạn nên đưa ra một số thông tin chi tiết về các thuật toán bạn tìm thấy trên google ...)

Nhưng bạn có thể xử lý theo cách này:

đầu tiên: Tạo một chức năng mà tạo ra tất cả các bộ sức mạnh của chiều dài n của một tập lệnh đưa ra:

đây là một mã giả có thể cho chức năng này:

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 

Thứ hai: Khi bạn làm điều này bạn chỉ cần quyết tâm:

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

Hope này hoạt động và nó giúp

Answer 3

Nếu tập hợp ban đầu có số N, bộ nguồn sẽ chứa 2^N phần tử. Tôi đề nghị sau

Thuật toán:
sequently tạo ra tất cả các tập con của tập hợp inital theo thứ tự tăng số lượng của họ về yếu tố này. Điều này có thể được thực hiện, ví dụ, bằng cách xem xét tất cả hoán vị của một mảng, bao gồm k và n-k số không (điều này còn được gọi là mặt nạ). Mỗi mặt nạ mô tả một tập hợp con duy nhất - chúng tôi chỉ chọn các phần tử đứng trên các vị trí được đặt thành 1. Bằng cách này, chúng tôi sẽ nhận được (in, lưu hoặc bất cứ điều gì là cần thiết) tất cả các tập con được đặt hàng bằng cách tăng kích thước của chúng, nếu bằng nhau thì theo thứ tự các phần tử xuất hiện trong tập hợp ban đầu.

phức tạp:
lặp 2^N mặt nạ và nhìn vào N vị trí trong mỗi sẽ dẫn chúng ta đến O(N * 2^N) phức tạp.

Thực hiện:
Đây là thực hiện của tôi trong C++, sử dụng std::next_permutation để tạo ra tất cả các mặt nạ với số cố định của ones. Nó đọc một tập hợp các số nguyên từ đầu vào tiêu chuẩn và tạo ra một cách tuần tự và in tất cả các tập con thành đầu ra tiêu chuẩn. Lưu ý rằng giải pháp này không lưu các tập con, nếu nó không phải là cần thiết:

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