Sequentially remove one element from a vector at a time with replacement

[LMHmedchem]

Hello,

As the title suggests, I have a vector of int,

vector<int> row_numbers{1,2,3,4,5,6,7,8,9};

I want to sequentially remove one element at a time starting with the first. When the second element is removed, the first element needs to go back in. The sequence would look like

// original vector, row_numbers.size()=9
row_numbers{1,2,3,4,5,6,7,8,9};

// trimmed vector, row_numbers_trim.size()=8
row_numbers_trim{2,3,4,5,6,7,8,9}; // 1 removed
row_numbers_trim{1,3,4,5,6,7,8,9}; // 2 removed, 1 replaced
row_numbers_trim{1,2,4,5,6,7,8,9}; // 3 removed, 2 replaced
row_numbers_trim{1,2,3,5,6,7,8,9}; // 4 removed, 3 replaced
row_numbers_trim{1,2,3,4,6,7,8,9}; // 5 removed, 4 replaced
row_numbers_trim{1,2,3,4,5,7,8,9}; // 6 removed, 5 replaced
row_numbers_trim{1,2,3,4,5,6,8,9}; // 7 removed, 6 replaced
row_numbers_trim{1,2,3,4,5,6,7,9}; // 8 removed, 7 replaced
row_numbers_trim{1,2,3,4,5,6,7,8}; // 9 removed, 8 replaced

I have been working under the assumption that the best method would be to have row_numbers remain untouched and work on a copy. For each step in the sequence, you would create row_numbers_trim as a copy of row_numbers, and then remove an element from row_numbers_trim.

// position being removed
int counter = 0;
 // copy original vector
row_numbers_trim = row_numbers;
// remove the first element from the copy
row_numbers_trim(row_numbers_trim.begin()+counter);

All you would have to do here is to increment counter in a loop.

Does this make sense or is there a better way?

LMHmedchem

[laserlight]

Do you really need a vector? These operations (lots of deletions and insertions in the middle) sound more appropriate for a linked list.

[monarch_dodra]

Do you really need a vector? These operations (lots of deletions and insertions in the middle) sound more appropriate for a linked list.

Well, depending on how you look at it, he's only *swapping* items in and out, but never actually doing insertions or deletions. Given OP (seems) to be working with trivial ints, then sticking with vector seems like a good choice.

That said, doing it with lists and splicing was indeed the first thing I thought about doing. Doing it like that right of the bat might be smarter too, if you expect actual insertions/deletions later down the line.

[superbonzo]

Does this make sense or is there a better way?

if you don't need memory contiguity then you can use a non-owning view instead ( take alook at boost filter iterator, for example; this has the bonus of generalizing to any filtering predicate ); alternatively, if you need memory contiguity and/or a range of vector<> iterators, something like:

// given a (non empty) vector row_numbers, and a function useful_stuff( row_numbers.begin(), row_numbers.end() )

std::for_each( row_numbers.begin() + 1, row_numbers.end(), [&]( int& i )
	{
		swap( row_numbers.front(), i );
		useful_stuff( row_numbers.begin() + 1, row_numbers.end() );
	} );

[2kaud]

I want to sequentially remove one element at a time starting with the first. When the second element is removed, the first element needs to go back in.

Why? What are you trying to really achieve?

[monarch_dodra]

Why? What are you trying to really achieve?

I think he wants to process sequence of partial permutations?

[LMHmedchem]

Hello and thank you for the responses,

I have set up some code to evaluate a data table by taking the determinant of the square matrix. This is the determinant of the product matrix of the original data table multiplied by its transpose. Theoretically this is a metric of the amount of information contained in the original data table. I need a way to vary the data that is being analyzed, meaning to take the determinant of sub-sets of the original data table. My data is stored in a vector of column objects with one object for each column in my input file. Each object has a vector for the column data and several variables giving the column header, data type, etc. If I want to access the column data using the header name I store the objects in a map instead of a vector with the column header as the index.

