Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Minimal number of transformations

• To: mathgroup at smc.vnet.net
• Subject: [mg103144] Minimal number of transformations
• From: Maxim <musimba at gmail.com>
• Date: Wed, 9 Sep 2009 04:43:26 -0400 (EDT)

Hello everyone,

Is there any Mathematica function that can calculate the minimal
number of transofrmations needed to go from one list to another.

For instance:

To go from
before = { {1, 2, 3}, {4, 5, 6} }
to
after = { {6, 1, 2, 3}, {4, 5} }
one transformation is needed: moving of the number 6 from second inner
list to the first.

The lists have some specific properties:

1. List Depth is always 3
2. Numbers in the lists are always unique and are sequential numbers:
1, 2, 3, ...
3. Flatten[Length[before]] == Flatten[Length[after]], which means
numbers are never removed or added from/to the list.

This is somewhat similat to EditDistance, except that it should work
on list of lists and it should be able to count element moves, rather
than substitutions.

Thanks!

• Follow-Ups:
  • Re: Re[2]: Minimal number of transformations
    • From: Leonid Shifrin <lshifr@gmail.com>
  • Re: Minimal number of transformations
    • From: Leonid Shifrin <lshifr@gmail.com>