Counting down an integer vector from the highest degree (111) to the lowest degree (000)

[Matt Chwastek]

Anyone who can help,

I am curretnly attempting to write some code that will allow iteration
using a vector<int> from the highest possilbe degree of a combination
of ones & zeros (111, 110, 101, 011, 100, 010, 001, 000). The ordering
of element containing the same number of ones is not important to the
code, just the fact that the highest number of ones are iterated first.


I would prefer not to use a binary string as eventually the
combinations will change to combination of any numbers (0,1,2,3,etc.)

I have looked at several implementation of Gray Codes, but have not
been able to figure out a way to complete this iteration cleanly.

Any help or suggestions on where else to look would be greatly
appreciated.

Thanks

Matt

 

[BobR]

Matt Chwastek wrote in message

Anyone who can help,

I am curretnly attempting to write some code that will allow iteration
using a vector<int> from the highest possilbe degree of a combination
of ones & zeros (111, 110, 101, 011, 100, 010, 001, 000). The ordering
of element containing the same number of ones is not important to the
code, just the fact that the highest number of ones are iterated first.

I would prefer not to use a binary string as eventually the
combinations will change to combination of any numbers (0,1,2,3,etc.)

I have looked at several implementation of Gray Codes, but have not
been able to figure out a way to complete this iteration cleanly.

Any help or suggestions on where else to look would be greatly
appreciated.
Thanks
Matt

Maybe the 'std::bitset' could help you:

std::vector<int> Vint;
// fill the Vint object.
std::bitset<32> Sbit;
Sbit = Vint.at(0);
size_t Count = Sbit.count(); // number of bits that are set

 

[Jim Langston]

Anyone who can help,

I am curretnly attempting to write some code that will allow iteration
using a vector<int> from the highest possilbe degree of a combination
of ones & zeros (111, 110, 101, 011, 100, 010, 001, 000). The ordering
of element containing the same number of ones is not important to the
code, just the fact that the highest number of ones are iterated first.


I would prefer not to use a binary string as eventually the
combinations will change to combination of any numbers (0,1,2,3,etc.)

I have looked at several implementation of Gray Codes, but have not
been able to figure out a way to complete this iteration cleanly.

Any help or suggestions on where else to look would be greatly
appreciated.

Thanks

Matt

It could be done with very funky math, or simply converting the int to a
string, then counting.

I'm sure you can optimize this quite well:

#include <iostream>
#include <sstream>

int CountDigits( const int Value, const int Check )
{
if ( Check < 0 || Check > 9 )
return 0;
char CheckDigit = '0' + Check;

std::stringstream ConvertToStr;
ConvertToStr << Value;
std::string StrInt;
ConvertToStr >> StrInt;

int NumOfDigits = 0;
std::string::size_type Pos = 0;
while ( Pos != std::string::npos )
{
Pos = StrInt.find( CheckDigit, Pos );
if ( Pos != std::string::npos )
{
++Pos;
++NumOfDigits;
}
}

return NumOfDigits;

}

int main()
{
int CheckThis = 1011010;
std::cout << "Number of 1's in " << CheckThis << " is " <<
CountDigits( CheckThis, 1 ) << "\n";
std::cout << "Number of 0's in " << CheckThis << " is " <<
CountDigits( CheckThis, 0 ) << "\n";
std::cout << "Number of 9's in " << CheckThis << " is " <<
CountDigits( CheckThis, 9 ) << std::endl;

std::string wait;
std::getline( std::cin, wait );
}

 

[Jim Langston]

It could be done with very funky math, or simply converting the int to a
string, then counting.

I'm sure you can optimize this quite well:

#include <iostream>
#include <sstream>

int CountDigits( const int Value, const int Check )
{
if ( Check < 0 || Check > 9 )
return 0;
char CheckDigit = '0' + Check;

std::stringstream ConvertToStr;
ConvertToStr << Value;
std::string StrInt;
ConvertToStr >> StrInt;

int NumOfDigits = 0;
std::string::size_type Pos = 0;
while ( Pos != std::string::npos )
{
Pos = StrInt.find( CheckDigit, Pos );
if ( Pos != std::string::npos )
{
++Pos;
++NumOfDigits;
}
}

return NumOfDigits;

}

int main()
{
int CheckThis = 1011010;
std::cout << "Number of 1's in " << CheckThis << " is " <<
CountDigits( CheckThis, 1 ) << "\n";
std::cout << "Number of 0's in " << CheckThis << " is " <<
CountDigits( CheckThis, 0 ) << "\n";
std::cout << "Number of 9's in " << CheckThis << " is " <<
CountDigits( CheckThis, 9 ) << std::endl;

std::string wait;
std::getline( std::cin, wait );
}

Here's a little better while loop (I had actually tried this before but it
wasn't working, I forgot that != seems to take precidence over = )

#include <iostream>
#include <sstream>

int CountDigits( const int Value, const int Check )
{
if ( Check < 0 || Check > 9 )
return 0;
char CheckDigit = '0' + Check;

std::stringstream ConvertToStr;
ConvertToStr << Value;
std::string StrInt;
ConvertToStr >> StrInt;

int NumOfDigits = 0;
std::string::size_type Pos = std::string::npos;
while ( (Pos = StrInt.find( CheckDigit, Pos + 1 )) !=
std::string::npos )
{
++NumOfDigits;
}

return NumOfDigits;

}

