Generating all sequences of 1s and 0s of length 30

[gofer]

I'm trying to generate all possible sequences of 1s and 0s of length 30 where no subsequence is repeated 3 consecutive times (without subsequences like 000 or 101010 or 100100100). I'm not sure how I should approach the problem and when I asked my "mentor" about it he gave me some really vague answers (mostly repeating the phrase "There are different ways to do it").

So any help will be greatly appreciated. Thanks in advance

[v0id]

What language is it going to be in? If you're using C++, you can use two of the standard algorithm functions to solve the problem. They're called next_permutation and prev_permutation.

If not, you may check Wikipedia's article on permutations.

[gofer]

Thanks for the reply. The language is irrelevant - I can do it in a language that best suits the task (although I was planning to use C++).

However I still don't understand how am I supposed to use permutations to solve the problem. Permutations simply change the order of the elements in a set. What's the set?

Are you suggesting to generate every possible combination of 1s and 0s of length 30 and then search for consecutive sequences in all of them? Because that seems awfully slow to me...

[v0id]

Oh, sorry. I read your question a little too fast. I read it as you just wanted the permutations.

You could search for them, yes, but you're right, that is slow. It's the only solution I can think of right now, but I'm sure somebody will stop by and provide you some better answers.

[WingedPanther]

First issue: you are searching through a space of 2^30 or 1,073,741,824 strings.
Second issue: your "invalid" strings consist of
2^1 3 digit strings
2^2 6 digit strings
2^3 9 digit strings
2^4 12 digit strings
2^5 15 digit strings
...
2^10 30 digit strings
This means you have 2^11-2 potential substrings to check for each of your strings. Of course, some of the longer strings are invalid because of the shorter strings (00 00 00 contains 000, etc).

The two options I can see are:
1) build a minimal list of invalid substrings, and for each candidate, check for the presence of all the invalid substrings. This may be prohibitively large.
2) for each string, loop through it grabbing 1, then 2, then 3, etc characters, checking to see if it is the basis of an invalid string.

[gofer]

Thanks for the help This is what I came up with:

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

struct SortStrings
{
	bool operator()( const string& lhs, const string& rhs ) const
	{
		return lhs.length() < rhs.length();
	}
};

std::string StringFromInt( int n )
{
	if( n == 0 )
		return "0";

	int i = 31;
	while( !( (1 << i) & n ) ) // Finds the most significant bit equal to 1
		--i;

	std::string result;

	for( int j = i; j>=0; --j )
	{
		std::string res = (1<<j) & n ? "1" : "0";
		result.append( res );
	}

	return result;
}

void GenereateInvalidDict( std::vector<std::string>& out )
{
	std::vector<std::string> temp;
	for(int i = 0; i < 1024; ++i)
	{
		std::string s = StringFromInt(i);
		temp.push_back( s );

		if( s.length() < 10 )
			temp.push_back( std::string("0") += s );
		if( s.length() < 9 )
			temp.push_back( std::string("00") += s );
	}

	std::sort( temp.begin(), temp.end(), SortStrings() );

	std::vector<std::string> temp2;
	for( size_t i = 0; i<temp.size(); ++i )
	{
		bool bNeeded = true;

		for( size_t j = 0; j<i; ++j )
		{
			std::string toSearch = temp[j];
			toSearch += temp[j];
			toSearch += temp[j];
			if( temp[i].find( toSearch ) != temp[i].npos )
			{
				bNeeded = false;
				//break;
			}
		}
		if( bNeeded )
			temp2.push_back( temp[i] );
	}

	for( size_t i = 0; i<temp2.size(); ++i )
	{
		std::string s = temp2[i];
		s.append( temp2[i] );
		s.append( temp2[i] );

		out.push_back( s );
	}
}

bool IsValid( const std::vector<std::string>& invalid, const string& s )
{
	for( size_t i = 0; i<invalid.size(); ++i )
		if( s.find( invalid[i] ) != s.npos )
			return false;
	return true;
}
void Generate1sAnd0s( const std::vector<std::string>& invalid, const std::string& s, ostream& out )
{
	if( s.length() == 30 )
	{
		out << s.c_str() << endl;
		return;
	}

	string s0 = s; s0.append( "0" );
	string s1 = s; s1.append( "1" );
	if( IsValid( invalid, s0 ) )
		Generate1sAnd0s( invalid, s0, out );
	if( IsValid( invalid, s1 ) )
		Generate1sAnd0s( invalid, s1, out );
}

int main()
{
	std::vector<std::string> invalid;
	GenereateInvalidDict( invalid );
	Generate1sAnd0s( invalid, "", cout );
	cout << "Done" << endl;
	return 0;
}

GenereateInvalidDict generates the dictionary of invalid strings and Generate1sAnd0s recursively appends a 1 and/or a 0 to the string if it's a valid one, until it reaches the required length of 30