# How to avoid cross comparisons in permutation finding?

• September 22nd, 2015, 10:27 PM
lucky6969b
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?
• September 23rd, 2015, 06:53 AM
OReubens
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/
• September 23rd, 2015, 08:20 AM
monarch_dodra
Re: How to avoid cross comparisons in permutation finding?
Quote:

Originally Posted by 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

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
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.
• September 23rd, 2015, 08:22 AM
monarch_dodra
Re: How to avoid cross comparisons in permutation finding?
Quote:

Originally Posted by 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/

That's not what he's asking for though. Although he *did* say permutations, it's more like he's asking for combinations.
• September 23rd, 2015, 03:13 PM
tiliavirga
Re: How to avoid cross comparisons in permutation finding?
Quote:

Originally Posted by monarch_dodra
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.
• September 23rd, 2015, 03:30 PM
monarch_dodra
Re: How to avoid cross comparisons in permutation finding?
Quote:

Originally Posted by tiliavirga
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.
• September 23rd, 2015, 06:08 PM
lucky6969b
Re: How to avoid cross comparisons in permutation finding?
Thanks buddies, Glad to have all the terms and algorithms cleared
Jack
• September 23rd, 2015, 06:19 PM
tiliavirga
Re: How to avoid cross comparisons in permutation finding?
Quote:

Originally Posted by monarch_dodra
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.
• September 24th, 2015, 04:11 AM
monarch_dodra
Re: How to avoid cross comparisons in permutation finding?
Quote:

Originally Posted by tiliavirga
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.
• September 27th, 2015, 02:36 AM
tiliavirga
Re: How to avoid cross comparisons in permutation finding?
Quote:

Originally Posted by monarch_dodra
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.
• September 27th, 2015, 08:11 AM
laserlight
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.
• September 28th, 2015, 06:44 AM
tiliavirga
Re: How to avoid cross comparisons in permutation finding?
Quote:

Originally Posted by laserlight
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.
• October 13th, 2015, 08:17 AM
lucky6969b
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
• October 13th, 2015, 12:01 PM
monarch_dodra
Re: How to avoid cross comparisons in permutation finding?
Come on. You should know how to iterate your for loop backwards now.