I need to be able to extract subsets of rows from the input data to process with the matrix determinant code. The way I set it up, I pass the determinant function a vector giving the row id numbers of the rows I want processed. This is the row_numbers vector I mentioned. There is a for loop that loops through the row_numbers vector and loads the indicated rows into a matrix of the proper size. (for this data there are 43 columns)

For the example row_numbers{1,2,3,4,5,6,7,8,9}, a 9x43 matrix would be declared and populated with the data for rows 1-9.

The code looks like,

//declarations
unsigned int i,j ; // loop iterators
unsigned int current_number_of_rows = 0; // number of rows in passed vector
unsigned int matrix_column_number = 0;
unsigned int row_id_number = 0;
double current_cell_value;

// matrix for input PCA data and product
MatrixXd PCA_values, product_matrix;

// set row dimension to number of rows passed in call
current_number_of_rows = row_numbers.size();

// size matricies based on ammount of data passed
PCA_values.resize(current_number_of_rows, num_data_columns);
product_matrix.resize(num_data_columns, num_data_columns);

// loop through all data input columns, start with first_input_column
// columns before first_input_column contain documentation data
for(i=first_input_column; i<num_input_columns; i++){

   // loop on all data rows for this column
   for(j=0; j<current_number_of_rows; j++){
      // extract current row number from passed vector
      row_id_number = row_numbers[j];
      // row id numbers run from 1-n, vector runs from 0-n, this is a correction
      row_id_number = row_id_number -1;
      // get cell value for that row number
      current_cell_value = columns[i].double_data[row_id_number];
      // assign to matrix
      PCA_values(j, matrix_column_number) = current_cell_value;
   }

   // increment to next column
   matrix_column_number++;
}

To process a specific sub-set of the original data, I just need to load the row numbers into row_numbers. One of the algorithms I want to process is to leave out one row at a time and record the effect on the determinant. In theory, if the determinant does not decrease when a row is removed, the row is providing redundant data. It's not that simple, but I need to get this running to investigate further. I'm sure there are allot of reasonable mechanisms for modifying the contents of the PCA_values matrix, so any suggestions would be appreciated.

The matrix stuff is done with the Eigen library in case that matters.

LMHmedchem

[monarch_dodra]

To process a specific sub-set of the original data, I just need to load the row numbers into row_numbers. One of the algorithms I want to process is to leave out one row at a time and record the effect on the determinant. In theory, if the determinant does not decrease when a row is removed, the row is providing redundant data. It's not that simple, but I need to get this running to investigate further. I'm sure there are allot of reasonable mechanisms for modifying the contents of the PCA_values matrix, so any suggestions would be appreciated.

The matrix stuff is done with the Eigen library in case that matters.

LMHmedchem

I'm a bit rusty on my linear algebra, but it seems you are basically just trying to find the basis of your matrix? Aren't there known algorithms that do that already?

[LMHmedchem]

I'm a bit rusty on my linear algebra, but it seems you are basically just trying to find the basis of your matrix? Aren't there known algorithms that do that already?

This is an optimization process that is an application of experimental design theory (D-optimality). The object here is to examine rows of data and find the minimal set of rows with maximal numerical information. In other words, we are looking for rows whose data is redundant to the overall data. The D-optimal method uses the determinant of the square matrix as it's metric of optimality. The larger the determinant the better.

I am working from some papers but there are aspects of the algorithm that are not entirely clear the way it was written up. I am cross checking references and trying to get a better understanding of the method. The goal of maximizing the X'X determinant is straight forward, but the best method for systematically examining various combinations of rows is generally just described as "iterative". Something like all possible subsets is not possible given the quantity of data, so I am looking at various stepwise methods. There are MATLAB modules that do this kind of thing, but I often find that the implementation is not really what I need and so it is better to write it myself if I can unwind the algorithm.

Right now I am just trying to get it to work well enough to evaluate if I am getting interesting results.

LMHmedchem