subset of k elements

[shmokarami]

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?

[JLBorges]

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]

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]

> 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.

[JLBorges]

Using inverted Gray codes:

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

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.

[shmokarami]

I thank you so much.

[JLBorges]

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

OP, give this a read.
http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK4/NODE152.HTM

[Duoas]

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]

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]

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

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.