How can I change duplicate elements in a vector of ints so no values are repeated while also maintaining the...

I have code that generates a distribution of N floating points from 0 to 1 based on a parameterized equation. I need them as 8 bit integer values so after that I scale them up to 255 and round them to the nearest int. I also need them to be unique with no repeated values. It's fairly trivial to test for duplicates and remove them, however, I need to retain the original number size of N distribution points. In some cases I may already have a unique set in which case, no action is needed:

0 3 15 40 78 128 177 215 240 252 255 -> No Op

But sometimes I may end up with something like:

0 0 0 2 21 128 234 253 255 255 255

In that case, what I would like to end up with is a set that looks like this:

0 1 2 3 21 128 234 252 253 254 255

I'm adjusting each repeated value by the minimum needed to make it unique while also maintain a monotonic order as well as the original number of points.

So, from left to right, what I need to do is increment the first repeat value by 1 and so on. But note that the 4th element is 2 so I also need to account for the possibility of creating a duplicate while incrementing other values.

But then on the right hand side, 255 is my max possible value so I need those to step down by 1 going left.

I'm currently using Eigen as the Vector container but I can use anything in STL.

Other complications are that I can't know ahead of time the number of original points, N, which can be any positive integer from from 2 to 255.

Another possibly relevant and useful detail might be that my original distribution set of doubles from 0 to 1 is guaranteed to be unique and monotonically increasing. I don't know how that can be leveraged but it's perfectly acceptable to attempt to account repeats before scaling to 255 if there is a better solution.

Here is the code that currently generates the distribution set of doubles and then scales it to ints:

Eigen::VectorXi v_i(NUMBER_OF_POINTS);  // NUMBER_OF_POINTS: int from 2 to 255

Eigen::VectorXd v_d(NUMBER_OF_POINTS);

double d;



for ( int i = 1; i < v_d.size() - 1; ++i )

    {

        d = i / ( v_d.size() - 1.0 );

        v( i ) = 1.0 / ( 1.0 + pow( d / ( 1.0 - d ), -SLOPE ) );  // SLOPE: double > 0

    }



v_d( 0 ) = 0;  // Manually setting the endpoints to 0 and 1 to avoid divide by zero error 



v_d( v_d.size() - 1 ) = 1.0;



for ( int i = 0; i < v_i.size(); ++i )

{

    v_i(i) = round( v_d( i ) * 255 );

}



std::cout << v_i << std::endl;

Thanks in advance for the help.

asked Nov 5 '18 at 23:35

Morgan

Is this even possible in the general case? What if you have a sequence 1 2 2 2 2 3? What should those interim values be converted to?

– Lightness Races in Orbit
Nov 6 '18 at 12:51

@LightnessRacesinOrbit I believe it's possible but it's a tough problem. The begining and end will always be locked to 0 and 255. So your example might look something like this 0 1 2 2 2 2 3 255. In that case I would need to increment that second 2 by 1 and then recursively increment the rest so that there are no repeats but it monotonically increases. So your example would end up like this: 0 1 2 3 4 5 6 255. I realize it may seem strange that from your example, 3 gets changed to 6 but fortunately, how close the new values are to the old values is not important.

– Morgan
Nov 6 '18 at 23:46

Okay, so changing non-repeating values is permitted.

– Lightness Races in Orbit
Nov 7 '18 at 10:42

add a comment |

0 3 15 40 78 128 177 215 240 252 255 -> No Op

But sometimes I may end up with something like:

0 0 0 2 21 128 234 253 255 255 255

In that case, what I would like to end up with is a set that looks like this:

0 1 2 3 21 128 234 252 253 254 255

I'm adjusting each repeated value by the minimum needed to make it unique while also maintain a monotonic order as well as the original number of points.

But then on the right hand side, 255 is my max possible value so I need those to step down by 1 going left.

I'm currently using Eigen as the Vector container but I can use anything in STL.

Other complications are that I can't know ahead of time the number of original points, N, which can be any positive integer from from 2 to 255.

Here is the code that currently generates the distribution set of doubles and then scales it to ints:

