Re[4]: Minimal number of transformations
- To: mathgroup at smc.vnet.net
- Subject: [mg103251] Re[4]: [mg103144] Minimal number of transformations
- From: Maxim Volkov <musimba at gmail.com>
- Date: Fri, 11 Sep 2009 05:29:32 -0400 (EDT)
- References: <200909090843.EAA05869@smc.vnet.net> <34c814850909091040x194eaa68ld60f646d3ee5cb53@mail.gmail.com> <1987744366.20090910134505@gmail.com> <34c814850909100414j2bacb148l17df9e54c4a65b37@mail.gmail.com>
- Reply-to: Maxim Volkov <Musimba at gmail.com>
Hi Leonid,
Correct. Two types of transofrmations. Let's call them inter-list
transformations and intra-list transformation for transformations
between sublists and for a transformation within one sublist
correspondingly.
The difficult part is intra-list transformations.
Here's a piece of code which makes a random intra-transformation:
randomTransoformation[l_] :=
Module[
{len, el},
len = Length[l];
Insert[Delete[l, #], l[[#]], RandomInteger[{1, len}]] &@
RandomInteger[{1, len}]]
It extracts one element from some position and then inserts the same
element into another position. In this case {a,b,c}->>{b,c,a} is one
transfotrmation (extract 'a' from the first position and insert it to
the last). So, to use combinatorics terms, this transoformation is not
a transposition, rather it is a cycle with some specific properties.
Regards,
Maxim
> Hi Maxim,
> In this case, I think you should be even more specific. I can see two typ=
es of
> transformations: to move an element from one sublist to another one, and =
to
> move some element within the same sublist. Are both of these counted?
> For example
{{a,b},{c,d}}->> {{a,c,b},{d}} should then be what - 2? (one step to move c=
to the
> first sublist, then another one to move c within the first sublist). Also=
, you should
> specify the rules - how elements are moved from one sublist to another - =
for
> example they are always appended in front of a sublist.
> Also, for moving elements within a sublist: you say that {a,b,c}->{b,c,a}=
is one
> transformation. I can see two transpositions a<->b and then a<->c, or a s=
ingle syclic shift.
> You must provide a fixed notion of transformation here, for example a sin=
gle two-element
> transposition of adjacent (or not necessarily adjacent) elements. If you =
count transposition
> of any two elements (not necessarily adjacent) as a single transformation=
, then indeed
{a,b,c}->>{b,c,a} is one. But you have to state all these rules, otherwise =
the problem is IMO
> not well defined.
> Regards,
> Leonid
> On Thu, Sep 10, 2009 at 1:45 PM, Maxim Volkov <musimba at gmail.com> wrote:
> Hi Leonid,
> Thanks for the answer. But I think I haven't made myself clear. Not
> only the order of sublists is important, but so is the order of
> elements in the sublists.
> ex.: {{a, b, c}} != {{b, c, a}}
> So the most difficult part here is to find minimal number of inner
> list transformations. In case of the above example it is one
> transformation:
> a is moved from the first position to the last.
>> Hi Maxim,
>> assuming that the order of sublists matters ( that is, that lists
>> {{1,2},{3,4}} and {{3,4},{1,2}} are
>> considered different), that the order of elements inside sublists
>> does not matter (that is, {{1,2},{3,4}} and {{2,1},{4,3}} are
>> considered the same), and that both lists contain the same set of
>> distinct elements, we just need to count the number of elements that
>> must be taken from one of the sublists and
>> placed to some other one. The following code will hopefully do this:
>> ClearAll[transformDistance, listOfDistinctQ, sublist, transforms];
>> Protect[sublist];
>> listOfDistinctQ[x : {{__} ..}] :=
>> Length[Flatten[x]] == Length[Union[Flatten[x]]];
>> listOfDistinctQ[___] := False;
>> transforms[start_?listOfDistinctQ, end_?listOfDistinctQ] /;
>> Length[start] == Length[end] &&
>> Union[Flatten[start]] === Union[Flatten[end]] :=
>> Rule @@@ DeleteCases[
>> SplitBy[
>> #[[Ordering[#[[All, 1]]]]] &@
>> Flatten[
>> Map[MapIndexed[Thread[{#1, sublist @@ #2}] &, #] &,
>> {start, end}],
>> 2],
>> First], {x_, x_}];
>> transformDistance[start_, end_] := Length[transforms[start, end]];
>> The function <transforms> returns a list of transformation steps that le=
ad from start list to
>> end list. The function transformDistance gives the number of transforms=
, which is just the
>> length of the list of rules returned by <transforms>. The head <sublist>=
is introduced simply
>> for better visualization.
>>
>> Examples:
>> In[1] =
>> ClearAll[a,b,c,d,e,f,];
>> In[2] =
>> transforms[{{a, b, c}, {d, e, f}}, {{a, b, c, d}, {e, f}}]
>> Out[2] = {{d, sublist[2]} -> {d, sublist[1]}}
>> In[3] = transforms[{{a, b}, {c, d}, {e, f}}, {{c, b, a}, {e}, {d, f}}]
>> Out[3] = {{c, sublist[2]} -> {c, sublist[1]}, {d, sublist[2]} -> {d,
>> sublist[3]}, {e, sublist[3]} -> {e, sublist[2]}}
>> In[4] = transforms[{{a, b}, {c, d}, {e, f}}, {{c, d}, {e, f}, {a, b}}]
>> Out[4] = {{a, sublist[1]} -> {a, sublist[3]}, {b, sublist[1]} -> {b,
>> sublist[3]}, {c, sublist[2]} -> {c, sublist[1]}, {d,
>> sublist[2]} -> {d, sublist[1]}, {e, sublist[3]} -> {e,
>> sublist[2]}, {f, sublist[3]} -> {f, sublist[2]}}
>> Hope this helps.
>> Regards,
>> Leonid
>> On Wed, Sep 9, 2009 at 12:43 PM, Maxim <musimba at gmail.com> wrote:
>> 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!
- References:
- Minimal number of transformations
- From: Maxim <musimba@gmail.com>
- Minimal number of transformations