CODEWITHSUNDEEP
listoptimizationdata-structurestree
aterpin
aterpin

Reputation: 110

Efficient data structure to perform bulk reverse, bulk swap and random access

Problem

I am looking for an efficient data structure to perform bulk reverse, bulk swap and random access. The number of elements is constant.

To better explain what I'm looking for, I will introduce a bespoke problem:

We have K vessels, labeled 1, 2, .., K. It is given an initial permutation of this vessels, and it is required to perform some changes on this permutation, i.e.: a set (block) of vessels can be swapped with another block, a set can be reversed and at any time should be possible to answer what is the vessel in position i.

A better explanation may be provided through examples:

Initial permutation: (3 4 1 2 7 6 5)

Swap the block (4 1) with (2 7): (3 2 7 4 1 6 5)

Reverse the block (7 4 1): (3 2 1 4 7 6 5)

Get vessel in position (1-based) 3: 1

Please note also that all this should be circular, e.g:

Swap the block (5 3) with (2 1): (1 5 3 4 7 6 2)

While in the examples I provided a block is identified by its label, please consider that each block is actually identified by the starting position and the end position:

Given the permutation (1 5 3 4 7 6 2) the block (3 4 7) is identified by the indices (1-based) {3, 5}.

I used the labels with the hope of a clearer understanding of the kind of moves.

I won't give any assumptions or limitations to the number of vessels and operations, but there are two main situations that can be faced:

  1. Lot of random access needed, only one every set of accesses a bulk swap and a bulk reverse
  2. Lot of random access and potentially a bulk swap and reverse each access

Some ideas

An idea to tackle this problem could be to use a treap to perform log(n) swap, lazy propagation bulk reversion and access. Of course there are some issues to keep the tree balanced, but they can be solved.

Another approach could be to use a double linked list to perform constant swap and constant reverse operation, but is this possible?

Under the assumption that all the queries are on sequential locations, or that is possible to use extra memory to store pointers or similar to provide random access also in list-like data structures, is in some way possible to provide constant time swap and constant time reversion?

With the hope of finding better ad hoc solutions:

Suppose that each move is structured as follow:

  1. Take two intervals (adjacent, e.g. from (1 2 3 4 5) take (1 2) and (3 4))
  2. Eventually swap the two
  3. Eventually reverse one or both, but no overlapping! (e.g. swap (1 2), but not (2 3) or (5 1) which is not one of the selected intervals)
  4. Repeat 1

The possible moves are:

  1. Swap the two intervals
  2. Reverse the two intervals but no swap
  3. Swap the two intervals and reverse only one

Upvotes: 1

Views: 133

Answers (1)

kur ag
kur ag

Reputation: 593

If I understand correctly, you will write a program to solve TSP with 3-opt similar heuristic. This article can be your start point http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.570&rep=rep1&type=pdf.

This topic is very broad. You need to the literature search.

Upvotes: 1

Related Questions