Eigen::VectorXi v_i(NUMBER_OF_POINTS);  // NUMBER_OF_POINTS: int from 2 to 255

Eigen::VectorXd v_d(NUMBER_OF_POINTS);

double d;



for ( int i = 1; i < v_d.size() - 1; ++i )

    {

        d = i / ( v_d.size() - 1.0 );

        v( i ) = 1.0 / ( 1.0 + pow( d / ( 1.0 - d ), -SLOPE ) );  // SLOPE: double > 0

    }



v_d( 0 ) = 0;  // Manually setting the endpoints to 0 and 1 to avoid divide by zero error 



v_d( v_d.size() - 1 ) = 1.0;



for ( int i = 0; i < v_i.size(); ++i )

{

    v_i(i) = round( v_d( i ) * 255 );

}



std::cout << v_i << std::endl;

Thanks in advance for the help.

asked Nov 5 '18 at 23:35

Morgan

Is this even possible in the general case? What if you have a sequence 1 2 2 2 2 3? What should those interim values be converted to?

– Lightness Races in Orbit
Nov 6 '18 at 12:51

@LightnessRacesinOrbit I believe it's possible but it's a tough problem. The begining and end will always be locked to 0 and 255. So your example might look something like this 0 1 2 2 2 2 3 255. In that case I would need to increment that second 2 by 1 and then recursively increment the rest so that there are no repeats but it monotonically increases. So your example would end up like this: 0 1 2 3 4 5 6 255. I realize it may seem strange that from your example, 3 gets changed to 6 but fortunately, how close the new values are to the old values is not important.

– Morgan
Nov 6 '18 at 23:46

Okay, so changing non-repeating values is permitted.

– Lightness Races in Orbit
Nov 7 '18 at 10:42

add a comment |

0 3 15 40 78 128 177 215 240 252 255 -> No Op

But sometimes I may end up with something like:

0 0 0 2 21 128 234 253 255 255 255

In that case, what I would like to end up with is a set that looks like this:

0 1 2 3 21 128 234 252 253 254 255

I'm adjusting each repeated value by the minimum needed to make it unique while also maintain a monotonic order as well as the original number of points.

But then on the right hand side, 255 is my max possible value so I need those to step down by 1 going left.

I'm currently using Eigen as the Vector container but I can use anything in STL.

Other complications are that I can't know ahead of time the number of original points, N, which can be any positive integer from from 2 to 255.

Here is the code that currently generates the distribution set of doubles and then scales it to ints:

Eigen::VectorXi v_i(NUMBER_OF_POINTS);  // NUMBER_OF_POINTS: int from 2 to 255

Eigen::VectorXd v_d(NUMBER_OF_POINTS);

double d;



for ( int i = 1; i < v_d.size() - 1; ++i )

    {

        d = i / ( v_d.size() - 1.0 );

        v( i ) = 1.0 / ( 1.0 + pow( d / ( 1.0 - d ), -SLOPE ) );  // SLOPE: double > 0

    }



v_d( 0 ) = 0;  // Manually setting the endpoints to 0 and 1 to avoid divide by zero error 



v_d( v_d.size() - 1 ) = 1.0;



for ( int i = 0; i < v_i.size(); ++i )

{

    v_i(i) = round( v_d( i ) * 255 );

}



std::cout << v_i << std::endl;

Thanks in advance for the help.

asked Nov 5 '18 at 23:35

Morgan

0 3 15 40 78 128 177 215 240 252 255 -> No Op

But sometimes I may end up with something like:

0 0 0 2 21 128 234 253 255 255 255

In that case, what I would like to end up with is a set that looks like this:

0 1 2 3 21 128 234 252 253 254 255

I'm adjusting each repeated value by the minimum needed to make it unique while also maintain a monotonic order as well as the original number of points.

But then on the right hand side, 255 is my max possible value so I need those to step down by 1 going left.

I'm currently using Eigen as the Vector container but I can use anything in STL.

Other complications are that I can't know ahead of time the number of original points, N, which can be any positive integer from from 2 to 255.

