C++

Forum

 
subset of k elements

shmokarami (20)
Hi, I want to write an algorithm, in which it needs to find all subset of k elements from the set {1,2,...,n} elements, for k=1,...,p (p is defined by user),
I have no idea to write code which efficient in speed and memory,
Can anybody help me?
Last edited on
JLBorges (13770)
1. Generate each permutation of the n elements
2. For each permutation, pick the first k elements

std::next_permutation()
http://en.cppreference.com/w/cpp/algorithm/next_permutation

mik2718 (347)
Thats going to generate loads of duplicates and is very inefficient

(imagine n=100 and k=2)

I'm not sure what the best way is but I suggest more research
JLBorges (13770)
> Thats going to generate loads of duplicates

Yes, duplicate sets.


> and is very inefficient

True. A lexicographic-ordering algorithm or the grey-code algorithm would be faster.
Last edited on
JLBorges (13770)
Using inverted Gray codes:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
#include <iostream>
#include <vector>
#include <algorithm>

void print_subset( std::vector<bool> bit_mask, std::size_t req_size )
{
    if( std::count( bit_mask.begin(), bit_mask.end(), true ) == req_size )
    {
        static int cnt = 0 ;
        std::cout << ++cnt << ". [ " ;
        for( std::size_t i = 0 ; i < bit_mask.size() ; ++i )
            if( bit_mask[i] ) std::cout << i+1 << ' ' ;
        std::cout << "]\n" ;
    }
}

// generate the next Gray code (in reverse)
// http://en.wikipedia.org/wiki/Gray_code
bool next_bitmask( std::vector<bool>& bit_mask )
{
    std::size_t i = 0 ;
    for( ; ( i < bit_mask.size() ) && bit_mask[i] ; ++i )
        bit_mask[i] = false ;

    if( i < bit_mask.size() ) { bit_mask[i] = true ; return true ; }
    else return false ;
}

int main()
{
    std::size_t k, n ;
    std::cout << "n? " && std::cin >> n ;
    std::cout << "k? " && std::cin >> k ;
    std::vector<bool> bit_mask(n) ;
    do print_subset( bit_mask, k ) ; while( next_bitmask(bit_mask) ) ;
}
kev82 (323)
Am I missing something obvious here?

Just loop a large enough bit size integer from 1 to 2^n inclusive exclusive. If the parity of the integer is less than or equal p then the integer represents a valid subset of size k<=p. Item i is in the subset if bit i of the integer is 1.

Calculating the parity can be a bit slow. If this is an issue then precalculate a lookup table for the parity of an 8 bit number and then split the integer into 8 bit numbers.

With carful thought, and small p, you can optimize to skip a lot of integers.
Last edited on
shmokarami (20)
I thank you so much.
JLBorges (13770)
> Just loop a large enough bit size integer from 1 to 2^n inclusive.

Yes. Standard integral types will work for n <= std::numeric_limits< unsigned long long >::digits. With a lookup table for parity, that would be faster.

For larger n, a big integer library would be needed. Don't know if that would be any faster.



ResidentBiscuit (4459)
Duthomhas (13206)
As this is a fairly obvious homework assignment, I'm not so sure the OP has received the help he needs. I would also warn him against turning in anything like JLBorges's code. Even though he made it really simple it is still beyond anything the teacher will expect you to personally produce.
shmokarami (20)
Thanks for your consideration, I need subset of k elements of {1,2,..,n} for my algorithm in "Network Theory", This is only a partial task of the algorithm and in best scenario k=100 and n=1000. that the best way mentioned by JLBorges using Gray codes, seems not work. how can I generate a subset of k elements of {1,2,..,n} randomly?
JLBorges (13770)
> how can I generate a subset of k elements of {1,2,..,n} randomly?

1. Generate a random permutation of the n elements.
http://en.cppreference.com/w/cpp/algorithm/random_shuffle

2. Select the first k elements
kev82 (323)
I want to write an algorithm, in which it needs to find all subset of k elements


and in best scenario k=100 and n=1000


If you haven't already, you may want to rethink what you're doing, there are roughly 10^139 size 100 subsets of 1000 elements.
Topic archived. No new replies allowed.