Combination algorithm

Question

I want to make a simple sorting algorithm.

given the input "abcde", I would like to get the result below. could you tell me an algorithm for this?

arr[0] = "a" arr[1] = "ab" arr[2] = "ac" arr[3] = "ad" arr[4] = "ae" arr[5] = "abc" arr[6] = "abd" arr[7] = "abe" ... arr[n] = "abcde" arr[n+1] = "b" arr[n+2] = "bc" arr[n+3] = "bd" arr[n+4] = "be" arr[n+5] = "bcd" arr[n+5] = "bce" arr[n+5] = "bde" ... arr[n+m] = "bcde" ... ... 

Answer 1

The "Generate Power Set" algorithm from an array is what you are looking for. You can try Google or another search engine to find the algorithm that best suits your needs.

Answer 2

In C ++, the following procedure is specified:

 template <typename Iterator> bool next_combination(const Iterator first, Iterator k, const Iterator last) { /* Credits: Mark Nelson http://marknelson.us */ if ((first == last) || (first == k) || (last == k)) return false; Iterator i1 = first; Iterator i2 = last; ++i1; if (last == i1) return false; i1 = last; --i1; i1 = k; --i2; while (first != i1) { if (*--i1 < *i2) { Iterator j = k; while (!(*i1 < *j)) ++j; std::iter_swap(i1,j); ++i1; ++j; i2 = k; std::rotate(i1,j,last); while (last != j) { ++j; ++i2; } std::rotate(k,i2,last); return true; } } std::rotate(first,k,last); return false; } 

Then you can do the following:

 std::string s = "abcde"; for(std::size_t i = 1; i != s.size(); ++i) { do { std::cout << std::string(s.begin(),s.begin() + i) << std::endl; } while(next_combination(s.begin(),s.begin() + i,s.end())); } 

Note. What would you expect to see combinations 2 ^ n-1, where n is the length of the array or string.

Answer 3

You are describing a power set . Here is the C ++ code:

 #include <vector> #include <string> #include <algorithm> #include <functional> using namespace std; vector< string > string_powerset( string const &in ) { vector< string > result(1); // start output with one empty string result.reserve( 1 << in.size() ); // output size = 2^( in.size() ) if ( result.capacity() != 1<<in.size() ) throw range_error( "too big" ); for ( string::const_iterator it = in.begin(); it != in.end(); ++ it ) { size_t middle = result.size(); // duplicate what we have so far result.insert( result.end(), result.begin(), result.end() ); // append current character onto duplicated output for_each( result.begin() + middle, result.end(), bind2nd( mem_fun_ref( &string::push_back ), * it ) ); } return result; } 

Tested: v). Range checking is not the best, but anything.

This code will tend to overflow due to the exponential growth of the force set, so you should only pass short lines. Another published answer avoids this problem by generating and returning one row at a time. However, this is easier to understand, and using the much more complex and complex part of the code will be premature optimization if you do not have an overflow problem.

EDIT: I wrote the answer next_subset and it doesn't look like Ben.