Here is the code that currently generates the distribution set of doubles and then scales it to ints:

Eigen::VectorXi v_i(NUMBER_OF_POINTS);  // NUMBER_OF_POINTS: int from 2 to 255

Eigen::VectorXd v_d(NUMBER_OF_POINTS);

double d;



for ( int i = 1; i < v_d.size() - 1; ++i )

    {

        d = i / ( v_d.size() - 1.0 );

        v( i ) = 1.0 / ( 1.0 + pow( d / ( 1.0 - d ), -SLOPE ) );  // SLOPE: double > 0

    }



v_d( 0 ) = 0;  // Manually setting the endpoints to 0 and 1 to avoid divide by zero error 



v_d( v_d.size() - 1 ) = 1.0;



for ( int i = 0; i < v_i.size(); ++i )

{

    v_i(i) = round( v_d( i ) * 255 );

}



std::cout << v_i << std::endl;

Thanks in advance for the help.

c++ vector eigen

asked Nov 5 '18 at 23:35

Morgan

asked Nov 5 '18 at 23:35

Morgan

asked Nov 5 '18 at 23:35

Morgan

asked Nov 5 '18 at 23:35

Morgan

asked Nov 5 '18 at 23:35

Morgan

Is this even possible in the general case? What if you have a sequence 1 2 2 2 2 3? What should those interim values be converted to?

– Lightness Races in Orbit
Nov 6 '18 at 12:51

@LightnessRacesinOrbit I believe it's possible but it's a tough problem. The begining and end will always be locked to 0 and 255. So your example might look something like this 0 1 2 2 2 2 3 255. In that case I would need to increment that second 2 by 1 and then recursively increment the rest so that there are no repeats but it monotonically increases. So your example would end up like this: 0 1 2 3 4 5 6 255. I realize it may seem strange that from your example, 3 gets changed to 6 but fortunately, how close the new values are to the old values is not important.

– Morgan
Nov 6 '18 at 23:46

Okay, so changing non-repeating values is permitted.

– Lightness Races in Orbit
Nov 7 '18 at 10:42

add a comment |

Is this even possible in the general case? What if you have a sequence 1 2 2 2 2 3? What should those interim values be converted to?

– Lightness Races in Orbit
Nov 6 '18 at 12:51

@LightnessRacesinOrbit I believe it's possible but it's a tough problem. The begining and end will always be locked to 0 and 255. So your example might look something like this 0 1 2 2 2 2 3 255. In that case I would need to increment that second 2 by 1 and then recursively increment the rest so that there are no repeats but it monotonically increases. So your example would end up like this: 0 1 2 3 4 5 6 255. I realize it may seem strange that from your example, 3 gets changed to 6 but fortunately, how close the new values are to the old values is not important.

– Morgan
Nov 6 '18 at 23:46

Okay, so changing non-repeating values is permitted.

– Lightness Races in Orbit
Nov 7 '18 at 10:42

Is this even possible in the general case? What if you have a sequence 1 2 2 2 2 3? What should those interim values be converted to?

– Lightness Races in Orbit
Nov 6 '18 at 12:51

@LightnessRacesinOrbit I believe it's possible but it's a tough problem. The begining and end will always be locked to 0 and 255. So your example might look something like this 0 1 2 2 2 2 3 255. In that case I would need to increment that second 2 by 1 and then recursively increment the rest so that there are no repeats but it monotonically increases. So your example would end up like this: 0 1 2 3 4 5 6 255. I realize it may seem strange that from your example, 3 gets changed to 6 but fortunately, how close the new values are to the old values is not important.

– Morgan
Nov 6 '18 at 23:46

Okay, so changing non-repeating values is permitted.

– Lightness Races in Orbit
Nov 7 '18 at 10:42

add a comment |

3 Answers
3

active

oldest

votes

The simplest way to approach this is to do two passes over the array, assuming it is sorted to begin with:

forward pass, modifies A[n] = A[n-1] + 1 when A[n] <= A[n-1] and clamps to 255

reverse pass, modifies A[n] = A[n+1] - 1 when A[n] >= A[n+1] and (optionally) clamps to 0

