How to avoid cross comparisons in permutation finding?

[lucky6969b]

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++

for (auto& : values)
  for (auto& : values)
         .........

I don't want to do this, How can I drop the unwanted combinations in this permutation test?

[OReubens]

don't generate them in the first place ?

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

[monarch_dodra]

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

if I compare this set in C++

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.

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

[monarch_dodra]

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.

[tiliavirga]

C++11 is nice and all, but iterators still exist and are still your friend.

Also integers still exist and are your friend.

    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.

[monarch_dodra]

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.

[lucky6969b]

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

[tiliavirga]

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.

[monarch_dodra]

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.

[tiliavirga]

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.

[laserlight]

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.

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.

[tiliavirga]

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

    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.

[lucky6969b]

Hello,

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

[monarch_dodra]

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?