int main()
{
int CheckThis = 1011010;
std::cout << "Number of 1's in " << CheckThis << " is " <<
CountDigits( CheckThis, 1 ) << "\n";
std::cout << "Number of 0's in " << CheckThis << " is " <<
CountDigits( CheckThis, 0 ) << "\n";
std::cout << "Number of 9's in " << CheckThis << " is " <<
CountDigits( CheckThis, 9 ) << std::endl;

std::string wait;
std::getline( std::cin, wait );
}

 

[Matt Chwastek]

The problem with converting a value to a string is that in the form of
the problem which I am trying to implement consecutive values (i.e. 8,9
or 255, 256) do not follow the path through which the iteration is
intended

I am trying to implement in code a graph theoretic problem where the
highest degree combinations (i.e. largest number of 1s in the sequence)
are iterated first.

For example:

In the case of a vector of size 10 the iteration would begin with the
vector [1 1 1 1 1 1 1 1 1 1], whose degree is 10, and the next 10
iterations would contain all unique combinations of 9 1s in the vector
of size 10, i.e. [1 1 1 1 1 1 1 1 1 0], [1 1 1 1 1 1 1 0 1], etc,
whose degree is 9. The iteration would continue in the manner until it
reached [0 0 0 0 0 0 0 0 0] whose degree is 0.

So far it seems to me to be very difficult to implement this in the
code, and being as I could be described as a novice when it comes to
programming, any help would be greatly appreciated.

Thanks for your help

 

[Victor Bazarov]

The problem with converting a value to a string is that in the form of
the problem which I am trying to implement consecutive values (i.e.
8,9 or 255, 256) do not follow the path through which the iteration is
intended

I am trying to implement in code a graph theoretic problem where the
highest degree combinations (i.e. largest number of 1s in the
sequence) are iterated first.

For example:

In the case of a vector of size 10 the iteration would begin with the
vector [1 1 1 1 1 1 1 1 1 1], whose degree is 10, and the next 10
iterations would contain all unique combinations of 9 1s in the vector
of size 10, i.e. [1 1 1 1 1 1 1 1 1 0], [1 1 1 1 1 1 1 0 1], etc,
whose degree is 9. The iteration would continue in the manner until
it reached [0 0 0 0 0 0 0 0 0] whose degree is 0.

So far it seems to me to be very difficult to implement this in the
code, and being as I could be described as a novice when it comes to
programming, any help would be greatly appreciated.

Thanks for your help

If you know the number of 0s and 1s in your string, you can *easily*
enumerate (go through) all combinations of those using 'next_permutation'
function:

#include <algorithm>
#include <string>
#include <iostream>

int main()
{
std::string a("00011111");
do {
std::cout << a << std::endl;
}
while (std::next_permutation(a.begin(), a.end()));
}

(the length of the string is the total number of your digits, and you
need to set the *first* N chars of it to '0', and the rest to '1').

The only difference I see in this from your requirements is that for
any certain number of 0s and 1s, using 'next_permutation' counts
*forward* in terms of the value of the resulting binary number, not
back. But I am sure you can overcome that tiny obstacle.

Good luck!

V

 

[Michael Angelo Ravera]

The problem with converting a value to a string is that in the form of
the problem which I am trying to implement consecutive values (i.e. 8,9
or 255, 256) do not follow the path through which the iteration is
intended

I am trying to implement in code a graph theoretic problem where the
highest degree combinations (i.e. largest number of 1s in the sequence)
are iterated first.

For example:

In the case of a vector of size 10 the iteration would begin with the
vector [1 1 1 1 1 1 1 1 1 1], whose degree is 10, and the next 10
iterations would contain all unique combinations of 9 1s in the vector
of size 10, i.e. [1 1 1 1 1 1 1 1 1 0], [1 1 1 1 1 1 1 0 1], etc,
whose degree is 9. The iteration would continue in the manner until it
reached [0 0 0 0 0 0 0 0 0] whose degree is 0.

So far it seems to me to be very difficult to implement this in the
code, and being as I could be described as a novice when it comes to
programming, any help would be greatly appreciated.

Thanks for your help

There are several reasonable approaches to this problem depending upon
whether you have rooms to save the entire enumeration or not.

If you have room to save your entire enumeration, you can simply
generate your entire enumeration, score the values as to how high they
are ranked as you generate them and sort them. This will extend well
when you have values other than just one and zero also. It will always
work as long as

If you don't have room to save the entire enumeration and sort it,
there is a better way:
You have to create a function that maps an integer between 0 and one
less than the number of vectors that you care about into the vector.
This is done by what is known as the "Principle of Vacant Spaces"

To do the latter, for the binary case, you have to recognize that if
*I* is less than the sum of the number of combinations of "N* (the
length of your vector) things taken *M* at a time varying M from 0 by 1
until the sum is greater than or equal to *I*, that there are *M* zeros
in the vector. Now you just have to figure out how to distribute those
*M* according to how big the residue is from the previous sum.

If you are just trying to generate them all, you skip the first
caluclation and set up a loop like this:
for (i = 0; i < vsize; i ++)
{
max_combin = combin (vsize, i);
for (j = 0; j < max_combin; j ++)
{
distribzeros (vsize, i, j);
}
}

Now you just have to make distribzeros generate a vector that is the
jth one that has that many zeros. I'll give you a better answer later
(after you've had a moment to think about how this works).