454,605 Members | 1,391 Online
Need help? Post your question and get tips & solutions from a community of 454,605 IT Pros & Developers. It's quick & easy.

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

 P: n/a Anyone who can help, I am curretnly attempting to write some code that will allow iteration using a vector
6 Replies

 P: n/a Matt Chwastek wrote in message <11**********************@k70g2000cwa.googlegroups .com>... >Anyone who can help,I am curretnly attempting to write some code that will allow iterationusing a vector

 P: n/a "Matt Chwastek" #include 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 ); } Nov 15 '06 #3

 P: n/a "Jim Langston" Anyone who can help,I am curretnly attempting to write some code that will allow iterationusing a vector #include 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 #include 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 ); } Nov 15 '06 #4

 P: n/a 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 Nov 20 '06 #5

 P: n/a 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 #include #include 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 Nov 20 '06 #6

 P: n/a 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). Nov 20 '06 #7

### This discussion thread is closed

Replies have been disabled for this discussion.