#24 multiply permutations, invert

open
nobody
None
5
2014-05-26
2014-05-25
dan hayes
No

Where is the function for multiplying permutations? For example in Macsyma it is permult(...) or for inverting a permutation which in Macsyma is INVERT_PERMUTATION(..) But neither of these works in maxima. So is there any commands or even some contributed files somewhere that are not a part of regular maxima as i know there are quite a few of these but finding them is quite a challenge in the directory structure. I know one could painstakingly create permutation matrices (seems also NO direct command for doing this either) and multiply but then one has also to go to the pain of making them all the same size etc.

Related

Support Requests: #24

Discussion

  • I don't have a copy of Macsyma. If you show us an example of how permult and INVERT_PERMUTAION work, we can create similar funcitons. For example, will this be enough?

    (%i4) permult(p1,p2):= block([p3:[]], for i in p2 do p3:endcons(part(p1,i),p3),p3)$
    
    (%i5) permult([5,4,3,2,1],[2,4,1,3,5]);
    (%o5)                     [4, 2, 5, 3, 1]
    
     
    Last edit: Jaime E. Villate 2014-05-25
    • dan hayes
      dan hayes
      2014-05-26

      Yes the second way as two lists and applying the rightmost, last argument , permutation first as it seems you did there. The understanding would be that also the lists would not necessarily have to have the same length and could skip numbers though repeated numbers could signal error message. Whatever numbers are in the list it would understood to be the 2nd line of the usual 2 line representation of a permutation with the first line assumed being the same numbers in the list but in increasing order from left to right such as setify(list) would do - any numbers skipped or not present would be assumed to be the identity in those numbers. For example if a list had only one number it would automatically be the identity. For example if had a list as [5,9] would also be the identity but [9,5] would mean 9 takes the place of 5, 5 takes place of 9 - or just the transposition of those two numbers - identity in all others or in cycle notation [9,5] which is also
      of course the same as [5,9] in cycle notation. It could also take any number of lists the order being applied from right to left in the multi product.

      Also see Macsyma under permutations as i think u have access to that. I will put some i copied from that:

      PERMUTATION_DECOMP(permlist)

      Decomposes permutation permlist into a product of cycles.  The permutation provided as input is represented as a list of all the
      integers from 1 through N.  As input, the list [I1,I2,...,In] represents the permutation 1->I1, 2->I2, ..., n->In.  The output is a
      list of lists, where each of the inner lists is a cycle.  In the output, the list [I1,I2,...,Ik] represents the cycle I1->I2,
      I2->I3,..., Ik->I1.  The cyclic decomposition is in canonical form,with the lowest integer in each cycle in the first position, and the
      cycles ordered by their first elements.

      The following variables are assigned values by PERMUTATION_DECOMP:

      PERMUTATION_INDEX
        Is set equal to the index of the permutation, which is the number of  transpositions in the permutation.

      PERMUTATION_PARITY    is set to EVEN or ODD, if the permutation is even or odd.

      Usage File for Permutation Computations in Macsyma
              --------------------------------------------------
      Notation


      A permutation is represented as a list of all the integers from 1 through N.  The list [I1,I2,...,In] represents the permutation
      1->I1, 2->I2, ..., n->In.

      A cyclic permutation is represented as a list [I1,I2,...,Ik],which represents the cycle I1->I2, I2->I3,...,Ik->I1 .

      Functions

      APPLY_PERMUTATION(permlist, list1) - Applies the permutation reepresented by the list permlist to the list list1. 

      PERMUTATION_DECOMP(permlist) - Decomposes the permutation represented
      by the list permlist into a product of cycles.

      APPLY_CYCLES(cycleslist, list1) - Applies the permutation represented by the list of cyles cylceslist to the list list1.

      INVERT_PERMUTATION(permlist) - Returns the inverse of the permutation represented by the list permlist.

      PERMULT(permlist1 {,permlist2,...}) - Multiplies the permutations represented by permlist1, permlist2, ... . The permutations are applied
      to a list starting from the right-most one and moving to the left.

      PERMUTATION_DECOMP(permlist) - Decomposes the permutation permlist into a product of cycles.  The cyclic decomposition is in canonical form,
      with the lowest integer in each cycle in the first position, and the cycles ordered by their first elements.

      The following variables are assigned values by PERMUTATION_DECOMP: - PERMUTATION_INDEX is set equal to the index of the permutation, which
         is the number of transpositions in the permutation.

      PERMUTATION_PARITY is set to EVEN or ODD, if the permutation is even
         or odd.

      PERMUTATION_UNDECOMP(cycleslist) - Converts a list of cycles in normal form back to the undecomposed permutation.  This function is the inverse
      of PERMUTATION_DECOMP.

      Option Variables

      PERMUTATION_INDEX - is set by PERMUTATION_DECOMP equal to the index of the permutation, which is the number of transpositions
      in the permutation.

      PERMUTATION_PARITY - is set by PERMUTATION_DECOMP equal to EVEN or ODD, if the permutation is even or odd.

      On Sunday, May 25, 2014 2:51 PM, Jaime E. Villate villate@users.sf.net wrote:

      If you show us an example of how permult and INVERT_PERMUTAION work, we can crate similar funcitons. For example, will this be enough?
      (%i4) permult(p1,p2):= block([p3:[]], for i in p2 do p3:endcons(part(p1,i),p3),p3)$ (%i5) permult([5,4,3,2,1],[2,4,1,3,5]); (%o5) [4, 2, 5, 3, 1]


      [support-requests:#24] multiply permutations, invert
      Status: open
      Group:
      Created: Sun May 25, 2014 06:46 AM UTC by dan hayes
      Last Updated: Sun May 25, 2014 06:46 AM UTC
      Owner: nobody
      Where is the function for multiplying permutations? For example in Macsyma it is permult(...) or for inverting a permutation which in Macsyma is INVERT_PERMUTATION(..) But neither of these works in maxima. So is there any commands or even some contributed files somewhere that are not a part of regular maxima as i know there are quite a few of these but finding them is quite a challenge in the directory structure. I know one could painstakingly create permutation matrices (seems also NO direct command for doing this either) and multiply but then one has also to go to the pain of making them all the same size etc.


      Sent from sourceforge.net because you indicated interest in https://sourceforge.net/p/maxima/support-requests/24/
      To unsubscribe from further messages, please visit https://sourceforge.net/auth/subscriptions/

       

      Related

      Support Requests: #24

      Attachments
      • dan hayes
        dan hayes
        2014-05-26

        Yes i made a mistake by "2nd way" as i see that the first was just the function definition. I have never heard of using the " in " command as you have it here ' for i in ...' and the word

        " in " is not in the maxima index. It's a new one on me. thanks - it will take some doing to do it the flexible way i was thinking. Was just wondering whether there was already a maxima command in lisp or something already. thanks

        On Sunday, May 25, 2014 8:52 PM, dan hayes zmth@users.sf.net wrote:

        Yes the second way as two lists and applying the rightmost, last argument , permutation first as it seems you did there. The understanding would be that also the lists would not necessarily have to have the same length and could skip numbers though repeated numbers could signal error message. Whatever numbers are in the list it would understood to be the 2nd line of the usual 2 line representation of a permutation with the first line assumed being the same numbers in the list but in increasing order from left to right such as setify(list) would do - any numbers skipped or not present would be assumed to be the identity in those numbers. For example if a list had only one number it would automatically be the identity. For example if had a list as [5,9] would also be the identity but [9,5] would mean 9 takes the place of 5, 5 takes place of 9 - or just the transposition of those two numbers - identity in all others or in cycle notation [9,5] which is also
        of course the same as [5,9] in cycle notation. It could also take any number of lists the order being applied from right to left in the multi product.
        Also see Macsyma under permutations as i think u have access to that. I will put some i copied from that:
        PERMUTATION_DECOMP(permlist)
        Decomposes permutation permlist into a product of cycles.  The permutation provided as input is represented as a list of all the
        integers from 1 through N.  As input, the list [I1,I2,...,In] represents the permutation 1->I1, 2->I2, ..., n->In.  The output is a
        list of lists, where each of the inner lists is a cycle.  In the output, the list [I1,I2,...,Ik] represents the cycle I1->I2,
        I2->I3,..., Ik->I1.  The cyclic decomposition is in canonical form,with the lowest integer in each cycle in the first position, and the
        cycles ordered by their first elements.
        The following variables are assigned values by PERMUTATION_DECOMP:
        PERMUTATION_INDEX
          Is set equal to the index of the permutation, which is the number of  transpositions in the permutation.
        PERMUTATION_PARITY    is set to EVEN or ODD, if the permutation is even or odd.
        Usage File for Permutation Computations in Macsyma
                --------------------------------------------------
        Notation


        A permutation is represented as a list of all the integers from 1 through N.  The list [I1,I2,...,In] represents the permutation
        1->I1, 2->I2, ..., n->In.
        A cyclic permutation is represented as a list [I1,I2,...,Ik],which represents the cycle I1->I2, I2->I3,...,Ik->I1 .
        Functions
        APPLY_PERMUTATION(permlist, list1) - Applies the permutation reepresented by the list permlist to the list list1. 
        PERMUTATION_DECOMP(permlist) - Decomposes the permutation represented
        by the list permlist into a product of cycles.
        APPLY_CYCLES(cycleslist, list1) - Applies the permutation represented by the list of cyles cylceslist to the list list1.
        INVERT_PERMUTATION(permlist) - Returns the inverse of the permutation represented by the list permlist.
        PERMULT(permlist1 {,permlist2,...}) - Multiplies the permutations represented by permlist1, permlist2, ... . The permutations are applied
        to a list starting from the right-most one and moving to the left.
        PERMUTATION_DECOMP(permlist) - Decomposes the permutation permlist into a product of cycles.  The cyclic decomposition is in canonical form,
        with the lowest integer in each cycle in the first position, and the cycles ordered by their first elements.
        The following variables are assigned values by PERMUTATION_DECOMP: - PERMUTATION_INDEX is set equal to the index of the permutation, which
           is the number of transpositions in the permutation.
        PERMUTATION_PARITY is set to EVEN or ODD, if the permutation is even
           or odd.
        PERMUTATION_UNDECOMP(cycleslist) - Converts a list of cycles in normal form back to the undecomposed permutation.  This function is the inverse
        of PERMUTATION_DECOMP.
        Option Variables
        PERMUTATION_INDEX - is set by PERMUTATION_DECOMP equal to the index of the permutation, which is the number of transpositions
        in the permutation.
        PERMUTATION_PARITY - is set by PERMUTATION_DECOMP equal to EVEN or ODD, if the permutation is even or odd.
        On Sunday, May 25, 2014 2:51 PM, Jaime E. Villate villate@users.sf.net wrote:
        If you show us an example of how permult and INVERT_PERMUTAION work, we can crate similar funcitons. For example, will this be enough?
        (%i4) permult(p1,p2):= block([p3:[]], for i in p2 do p3:endcons(part(p1,i),p3),p3)$ (%i5) permult([5,4,3,2,1],[2,4,1,3,5]); (%o5) [4, 2, 5, 3, 1]


        [support-requests:#24] multiply permutations, invert
        Status: open
        Group:
        Created: Sun May 25, 2014 06:46 AM UTC by dan hayes
        Last Updated: Sun May 25, 2014 06:46 AM UTC
        Owner: nobody
        Where is the function for multiplying permutations? For example in Macsyma it is permult(...) or for inverting a permutation which in Macsyma is INVERT_PERMUTATION(..) But neither of these works in maxima. So is there any commands or even some contributed files somewhere that are not a part of regular maxima as i know there are quite a few of these but finding them is quite a challenge in the directory structure. I know one could painstakingly create permutation matrices (seems also NO direct command for doing this either) and multiply but then one has also to go to the pain of making them all the same size etc.


        Sent from sourceforge.net because you indicated interest in https://sourceforge.net/p/maxima/support-requests/24/
        To unsubscribe from further messages, please visit https://sourceforge.net/auth/subscriptions/


        [support-requests:#24] multiply permutations, invert
        Status: open
        Group:
        Created: Sun May 25, 2014 06:46 AM UTC by dan hayes
        Last Updated: Sun May 25, 2014 09:41 PM UTC

        Owner: nobody
        Where is the function for multiplying permutations? For example in Macsyma it is permult(...) or for inverting a permutation which in Macsyma is INVERT_PERMUTATION(..) But neither of these works in maxima. So is there any commands or even some contributed files somewhere that are not a part of regular maxima as i know there are quite a few of these but finding them is quite a challenge in the directory structure. I know one could painstakingly create permutation matrices (seems also NO direct command for doing this either) and multiply but then one has also to go to the pain of making them all the same size etc.


        Sent from sourceforge.net because you indicated interest in https://sourceforge.net/p/maxima/support-requests/24/
        To unsubscribe from further messages, please visit https://sourceforge.net/auth/subscriptions/

         

        Related

        Support Requests: #24

        Attachments
  • Also:
    invert_permutation(p):= block([pi:copylist(p)], for i:1 thru length(p) do pi[p[i]]:i,pi)$

    A more robust version of permult and invert_permutation should check that the permutations have the same length and their elements are all different integers from 1 to the length of them.

     
  • I found a copy of the Macsyma manual and in a few days I will make a more complete proposal to reproduce Macsyma's functions for permutations (in the list and not here).
    Regarding "in", I think the documentation is clear. If you type "? for" it tells you that you should read the section for "do" and if you type "? do" it tells you "One other form of the 'do' is available in Maxima. The syntax is:

    for <variable> in <list> <end_tests> do <body>"
    

    and it gives some examples.