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. 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
    #1
    1. Advertising

  2. Matt Chwastek

    BobR Guest

    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

    --
    Bob R
    POVrookie
    BobR, Nov 15, 2006
    #2
    1. Advertising

  3. Matt Chwastek

    Jim Langston Guest

    "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
    #3
  4. Matt Chwastek

    Jim Langston Guest

    "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
    #4
  5. 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
    #5
  6. 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
    #6
  7. 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
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. sort a number highest to lowest

    , Dec 10, 2006, in forum: C Programming
    Replies:
    17
    Views:
    598
    santosh
    Dec 11, 2006
  2. rote
    Replies:
    3
    Views:
    421
    Mark Rae [MVP]
    Jan 24, 2008
  3. lector

    storing 1,000,000 records

    lector, Apr 6, 2008, in forum: C Programming
    Replies:
    19
    Views:
    465
    Barry Schwarz
    Apr 8, 2008
  4. Ruby Quiz

    [QUIZ] Counting Toothpicks (#111)

    Ruby Quiz, Jan 26, 2007, in forum: Ruby
    Replies:
    47
    Views:
    363
    Marcel Ward
    Jan 31, 2007
  5. Ruby Quiz
    Replies:
    2
    Views:
    95
    James Edward Gray II
    Feb 2, 2007
Loading...

Share This Page