Provided your array length is 256 or less, this is guaranteed to make all elements unique.

It is not necessarily optimal, nor will it guarantee that adjusted values are as close to their original value as possible, but that doesn't appear to be one of your requirements.

Anything more clever than this is likely to involve a significant amount of effort.

answered Nov 5 '18 at 23:57

paddy

43k53176

Thanks, @paddy . Your answer put me in the right direction. I added my own answer with working code based on your suggestions.

– Morgan
Nov 21 '18 at 19:53

If it was helpful, consider using the voting mechanism and/or accepting this answer.

– paddy
Nov 21 '18 at 21:47

Done. Upvoted too but it doesn't show publicly due to my low rep. Thanks again!

– Morgan
Nov 22 '18 at 22:15

add a comment |

You can do this by starting with a vector of 0,1,...,255, shuffle it and then sort the N first elements. The sorting can be done is constant time using a prefix sum:

#include <random>

#include <algorithm>

#include <numeric>

#include <iterator>

#include <iostream>

#include <Eigen/Dense>

using namespace Eigen;

using namespace std;



int main()

{

  VectorXi base = VectorXi::LinSpaced(256,0,255); 

  std::random_device rd;

  std::mt19937 g(rd());

  std::shuffle(base.begin(), base.end(), g);

  int N = 10;



  std::cout << base.head(N).transpose() << "n";



  // explicit sort

  {

    VectorXi A = base.head(N);

    std::sort(A.begin(), A.end());

    std::cout << A.transpose() << "n";

  }



  // no sort but O(256) pass

  {

    VectorXi mask = VectorXi::Zero(256), pos(256);

    mask(base.head(N)).fill(1);

    std::partial_sum (mask.begin(), mask.end(), pos.begin());

    VectorXi A(N);

    for(auto i:base.head(N))

      A(pos[i]-1) = i;

    std::cout << A.transpose() << "n";

  }



  // same with fused partial_sum

  {

    VectorXi mask = VectorXi::Zero(256);

    mask(base.head(N)).fill(1);

    VectorXi A(N);

    int c = 0;

    for(int i=0,c=0; i<256; ++i)

      if(mask[i])

        A(c++) = i;

    std::cout << A.transpose() << "n";

  }

}

To make begin()/end()/range-for-loop work you need the head of Eigen, but you can replace the formers by vec.data(), vec.data()+vec.size() and the later by a classic for loop.

answered Nov 6 '18 at 12:48

ggael

20.7k23145

add a comment |

The answer that @paddy gave is what I based my solution on. For completeness to the community, below is the actual code that solved the problem for me. I'm sure it's not the most efficient but it gets the job done and has adequate performance for data sets less than 1000 as they are in my case.

Assuming I have my problem data stored in an Eigen::VectorXi v_int

Eigen::VectorXi v_int_unique = v_int; // Beginning and end values never change 

                                      // middle value won't change if v_int.size() is odd



for ( int i = 1; i < v_int.size() / 2; ++i )

{

    if ( v_int( i ) == v_int( i - 1 ) )

    {

        v_int_unique( i ) = v_int( i ) + 1;

    }



    if ( v_int( i ) < v_int_unique( i - 1 ) )

    {

        v_int_unique( i ) = v_int_unique( i - 1 ) + 1;

    }



}



for ( int i = v_int.size() - 2; i > v_int.size() / 2; --i )

{

    if ( v_int( i ) == v_int( i + 1 ) )

    {

        v_int_unique( i ) =  v_int( i ) - 1;

    }



    if ( v_int( i ) > v_int_unique( i + 1 ) )

    {

        v_int_unique( i ) = v_int_unique( i + 1 ) - 1;

    }



}

answered Nov 21 '18 at 19:51

Morgan

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53163848%2fhow-can-i-change-duplicate-elements-in-a-vector-of-ints-so-no-values-are-repeate%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

3 Answers
3

active

oldest

votes

3 Answers
3

active

oldest

votes

The simplest way to approach this is to do two passes over the array, assuming it is sorted to begin with:

