Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Counting down an integer vector from the highest degree (111) to the lowest degree (000)

Reply
Thread Tools

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

 
 
Matt Chwastek
Guest
Posts: n/a
 
      11-15-2006
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

 
Reply With Quote
 
 
 
 
BobR
Guest
Posts: n/a
 
      11-15-2006

Matt Chwastek wrote in message
<(E-Mail Removed) .com>...
>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

--
Bob R
POVrookie


 
Reply With Quote
 
 
 
 
Jim Langston
Guest
Posts: n/a
 
      11-15-2006
"Matt Chwastek" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) oups.com...
> 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 );
}


 
Reply With Quote
 
Jim Langston
Guest
Posts: n/a
 
      11-15-2006

"Jim Langston" <(E-Mail Removed)> wrote in message
news:FTJ6h.31$(E-Mail Removed)...
> "Matt Chwastek" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed) oups.com...
>> 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 );
}


 
Reply With Quote
 
Matt Chwastek
Guest
Posts: n/a
 
      11-20-2006
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

 
Reply With Quote
 
Victor Bazarov
Guest
Posts: n/a
 
      11-20-2006
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


 
Reply With Quote
 
Michael Angelo Ravera
Guest
Posts: n/a
 
      11-20-2006

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).

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
converting MCSE degree to university degree mcp farahani MCSE 2 11-13-2009 06:53 PM
sort a number highest to lowest rhitz1218@gmail.com C Programming 17 12-11-2006 04:25 AM
Free memory allocate by a STL vector, vector of vector, map of vector Allerdyce.John@gmail.com C++ 8 02-18-2006 12:48 AM
counting up instead of counting down edwardfredriks Javascript 6 09-07-2005 03:30 PM
New Zealand, on the other hand, has one of the lowest growth rates and one of the lowest levels of broadband penetration in the world. punlic NZ Computing 6 05-02-2004 10:28 AM



Advertisments