0

Consider a table of m columns where columns represents some smooth functions with potentially some minor noise. Each function is given for the same set of argument values. However, the rows in the table are ordered from smallest values to largest as opposed to each smooth function being in its separate column. For example, if the 2 unscrambled series (for x values 0, 1, 2, 3) are

series1 series2
      0       3
      1       2
      2       1
      3       0

The data is instead incorrectly stored as

column1 column2
      0       3
      1       2
      1       2
      0       3

We want to reorder values in some rows so that each function is as smooth as possible (its derivative changes little). Values in the first 3 rows are in the correct order. While this is possible to develop an algorithm for this task that would take each row in turn and permute the order of values in that row to find the order resulting in the smallest sum of derivative differences, that might require to consider m! possibilities. I was wondering if there might be an existing solution? What if instead of 1D series of one variable x, I have surfaces in 2D space?

1
  • 2
    Wouldn't it be easier/better to fix whatever is writing the data out and avoid the problem? Sep 1, 2019 at 5:20

1 Answer 1

1

It seems for each row, there is an linear assignment problem to solve, where the cost matrix is given by the difference of the values to the ones from the previous row. Wikipedia gives some pointers to different algorithms. There are free libraries for solving such kind of problems available, for example, Google's OR tools.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.