forward pass, modifies A[n] = A[n-1] + 1 when A[n] <= A[n-1] and clamps to 255

reverse pass, modifies A[n] = A[n+1] - 1 when A[n] >= A[n+1] and (optionally) clamps to 0

Provided your array length is 256 or less, this is guaranteed to make all elements unique.

It is not necessarily optimal, nor will it guarantee that adjusted values are as close to their original value as possible, but that doesn't appear to be one of your requirements.

Anything more clever than this is likely to involve a significant amount of effort.

answered Nov 5 '18 at 23:57

paddy

43k53176

Thanks, @paddy . Your answer put me in the right direction. I added my own answer with working code based on your suggestions.

– Morgan
Nov 21 '18 at 19:53

If it was helpful, consider using the voting mechanism and/or accepting this answer.

– paddy
Nov 21 '18 at 21:47

Done. Upvoted too but it doesn't show publicly due to my low rep. Thanks again!

– Morgan
Nov 22 '18 at 22:15

add a comment |

The simplest way to approach this is to do two passes over the array, assuming it is sorted to begin with:

forward pass, modifies A[n] = A[n-1] + 1 when A[n] <= A[n-1] and clamps to 255

reverse pass, modifies A[n] = A[n+1] - 1 when A[n] >= A[n+1] and (optionally) clamps to 0

Provided your array length is 256 or less, this is guaranteed to make all elements unique.

It is not necessarily optimal, nor will it guarantee that adjusted values are as close to their original value as possible, but that doesn't appear to be one of your requirements.

Anything more clever than this is likely to involve a significant amount of effort.

answered Nov 5 '18 at 23:57

paddy

43k53176

Thanks, @paddy . Your answer put me in the right direction. I added my own answer with working code based on your suggestions.

– Morgan
Nov 21 '18 at 19:53

If it was helpful, consider using the voting mechanism and/or accepting this answer.

– paddy
Nov 21 '18 at 21:47

Done. Upvoted too but it doesn't show publicly due to my low rep. Thanks again!

– Morgan
Nov 22 '18 at 22:15

add a comment |

The simplest way to approach this is to do two passes over the array, assuming it is sorted to begin with:

forward pass, modifies A[n] = A[n-1] + 1 when A[n] <= A[n-1] and clamps to 255

reverse pass, modifies A[n] = A[n+1] - 1 when A[n] >= A[n+1] and (optionally) clamps to 0

Provided your array length is 256 or less, this is guaranteed to make all elements unique.

It is not necessarily optimal, nor will it guarantee that adjusted values are as close to their original value as possible, but that doesn't appear to be one of your requirements.

Anything more clever than this is likely to involve a significant amount of effort.

answered Nov 5 '18 at 23:57

paddy

43k53176

The simplest way to approach this is to do two passes over the array, assuming it is sorted to begin with:

forward pass, modifies A[n] = A[n-1] + 1 when A[n] <= A[n-1] and clamps to 255

reverse pass, modifies A[n] = A[n+1] - 1 when A[n] >= A[n+1] and (optionally) clamps to 0

Provided your array length is 256 or less, this is guaranteed to make all elements unique.

It is not necessarily optimal, nor will it guarantee that adjusted values are as close to their original value as possible, but that doesn't appear to be one of your requirements.

Anything more clever than this is likely to involve a significant amount of effort.

answered Nov 5 '18 at 23:57

paddy

43k53176

answered Nov 5 '18 at 23:57

paddy

43k53176

answered Nov 5 '18 at 23:57

paddy

43k53176

answered Nov 5 '18 at 23:57

paddy

43k53176

Thanks, @paddy . Your answer put me in the right direction. I added my own answer with working code based on your suggestions.

– Morgan
Nov 21 '18 at 19:53

If it was helpful, consider using the voting mechanism and/or accepting this answer.

– paddy
Nov 21 '18 at 21:47

Done. Upvoted too but it doesn't show publicly due to my low rep. Thanks again!

– Morgan
Nov 22 '18 at 22:15

add a comment |

Thanks, @paddy . Your answer put me in the right direction. I added my own answer with working code based on your suggestions.

