dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 14 of 14

Thread: How to avoid cross comparisons in permutation finding?

  1. #1
    Join Date
    Dec 2010
    Posts
    907

    How to avoid cross comparisons in permutation finding?

    If I have a set of values to compare with itself,
    say a tuple of 4 integers,
    The permutation is
    4x4/2 = 8
    where 1,2 == 2,1
    if I compare this set in C++
    Code:
    for (auto& : values)
      for (auto& : values)
             .........
    I don't want to do this, How can I drop the unwanted combinations in this permutation test?

  2. #2
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626

    Re: How to avoid cross comparisons in permutation finding?

    don't generate them in the first place ?

    see this for a possible implementation using STL
    http://www.cplusplus.com/reference/a...t_permutation/

  3. #3
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: How to avoid cross comparisons in permutation finding?

    Quote Originally Posted by lucky6969b View Post
    If I have a set of values to compare with itself,
    say a tuple of 4 integers,
    The permutation is
    4x4/2 = 8
    where 1,2 == 2,1
    Not even. It's 6 if you don't want dupes, and 10 if you allow them.

    Also, please don't use the word "tuple" if you don't have an actual C++ Tuple. It's confusing (I'm making the assumption you don't have a tuple, as the code you posted would not have actually worked).

    Quote Originally Posted by lucky6969b View Post
    if I compare this set in C++
    Code:
    for (auto& : values)
      for (auto& : values)
             .........
    I don't want to do this, How can I drop the unwanted combinations in this permutation test?
    C++11 is nice and all, but iterators still exist and are still your friend. If you want all non-ordered combination of a certain size of a set of values, then just have iterators start at (or after) the index of the current iterator.

    Code:
    #include <iostream>
    #include <vector>
    
    int main()
    {
        std::vector<int> values{1, 2, 3, 4};
       
        const auto it_end= values.cend();
        for (auto it_1 = values.cbegin(); it_1 != it_end; ++it_1) {
            for (auto it_2 = std::next(it_1); it_2 != it_end; ++it_2) {
                std::cout << *it_1 << " " << *it_2 << std::endl;
            }   
       }
    }
    If you want duplictes, then remove the "std::next" call. If you need more width, add more loops. There are also ways to make this work for any arbitrary (and run-time define) widths, but I don't think you need that.
    Is your question related to IO?
    Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  4. #4
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: How to avoid cross comparisons in permutation finding?

    Quote Originally Posted by OReubens View Post
    don't generate them in the first place ?

    see this for a possible implementation using STL
    http://www.cplusplus.com/reference/a...t_permutation/
    That's not what he's asking for though. Although he *did* say permutations, it's more like he's asking for combinations.
    Is your question related to IO?
    Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  5. #5
    Join Date
    Jun 2015
    Posts
    208

    Re: How to avoid cross comparisons in permutation finding?

    Quote Originally Posted by monarch_dodra View Post
    C++11 is nice and all, but iterators still exist and are still your friend.
    Also integers still exist and are your friend.

    Code:
        std::vector<int> values{1, 2, 3, 4};
    
        const int N = int(values.size());
        for (int i=0; i<N; ++i) {
            for (int j=i+1; j<N; ++j) {
                std::cout << values[i] << " " << values[j] << std::endl;
            }
        }
    This is a little more general since it's not based on the actual values in the values array, only how many they are.

    Essentially this algorithm finds all 2-sets in an N-set. There are N over 2 such sets which equals N(N-1)/2.

  6. #6
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: How to avoid cross comparisons in permutation finding?

    Quote Originally Posted by tiliavirga View Post
    Also integers still exist and are your friend.

    This is a little more general since it's not based on the actual values in the values array, only how many they are.
    Literally the exact same algorithm. Except it's *less* general as it requires an RA container.
    Is your question related to IO?
    Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  7. #7
    Join Date
    Dec 2010
    Posts
    907

    Re: How to avoid cross comparisons in permutation finding?

    Thanks buddies, Glad to have all the terms and algorithms cleared
    Jack

  8. #8
    Join Date
    Jun 2015
    Posts
    208

    Re: How to avoid cross comparisons in permutation finding?

    Quote Originally Posted by monarch_dodra View Post
    Literally the exact same algorithm. Except it's *less* general as it requires an RA container.
    Well, then less is more since my algorithm is independent of any container. All you need is the number N.
    Last edited by tiliavirga; September 23rd, 2015 at 06:22 PM.

  9. #9
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: How to avoid cross comparisons in permutation finding?

    Quote Originally Posted by tiliavirga View Post
    Well, then less is more since my algorithm is independent of any container. All you need is the number N.
    Yes. So independent in fact it will also magically work on std::list. Or std::set. Or boost::counting_iterator. Or boost::filter_iterator.

    I think you should read up on iterators (https://en.wikipedia.org/wiki/Iterator_pattern) and how they actually improve genericity by decoupling your algorithms from your containers. Your code snippet is quite the opposite from that.
    Is your question related to IO?
    Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  10. #10
    Join Date
    Jun 2015
    Posts
    208

    Re: How to avoid cross comparisons in permutation finding?

    Quote Originally Posted by monarch_dodra View Post
    Your code snippet is quite the opposite from that.
    Your iterator version decouples the algorithm from the use of a specific container but the iterators still need to work on some container. My version decouples the algorithm from any container at all. It's the form the algorithm would take for example in a textbook about combinatorial algorithms. It generates all k-subsets of an N-set for the special case of k=2. It's not tied down to some set implementation that supports iterators. In that sense it's more general.

    I appreciate your recommendation to read up on iterators and to return this nice gesture I recommend you to broaden your perspective on algorithms.

  11. #11
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,762

    Re: How to avoid cross comparisons in permutation finding?

    Quote Originally Posted by tiliavirga
    My version decouples the algorithm from any container at all.
    That does not sound correct to me: your version of the algorithm operates on a container that has a size() member function with operator[] for random access by 0-based index.

    Quote Originally Posted by tiliavirga
    It's the form the algorithm would take for example in a textbook about combinatorial algorithms.
    I agree, but then such textbooks tend to assume some kind of basic array, maybe using pseudocode rather than any particular programming language, leaving the reader to adapt the implementation to a desired container in a given programming language, i.e., if the container does not support random access, then the reader must take it into account rather than blindly following the pseudocode using array-style notation. monarch_dodra supplied just such an implementation for C++, adapted to all containers with forward iterators. Consequently, monarch_dodra's implementation is more general than your implementation; as algorithms they are the same; as general instructional pseudocode yours is better in that it has less reliance on C++-specific constructs. However, since this is in a C++-specific forum, the latter is not so important.
    Last edited by laserlight; September 27th, 2015 at 08:13 AM.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  12. #12
    Join Date
    Jun 2015
    Posts
    208

    Re: How to avoid cross comparisons in permutation finding?

    Quote Originally Posted by laserlight View Post
    That does not sound correct to me: your version of the algorithm operates on a container that has a size() member function with operator[] for random access by 0-based index.
    The algorithm generates all 2-sets of an N set, like

    Code:
        const int N = // any N;
        for (int i=0; i<N; ++i) {
            for (int j=i+1; j<N; ++j) {
                std::cout < "{" << i << "," << j << "}" << std::endl; // the 2-sets
            }
        }
    So the result of this algorithm are the {i,j} index sets. In the same vein the result of the other algorithm can be said to be the {it_i, it_j} iterator sets.

    My claim then was that the index solution is more general than the iterator solution simply because relative positions are more general than absolute positions. And they are indeed, but knowing that generality exists along many lines my claim was tounge-in-cheek which I though I made clear enougth by the in my post #5.
    Last edited by tiliavirga; September 29th, 2015 at 11:51 PM.

  13. #13
    Join Date
    Dec 2010
    Posts
    907

    Re: How to avoid cross comparisons in permutation finding?

    Hello,
    Code:
    for (auto it_1 = m_walkables.cbegin(); it_1 != it_end; ++it_1) {		 
    	for (auto it_2 = std::next(it_1); it_2 != it_end; ++it_2) {
    How do I do the combination finding in this order?
    set 1,2,3
    initially:
    1-1
    1-2
    1-3
    2-1
    2-2
    3-3

    now want to do
    1-3
    1-2
    1-1
    2-3
    2-2
    3-1

  14. #14
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: How to avoid cross comparisons in permutation finding?

    Come on. You should know how to iterate your for loop backwards now.

    This is standard nested iteration. What exactly is troubling you about this problem?

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)