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

Discussion in 'C++' started by Matt Chwastek, Nov 15, 2006.

1. ### Matt ChwastekGuest

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

Matt Chwastek, Nov 15, 2006

2. ### BobRGuest

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

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

--
Bob R
POVrookie

BobR, Nov 15, 2006

3. ### Jim LangstonGuest

"Matt Chwastek" <> wrote in message
news:...
> 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, Nov 15, 2006
4. ### Jim LangstonGuest

"Jim Langston" <> wrote in message
news:FTJ6h.31\$...
> "Matt Chwastek" <> wrote in message
> news:...
>> 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 );
> }

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 );
}

Jim Langston, Nov 15, 2006
5. ### Matt ChwastekGuest

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

Matt Chwastek, Nov 20, 2006
6. ### Victor BazarovGuest

Matt Chwastek wrote:
> 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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

Victor Bazarov, Nov 20, 2006
7. ### Michael Angelo RaveraGuest

Matt Chwastek wrote:
> 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).

Michael Angelo Ravera, Nov 20, 2006