– Morgan
Nov 21 '18 at 19:53

If it was helpful, consider using the voting mechanism and/or accepting this answer.

– paddy
Nov 21 '18 at 21:47

Done. Upvoted too but it doesn't show publicly due to my low rep. Thanks again!

– Morgan
Nov 22 '18 at 22:15

Thanks, @paddy . Your answer put me in the right direction. I added my own answer with working code based on your suggestions.

– Morgan
Nov 21 '18 at 19:53

If it was helpful, consider using the voting mechanism and/or accepting this answer.

– paddy
Nov 21 '18 at 21:47

Done. Upvoted too but it doesn't show publicly due to my low rep. Thanks again!

– Morgan
Nov 22 '18 at 22:15

add a comment |

You can do this by starting with a vector of 0,1,...,255, shuffle it and then sort the N first elements. The sorting can be done is constant time using a prefix sum:

#include <random>

#include <algorithm>

#include <numeric>

#include <iterator>

#include <iostream>

#include <Eigen/Dense>

using namespace Eigen;

using namespace std;



int main()

{

  VectorXi base = VectorXi::LinSpaced(256,0,255); 

  std::random_device rd;

  std::mt19937 g(rd());

  std::shuffle(base.begin(), base.end(), g);

  int N = 10;



  std::cout << base.head(N).transpose() << "n";



  // explicit sort

  {

    VectorXi A = base.head(N);

    std::sort(A.begin(), A.end());

    std::cout << A.transpose() << "n";

  }



  // no sort but O(256) pass

  {

    VectorXi mask = VectorXi::Zero(256), pos(256);

    mask(base.head(N)).fill(1);

    std::partial_sum (mask.begin(), mask.end(), pos.begin());

    VectorXi A(N);

    for(auto i:base.head(N))

      A(pos[i]-1) = i;

    std::cout << A.transpose() << "n";

  }



  // same with fused partial_sum

  {

    VectorXi mask = VectorXi::Zero(256);

    mask(base.head(N)).fill(1);

    VectorXi A(N);

    int c = 0;

    for(int i=0,c=0; i<256; ++i)

      if(mask[i])

        A(c++) = i;

    std::cout << A.transpose() << "n";

  }

}

To make begin()/end()/range-for-loop work you need the head of Eigen, but you can replace the formers by vec.data(), vec.data()+vec.size() and the later by a classic for loop.

answered Nov 6 '18 at 12:48

ggael

20.7k23145

add a comment |

You can do this by starting with a vector of 0,1,...,255, shuffle it and then sort the N first elements. The sorting can be done is constant time using a prefix sum:

#include <random>

#include <algorithm>

#include <numeric>

#include <iterator>

#include <iostream>

#include <Eigen/Dense>

using namespace Eigen;

using namespace std;



int main()

{

  VectorXi base = VectorXi::LinSpaced(256,0,255); 

  std::random_device rd;

  std::mt19937 g(rd());

  std::shuffle(base.begin(), base.end(), g);

  int N = 10;



  std::cout << base.head(N).transpose() << "n";



  // explicit sort

  {

    VectorXi A = base.head(N);

    std::sort(A.begin(), A.end());

    std::cout << A.transpose() << "n";

  }



  // no sort but O(256) pass

  {

    VectorXi mask = VectorXi::Zero(256), pos(256);

    mask(base.head(N)).fill(1);

    std::partial_sum (mask.begin(), mask.end(), pos.begin());

    VectorXi A(N);

    for(auto i:base.head(N))

      A(pos[i]-1) = i;

    std::cout << A.transpose() << "n";

  }



  // same with fused partial_sum

  {

    VectorXi mask = VectorXi::Zero(256);

    mask(base.head(N)).fill(1);

    VectorXi A(N);

    int c = 0;

    for(int i=0,c=0; i<256; ++i)

      if(mask[i])

        A(c++) = i;

    std::cout << A.transpose() << "n";

  }

}

To make begin()/end()/range-for-loop work you need the head of Eigen, but you can replace the formers by vec.data(), vec.data()+vec.size() and the later by a classic for loop.

