Как я могу изменить повторяющиеся элементы в векторе целых, чтобы значения не повторялись при сохранении количества элементов и монотонности?

Question

У меня есть код, который генерирует распределение N с плавающей запятой от 0 до 1 на основе параметризованного уравнения. Они нужны мне как 8-битные целочисленные значения, поэтому после этого я масштабирую их до 255 и округляю до ближайшего целого. Мне также нужно, чтобы они были уникальными без повторяющихся значений. Тестировать дубликаты и удалять их довольно тривиально, однако мне нужно сохранить исходный размер числа N точек распространения. В некоторых случаях у меня уже может быть уникальный набор, в этом случае никаких действий не требуется:

0 3 15 40 78 128 177 215 240 252 255 -> Без оп

Но иногда я могу получить что-то вроде:

0 0 0 2 21 128 234 253 255 255 255

В этом случае я хотел бы получить набор, который выглядит следующим образом:

0 1 2 3 21 128 234 252 253 254 255

Я корректирую каждое повторяющееся значение на минимум, необходимый для того, чтобы оно было уникальным, и в то же время поддерживаю монотонный порядок, а также исходное количество точек.

Итак, слева направо мне нужно увеличить первое значение повтора на 1 и так далее. Но обратите внимание, что 4-й элемент равен 2, поэтому мне также необходимо учитывать возможность создания дубликата при увеличении других значений.

Но с правой стороны 255 - это мое максимально возможное значение, поэтому мне нужно, чтобы они опустились на 1, двигаясь влево.

В настоящее время я использую Eigen в качестве контейнера Vector, но я могу использовать все что угодно в STL.

Другие сложности состоят в том, что я не могу заранее знать количество исходных точек, N, которые могут быть любым положительным целым числом от 2 до 255.

Другая, возможно, важная и полезная деталь может заключаться в том, что мой оригинальный набор двойных значений от 0 до 1 гарантированно будет уникальным и монотонно увеличивающимся. Я не знаю, как это можно использовать, но вполне приемлемо пытаться учесть повторы до масштабирования до 255, если есть лучшее решение.

Вот код, который в настоящее время генерирует набор распределения значений типа double, а затем масштабирует его до целых чисел:

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;

Заранее спасибо за помощь.

Answer 1

Вы можете сделать это, начав с вектора 0,1,...,255, перемешать его, а затем отсортировать N первых элементов. Сортировка может быть выполнена за постоянное время с использованием префикса 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";
  }
}

Чтобы заставить begin()/end()/range-for-loop работать, вам нужна голова Эйгена, но вы можете заменить формирователи на vec.data(), vec.data()+vec.size(), а позднее - на классический цикл for.

Answer 2

Ответ, который дал @paddy, - это то, на чем я основывал свое решение. Для полноты сообщества ниже приведен фактический код, который решил проблему для меня. Я уверен, что он не самый эффективный, но он выполняет свою работу и имеет достаточную производительность для наборов данных менее 1000, как в моем случае.

Предполагается, что мои данные о проблемах хранятся в 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;
    }

}

Answer 3

Самый простой способ сделать это - сделать два прохода над массивом, предполагая, что он отсортирован для начала:

• прямой проход, изменяет A[n] = A[n-1] + 1 при A[n] <= A[n-1] и зажимает до 255
• обратный проход, изменяет A[n] = A[n+1] - 1, когда A[n] >= A[n+1] и (опционально) зажимает до 0

При условии, что длина вашего массива равна 256 или меньше, это гарантирует, что все элементы будут уникальными.

Это не обязательно является оптимальным и не гарантирует, что скорректированные значения будут максимально приближены к их первоначальному значению, насколько это возможно, но это не является одним из ваших требований.

Что-нибудь более умное, чем это, может потребовать значительных усилий.