Results 1 to 2 of 2

Thread: Calculate smallest number of adjustments to get columns in correct order
Thanks Thanks: 0 Likes Likes: 0

  1. #1
    Board Regular
    Join Date
    Feb 2002
    Location
    North Yorkshire, UK
    Posts
    263
    Post Thanks / Like
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Default Calculate smallest number of adjustments to get columns in correct order

    This is possibly more of a maths question than an Excel question, but I thought it was the sort of thing that someone on here may be able to answer...

    Say that I have a data extract from one system, and I need to change the order of the columns so that they eventually end up in the same order as an extract from another system.

    Consider the following table:
    A2 B2 C2 D2 E2 F2 G2 H2 I2 J2 K2 L2 M2 N2 O2 P2 Q2 R2 S2 T2 U2
    6 37 35 7 8 9 12 10 11 54 14 16 18 19 17 34 53 27 28 13 4

    I need to manually move the columns so that the numeric values are in order (but not yet in the actual correct final column). For example, if I were to cut Column U and insert at Column A, and then cut Columns E:G and insert at Column C, that would change the layout so that the first 5 columns are not in the correct order, but still with some more cuts and inserts to do to finish the process:
    A2 B2 C2 D2 E2 F2 G2 H2 I2 J2 K2 L2 M2 N2 O2 P2 Q2 R2 S2 T2 U2
    4 6 7 8 9 37 35 12 10 11 54 14 16 18 19 17 34 53 27 28 13

    I need to figure out the minimum number of cuts and inserts required to move the columns to ascending order.

    I know that in actual Excel terms, I could do this easily by sorting and choosing "left to right" instead of the default "top to bottom", but the actual data I'm working with doesn't contain the numeric column values, so it's more of a maths theory question "What is the minimum number of "moves" required to put these items in order"?

    Think of it in terms of books on a bookshelf that that have been mixed up, what's the minimum number of moves required to put them back in alphabetical order? The best I've done for this original order is 8 moves, which I've accomplished a number of different ways.

    Is there some rule or formula that can calculate the minimum number of moves for this, or any given "order" of books?

    [edit] I forgot to clarify that you don't have to move one "book" at a time. You can move any number of adjacent books and it counts as 1 move as in the example above where I cut columns E:G.
    Last edited by JugglerJAF; Feb 15th, 2019 at 10:06 AM. Reason: clarification
    It's curtains for your Dr. Horrible ... lacy, gently wafting curtains.

  2. #2
    MrExcel MVP Eric W's Avatar
    Join Date
    Aug 2015
    Location
    Bountiful, UT
    Posts
    8,661
    Post Thanks / Like
    Mentioned
    42 Post(s)
    Tagged
    5 Thread(s)

    Default Re: Calculate smallest number of adjustments to get columns in correct order

    This may help:

    https://cs.stackexchange.com/questio...ay-from-1-to-n

    I think your last addendum makes a difference. If you have {3,4,1,2} you could sort that in one move ({1,2} in front of 3), while that link suggests 4-2 = 2 moves. I'd guess you could treat each sorted subrange as a unit, which would decrease the value of n, then that link implies that the answer would be n-1.
    Cheers,
    Eric

    When you eliminate the impossible, whatever remains, however improbable, must be the truth.

    -Posting guidelines, forum rules, terms of use, FAQs, BB codes, See how to search the forum
    -Post a screen shot with the HTML Maker

Some videos you may like

User Tag List

Tags for this Thread

Like this thread? Share it with others

Like this thread? Share it with others

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •