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?

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/

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.

Re: How to avoid cross comparisons in permutation finding?

Quote:

Originally Posted by

**OReubens**

That's not what he's asking for though. Although he *did* say permutations, it's more like he's asking for combinations.

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.

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.

Re: How to avoid cross comparisons in permutation finding?

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

Jack

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.

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.

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.

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.

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.

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

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?