answered Nov 6 '18 at 12:48

ggael

20.7k23145

add a comment |

You can do this by starting with a vector of 0,1,...,255, shuffle it and then sort the N first elements. The sorting can be done is constant time using a prefix sum:

#include <random>

#include <algorithm>

#include <numeric>

#include <iterator>

#include <iostream>

#include <Eigen/Dense>

using namespace Eigen;

using namespace std;



int main()

{

  VectorXi base = VectorXi::LinSpaced(256,0,255); 

  std::random_device rd;

  std::mt19937 g(rd());

  std::shuffle(base.begin(), base.end(), g);

  int N = 10;



  std::cout << base.head(N).transpose() << "n";



  // explicit sort

  {

    VectorXi A = base.head(N);

    std::sort(A.begin(), A.end());

    std::cout << A.transpose() << "n";

  }



  // no sort but O(256) pass

  {

    VectorXi mask = VectorXi::Zero(256), pos(256);

    mask(base.head(N)).fill(1);

    std::partial_sum (mask.begin(), mask.end(), pos.begin());

    VectorXi A(N);

    for(auto i:base.head(N))

      A(pos[i]-1) = i;

    std::cout << A.transpose() << "n";

  }



  // same with fused partial_sum

  {

    VectorXi mask = VectorXi::Zero(256);

    mask(base.head(N)).fill(1);

    VectorXi A(N);

    int c = 0;

    for(int i=0,c=0; i<256; ++i)

      if(mask[i])

        A(c++) = i;

    std::cout << A.transpose() << "n";

  }

}

To make begin()/end()/range-for-loop work you need the head of Eigen, but you can replace the formers by vec.data(), vec.data()+vec.size() and the later by a classic for loop.

answered Nov 6 '18 at 12:48

ggael

20.7k23145

You can do this by starting with a vector of 0,1,...,255, shuffle it and then sort the N first elements. The sorting can be done is constant time using a prefix sum:

#include <random>

#include <algorithm>

#include <numeric>

#include <iterator>

#include <iostream>

#include <Eigen/Dense>

using namespace Eigen;

using namespace std;



int main()

{

  VectorXi base = VectorXi::LinSpaced(256,0,255); 

  std::random_device rd;

  std::mt19937 g(rd());

  std::shuffle(base.begin(), base.end(), g);

  int N = 10;



  std::cout << base.head(N).transpose() << "n";



  // explicit sort

  {

    VectorXi A = base.head(N);

    std::sort(A.begin(), A.end());

    std::cout << A.transpose() << "n";

  }



  // no sort but O(256) pass

  {

    VectorXi mask = VectorXi::Zero(256), pos(256);

    mask(base.head(N)).fill(1);

    std::partial_sum (mask.begin(), mask.end(), pos.begin());

    VectorXi A(N);

    for(auto i:base.head(N))

      A(pos[i]-1) = i;

    std::cout << A.transpose() << "n";

  }



  // same with fused partial_sum

  {

    VectorXi mask = VectorXi::Zero(256);

    mask(base.head(N)).fill(1);

    VectorXi A(N);

    int c = 0;

    for(int i=0,c=0; i<256; ++i)

      if(mask[i])

        A(c++) = i;

    std::cout << A.transpose() << "n";

  }

}

To make begin()/end()/range-for-loop work you need the head of Eigen, but you can replace the formers by vec.data(), vec.data()+vec.size() and the later by a classic for loop.

answered Nov 6 '18 at 12:48

ggael

20.7k23145

answered Nov 6 '18 at 12:48

ggael

20.7k23145

answered Nov 6 '18 at 12:48

ggael

20.7k23145

answered Nov 6 '18 at 12:48

ggael

20.7k23145

add a comment |

Assuming I have my problem data stored in an Eigen::VectorXi v_int

Eigen::VectorXi v_int_unique = v_int; // Beginning and end values never change 

                                      // middle value won't change if v_int.size() is odd



for ( int i = 1; i < v_int.size() / 2; ++i )

