You are here:

C++/using an array for brute combinatorics/permutations


QUESTION: ok i dabble with programming a bit, and recently it occurred to me that digital audio has a very finite range of values, and that simply counting through to a very large number would iterate the bits through all possible combinations.
failing to get an arbitrary precision math library to work for me with a free msvc++6 compiler i have, i figured that i could try using a large array of unsigned 32bit integers as an equivalent for 16bit*44,100samples*5 seconds, so an unsigned int array [110250](which would be an equivalent bitcount)with a for(i=0;i<unsigned-integer-maximum-value;i++)array[position]=i
to loop through all the values for a single position
with a similar for loop flushing all the array positions to a file sequentially after each increment.

where i got lost was making the count increment the position in the array add to that value then reset its position and start rolling through the values from the lowest array position.
its not really an issue of major importance but its driving me crazy, because i just know its something so simple, and i
can not solve it myself.
i got the redirection and header insertion to work once a file is properly output so it will play back as a 16bit mono
.wav, but can't get the file generation here working right at all.
i can provide several (not properly working) source attempts
some with user variable samplerates,and lengths(simple cin)
i have if that helps, and will provide clarification if needed.
my sanity thanks you in advance,
ANSWER: Well the first point that I can make is that you might like to upgrade to a newer or alternative compiler, then the library you were interested in might built. For example there is an Express edition of MSVC++ 2005 available from Microsoft at, you can see what you get for free at There are other free compilers listed at on thefreecountry web site (home page is at

My second point is that you seem to be using 16-bit data. That is the audio samples are in 16-bit sized chunks, so why not use an array of 44100*5 16-bit unsigned integers, which for the MS 32-bit compilers would be values of type unsigned short int.

You can then easily create the saw-tooth wave you seem to describe by just incrementing the value stored in each successive array element.

Or were you specifically trying for some other wave shape and I misunderstood what you were trying to achieve?

Actually the more I read your question the more confused I become as to whether you are trying to iterate through all values of a very large integer or are trying to create audio programmatically.

Assuming you are trying to create audio programmatically, then in my solution you would do something like:

   typedef unsigned short  SampleType;

   unsigned int const NumberOfSamples( 44100*5 );

   SampleType samples[ NumberOfSamples ];

   SampleType offset(0);
   for ( unsigned int i(0); i < NumberOfSamples; ++i )
       samples[i] = SampleType(i) + offset;

I added an offset value that can be used to offset the start value. So setting it to 60000 would start the sequence at 60000 instead of 0.

The loop variable i will run from 0 to 220499 inclusive. These are 32-bit values so I cast them to the same type as the samples. SampleType is a type alias for a 16-bit unsigned short, so it has values ranging from 0 to 65535, when i exceeds this value and is cast to a 16-bit value that value wraps back to 0. Or, to put it another way, the top 16-bits of the 32-bit value are thrown away. With an offset of 0, the values in the samples array are as follows:

samples[0] = 0
samples[1] = 1
samples[2] = 2
samples[65533] = 65533
samples[65534] = 65534
samples[65535] = 65535
samples[65536] = 0
samples[65537] = 1
samples[65538] = 2
samples[131069] = 65533
samples[131070] = 65534
samples[131071] = 65535
samples[131072] = 0
samples[131073] = 1
samples[131074] = 2
samples[196605] = 65533
samples[196606] = 65534
samples[196607] = 65535
samples[196608] = 0
samples[196609] = 1
samples[196610] = 2
samples[220497] = 23889
samples[220498] = 23890
samples[220499] = 23891

If this is not what you had in mind then please post a follow up, as I mentioned I am confused as to what you are actually trying to achieve. It helps to know this to start, in case there is another way to do it I could suggest. If I do not understand what you are trying to do I cannot give such relevant advice.

Again sorry if I have misunderstood and this is not what you were after. However it might help you see what I thought you wanted to do and you could then use it as a basis for correcting me in a follow up question.

---------- FOLLOW-UP ----------

QUESTION: /*well the simplest way to describe the intent would be comparing audio data of a given length to a cryptographic key,
both have a finite number of possibilities, but unlike brute forcing a cryptokey, all the possible answers for the keyspace of an audio file of a given bitrate*samplerate*time would potentially be usable(even if incredibly space innefficient).
the approach i took was to create an unsigned integer array with ((desired samplerate * desired bitrate *length in seconds per output)/32bit integer size)positions in the array.
i then set out to start making it roll through all the bits in the array as though it were a single large binary number counting up from 0(as this would result in every possible combination) writing every array element sequentially to a file after every 1 bit increment in overall value.*/

roughly i was doing something like this:

unsigned int position;
unsigned int samples;
unsigned int size;
unsigned int i;
unsigned int k;
unsigned int j;
unsigned int l;
unsigned int seconds;
unsigned int intmax;

int main (void)
  cout <<"enter samplerate:";
  cin >> samplerate;
  cout << /n << "enter seconds:"
  cin >> seconds;
  i = 0;
  intmax = (i-1);
  i = 0;
  size = (samples * seconds);
  unsigned int samplearray[size];
  for (i=0; i<size; i++)
     samplearray[size] = 0;//init array to zero

  while(j < size)//run until all array positions = their largest values
        samplearray[position]=k;//increment through values of current array position
        for(l=0;l<size;l++)//loop through writing the array to file
         write ios::bin samplearray[l] to file output.txt //psuedocode for file output
         //this is where i keep having it fall apart. once i get the current position to its max value, i need to increment
     //the array position add to that value if it is not at int max, then decrement the array position and loop through that position
     //again then repeat. if the value after incrementing position is at its max i need to increment position again
     //check the value etc, and once we have a non max value, increment the value of that position, and loop back through
     //the array decrementing position and resetting their values to 0, until i get to the first element again.
     //this continues until all combinations of values for all positions have been output.
     // i planned to use bitwise inversion to halve the number of needed iterations, and add a user intervention
     //pause after every 500 or so files have been output. but i keep losing it on the recursion to handle this

     //this is the test for all array positions at final value to continue or end the while loop
        if samplearray[i]==intmax
     if k!=size

//making the 32bit segments into 16bit wav chunks is trivial, just open the file insert the wav header, then move a pointer
//2bytes and insert the chunk header and repeat, or alternately turn it into stereo by alternating the header for each
//channel every other two bytes. this also leaves open ladling it out as 8 bit mono or stereo, or even 32 bit.
// the only difference those alterations make is the run length for my purpose. its the bit faucet here that has me stuck
//and i just know once i explain it i am gonna be smacking my forehead and proclaiming d'oh!


OK, I am still not 100% certain I have understood exactly what you are trying to do and what you are having a problem with but as far as I can tell:

1/ From the point of view of what you are stuck with the audio is a bit of a red herring.

2/ What you really wish to know is how to perform increment operations for big integers spanning more than one primitive (i.e. built in) integer type value.

BTW, this will not work:

  unsigned int samplearray[size];

The size value is not constant so the array cannot be sized by the compiler at compile time. It therefore has to be allocated at runtime:

  unsigned int * samplearray = new unsigned int[size];

It will then need deleting when you are finished with it:

    delete [] samplearray;

Alternatively use an array form of smart pointer such as boost::scoped_array or boost::shared_array (see the Boost libraries at

Or use a std::vector.

On an aside, have you considered how long it will take to iterate through all combinations of a 3528000 bit number? (if indeed that is in fact what you are trying to do).

Remember that is 2 to the power 3528000. You might like to try it with all combinations of a single 32-bit number to start with i.e. execute a loop to increment an unsigned int from 0 until it reaches 0 (yes integers will wrap in this way) again viz:

   #include <ctime>    // for clock & CLOCKS_PER_SEC
   #include <iostream> // for std::cout

   int main()
       unsigned int v(0);
       clock_t start_tic( clock() );
       while ( v != 0 )
       clock_t end_tic( clock() );

       std::cout << v << " Elapsed time: "
         << (end_tic-start_tic)/double(CLOCKS_PER_SEC)
         << "\n";

       return 0; // for VC6.0; Not required for standard C/C++

On my system a release build using my release settings for MSVC++ 2005 took about three and a half seconds (this is believable as I have 2.4 GHz processors hence it takes 2 to 3 processor clock ticks per iteration). Note that I had to use v outside the loop to prevent the optimiser from eliminating the loop all together.

A 64-bit range will take more than 4 billion times this time, which by my calculations is around 15 billion seconds or 4175662 hours or 173985 days or 476 years. And this is doing nothing other than incrementing a single value. So I reckon that your program will probably take more time to run than any of us have, possibly more time than the universe has!

OK, back to main theme.

What you need to detect are the carry operations. These occur when individual unsigned integer values go from all ones to all zeros, or if the value after is less than the value before. You can also use this method to check for loop termination (i.e. detecting when all the combinations have been iterated through).

The way to do this, at least to start with, is to separate this off into a function of its own. You can then apply it to as many items as required – as adding one to certain values will cause a cascade of carry and add operations (you might like to study a processor instruction set, you will find such operations as add and add with carry, as well as a carry flag bit in a status register).

The increment with carry output function will look something like this:

   bool increment( unsigned int & v )
       return ++v == 0;

That is we increment the value passed in by reference and then compare the value to 0, and return true if it is. The only time incrementing an unsigned value will make it zero is if it were incremented from its maximum, all 1 bits value. Any other starting value, including 0, will yield a larger value. That is we return true if the increment caused an overflow and a carry operation is required.

We can re-phrase the 32-bit range count loop timer code using it like so:

   inline bool increment( unsigned int & v )
       return ++v == 0;

   int main()
       unsigned int v(0);
       clock_t start_tic( clock() );
       while ( !increment(v) )
       clock_t end_tic( clock() );

       std::cout << v << " Elapsed time: "
         << (end_tic-start_tic)/double(CLOCKS_PER_SEC)
         << " seconds.\n";

       return 0; // for VC6.0; Not required for standard C/C++


Note that for efficiency I have made the increment function inline. This code ran as fast as the original example on my system.

Now to use increment with multiple integer values we just keep calling it for successive values while increment returns true (i.e. while a carry is required), thus:

   carry = true;
   for ( unsigned int i(0); i < size && carry; ++i )
       carry = increment( samplearray[i] );

We increment the first value in the array and then each subsequent value in the array while increment returns true. We continue until carry is false (i.e. no further carry required) or we reach the end of the array.

After the loop carry will be false if the last value did not require a carry and true if it did. If this last value did require a carry then it must be the final value in the sample array and assuming we started with all zeros we have iterated around all combinations of bits for all values in the array and the array once again contains all zeros. Thus we can use this information to terminate the outer incrementing loop thus:

   bool carry( false );
   while ( !carry )
   // Do stuff with samples values

   // Increment samples
       carry = true;
       for ( unsigned int i(0); i < size && carry; ++i )
         carry = increment( samplearray[i] );

We could even wrap this logic up in another function:

   inline bool increment( unsigned int v[], unsigned int size )
       bool carry( true );
       for ( unsigned int i(0); i < size && carry; ++i )
         carry = increment( v[i] );
       return carry;

Which reduces our loop to:

       while ( !increment(samplearray, size) )
       // Do stuff with sample values

However I should point out that the compiler may decide that this second overload of the increment function is too complex to inline and call it as a regular function thus incurring a call overhead. Check out the inlining options for VC6.

I tested this logic using an array of 4 unsigned char samples (I wanted it to complete in my lifetime!). It also happens to be the same bit length as an unsigned int for this compiler (4*8 == 1*32), so allows a comparison with the original example’s timings. Using my VC++ 2005 release settings both versions took 11 seconds, 3 or more times that of the original, hence the extra logic incurs quite an overhead (I also suppose it means the compiler inlined the array version of the increment function in this case).

If I still have not understood what you are trying to do and having problems with or you need further explanations on anything I have covered here then please ask further follow-up questions. I think this is nearer to what you wanted though.  


All Answers

Answers by Expert:

Ask Experts


Ralph McArdell


I am a software developer with more than 15 years C++ experience and over 25 years experience developing a wide variety of applications for Windows NT/2000/XP, UNIX, Linux and other platforms. I can help with basic to advanced C++, C (although I do not write just-C much if at all these days so maybe ask in the C section about purely C matters), software development and many platform specific and system development problems.


My career started in the mid 1980s working as a batch process operator for the now defunct Inner London Education Authority, working on Prime mini computers. I then moved into the role of Programmer / Analyst, also on the Primes, then into technical support and finally into the micro computing section, using a variety of 16 and 8 bit machines. Following the demise of the ILEA I worked for a small company, now gone, called Hodos. I worked on a part task train simulator using C and the Intel DVI (Digital Video Interactive) - the hardware based predecessor to Indeo. Other projects included a CGI based train simulator (different goals to the first), and various other projects in C and Visual Basic (er, version 1 that is). When Hodos went into receivership I went freelance and finally managed to start working in C++. I initially had contracts working on train simulators (surprise) and multimedia - I worked on many of the Dorling Kindersley CD-ROM titles and wrote the screensaver games for the Wallace and Gromit Cracking Animator CD. My more recent contracts have been more traditionally IT based, working predominately in C++ on MS Windows NT, 2000. XP, Linux and UN*X. These projects have had wide ranging additional skill sets including system analysis and design, databases and SQL in various guises, C#, client server and remoting, cross porting applications between platforms and various client development processes. I have an interest in the development of the C++ core language and libraries and try to keep up with at least some of the papers on the ISO C++ Standard Committee site at


©2016 All rights reserved.