{

    if ( v_int( i ) == v_int( i - 1 ) )

    {

        v_int_unique( i ) = v_int( i ) + 1;

    }



    if ( v_int( i ) < v_int_unique( i - 1 ) )

    {

        v_int_unique( i ) = v_int_unique( i - 1 ) + 1;

    }



}



for ( int i = v_int.size() - 2; i > v_int.size() / 2; --i )

{

    if ( v_int( i ) == v_int( i + 1 ) )

    {

        v_int_unique( i ) =  v_int( i ) - 1;

    }



    if ( v_int( i ) > v_int_unique( i + 1 ) )

    {

        v_int_unique( i ) = v_int_unique( i + 1 ) - 1;

    }



}

answered Nov 21 '18 at 19:51

Morgan

add a comment |

Assuming I have my problem data stored in an Eigen::VectorXi v_int

Eigen::VectorXi v_int_unique = v_int; // Beginning and end values never change 

                                      // middle value won't change if v_int.size() is odd



for ( int i = 1; i < v_int.size() / 2; ++i )

{

    if ( v_int( i ) == v_int( i - 1 ) )

    {

        v_int_unique( i ) = v_int( i ) + 1;

    }



    if ( v_int( i ) < v_int_unique( i - 1 ) )

    {

        v_int_unique( i ) = v_int_unique( i - 1 ) + 1;

    }



}



for ( int i = v_int.size() - 2; i > v_int.size() / 2; --i )

{

    if ( v_int( i ) == v_int( i + 1 ) )

    {

        v_int_unique( i ) =  v_int( i ) - 1;

    }



    if ( v_int( i ) > v_int_unique( i + 1 ) )

    {

        v_int_unique( i ) = v_int_unique( i + 1 ) - 1;

    }



}

answered Nov 21 '18 at 19:51

Morgan

add a comment |

Assuming I have my problem data stored in an Eigen::VectorXi v_int

Eigen::VectorXi v_int_unique = v_int; // Beginning and end values never change 

                                      // middle value won't change if v_int.size() is odd



for ( int i = 1; i < v_int.size() / 2; ++i )

{

    if ( v_int( i ) == v_int( i - 1 ) )

    {

        v_int_unique( i ) = v_int( i ) + 1;

    }



    if ( v_int( i ) < v_int_unique( i - 1 ) )

    {

        v_int_unique( i ) = v_int_unique( i - 1 ) + 1;

    }



}



for ( int i = v_int.size() - 2; i > v_int.size() / 2; --i )

{

    if ( v_int( i ) == v_int( i + 1 ) )

    {

        v_int_unique( i ) =  v_int( i ) - 1;

    }



    if ( v_int( i ) > v_int_unique( i + 1 ) )

    {

        v_int_unique( i ) = v_int_unique( i + 1 ) - 1;

    }



}

answered Nov 21 '18 at 19:51

Morgan

Assuming I have my problem data stored in an Eigen::VectorXi v_int

Eigen::VectorXi v_int_unique = v_int; // Beginning and end values never change 

                                      // middle value won't change if v_int.size() is odd



for ( int i = 1; i < v_int.size() / 2; ++i )

{

    if ( v_int( i ) == v_int( i - 1 ) )

    {

        v_int_unique( i ) = v_int( i ) + 1;

    }



    if ( v_int( i ) < v_int_unique( i - 1 ) )

    {

        v_int_unique( i ) = v_int_unique( i - 1 ) + 1;

    }



}



for ( int i = v_int.size() - 2; i > v_int.size() / 2; --i )

{

    if ( v_int( i ) == v_int( i + 1 ) )

    {

        v_int_unique( i ) =  v_int( i ) - 1;

    }



    if ( v_int( i ) > v_int_unique( i + 1 ) )

    {

        v_int_unique( i ) = v_int_unique( i + 1 ) - 1;

    }



}

answered Nov 21 '18 at 19:51

Morgan

answered Nov 21 '18 at 19:51

Morgan

answered Nov 21 '18 at 19:51

Morgan

answered Nov 21 '18 at 19:51

Morgan

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

Search This Blog

Ufyukyu