Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Next permutation

by aartist (Pilgrim)
on Feb 25, 2019 at 18:15 UTC ( [id://1230512]=perlquestion: print w/replies, xml ) Need Help??

aartist has asked for the wisdom of the Perl Monks concerning the following question:

Hi

How do you get next permutation from sequence of numbers ? For example : for 117 -> 171.

Replies are listed 'Best First'.
Re: Next permutation
by LanX (Saint) on Feb 25, 2019 at 18:25 UTC
    You can use Algorithm::Permute for that.

    You'll need to split the ciphers into a list and join them again.

    There is more to say about it ... but your question is too sparse to go into details of non-repeating and non-module implementation...

    Cheers Rolf
    (addicted to the Perl Programming Language :)
    Wikisyntax for the Monastery FootballPerl is like chess, only without the dice

      Thanks for the answer. I am looking for non-modules solution. I don't want to find all the solution. I just want to find next number in sequence. We should be able to derive from current number. Foe example : ( swap till you hit the largest number as first. If you hit the largest number as first, get the next number on left side and then place remaining number in sorted order ) : 117 => 171 => 711 or : 1234 =>(swap) 12.43 =>(largest 4) : 13.24 =>(swap) 13.42 => (largest) 14.23 =>(swap) :14.32 etc..

        How is what you want to do different than a Bubble Sort where you stop on the first swap? A bubble sort moves the highest element up by one position for each pass (here a digit). What do you want to happen if the highest number is already first in the order?

        Update:
        Probably a better way to get the index of max value...But is this what you want?
        Code should run fairly quickly albeit a bit wordy for Perl.

        #!/usr/bin/perl use strict; use warnings; my @array = split '', "117"; print @array, "\n"; print @array,"\n" while rot_max_left(\@array); @array = split '', "1234"; print "\n",@array,"\n"; print @array,"\n" while rot_max_left(\@array); sub rot_max_left { my $array_ref = shift; my $maxi=0; return 0 unless ($maxi = get_index_of_max($array_ref)); ($array_ref->[$maxi-1],$array_ref->[$maxi]) = ($array_ref->[$maxi] +,$array_ref->[$maxi-1]); return $maxi; } sub get_index_of_max { my $array_ref = shift; my $maxi = 0; foreach (my $i=1;$i<@$array_ref;$i++) { $maxi = $i if ($array_ref->[$i] > $array_ref->[$maxi]) } return $maxi; } __END__ 117 171 711 1234 1243 1423 4123
        Your requirements are cryptic for me.

        Please note that you can easily implement any "swap" with array slices, like

        @a[0,1]=@a[1,0]

        and @a=split//,$number

        will initialize it.

        Now you know everything needed to implement your ideas.

        HTH! :)

        Cheers Rolf
        (addicted to the Perl Programming Language :)
        Wikisyntax for the Monastery FootballPerl is like chess, only without the dice

Re: Next permutation
by tybalt89 (Monsignor) on Feb 25, 2019 at 19:28 UTC

    Just one simple? regex :)

    #!/usr/bin/perl # https://perlmonks.org/?node_id=1230512 use strict; use warnings; $_ = 117; print "start at $_\n"; s/.*\K # find the last (.) # digit such that (.*) # there is a later (latest) (.)(??{$1 >= $3 and 'x'}) # digit greater than it (.*) # and get rest # swap those two digits ( $1 & $3 ) # then reverse everything after the first swapped digit / $3 . reverse $2.$1.$4 /xe; print " next is $_\n";

    Outputs:

    start at 117 next is 171
Re: Next permutation
by pryrt (Abbot) on Feb 25, 2019 at 18:25 UTC

    You can use a module like Algorithm::Permute or Math::Combinatorics.

    Or you could write the loops yourself. But really, unless it's for the learning exercise, it's probably not worth it. And if it were for the learning exercise, then you wouldn't be asking us to write the code for you, so I doubt it is.

    If I am wrong about that, you should try to read the source code for one or both of those CPAN modules, and see how they do it, and try to code up your own (simplfied) version that uses the bare algorithm. Or you could make an attempt to at least describe the algorithm you'd use to permute by hand, and we could point you to the Perl functions and other constructs which might help you with implementing the algorithm in Perl.

    But learning how to use the CPAN modules is a worthwhile learning exercise, in and of itself; so even if you do want to manually implement it, try it with one or both of those modules.

Re: Next permutation
by Marshall (Canon) on Feb 25, 2019 at 19:02 UTC
    The Perl built in glob function can do permutations. Here are some examples:
    In a permutation, order matters, in a combination, order doesn't matter.
    #!/usr/bin/perl use strict; use warnings; my @permutations = glob "{1,2,3}" x 3; print "@permutations\n"; @permutations = glob "{1,1,7}" x 3; print "@permutations\n"; @permutations = glob "{a,b,c}{1,2}"; print "@permutations\n"; __END__ extra new lines added for readability Example1: 111 112 113 121 122 123 131 132 133 211 212 213 221 222 223 231 232 233 311 312 313 321 322 323 331 332 333 Example2: 111 111 117 111 111 117 171 171 177 111 111 117 111 111 117 171 171 177 711 711 717 711 711 717 771 771 777 Example:3 combinations "one from column A", one from column "B". a1 a2 b1 b2 c1 c2
      That is called a cross product :-)

      It doesn't give the permutation ( 3 * 2 * 1 = 3! ) (The permutation of 3 objects gives 6 tuples. The cross product gives 3 * 3 * 3 = 27 tuples).

        Ok. well anyway the OP divulged some more info about the his requirements at Re^2: Next permutation and I wrote some code in response to that. The OP wants some enhancements and I've asked the OP to give it a stab on his own. Let's see how that goes......
Re: Next permutation
by bliako (Monsignor) on Feb 25, 2019 at 18:29 UTC
    # by bliako for https://perlmonks.org/?node_id=1230512 use strict; use warnings; use Algorithm::Combinatorics qw/permutations/; die "Usage : $0 number" unless scalar @ARGV; my @digits = split //, $ARGV[0]; my $iter = permutations(\@digits); print "$0 : permutations for $ARGV[0]:\n"; while (my $p = $iter->next) { print " ".join(",", @$p)."\n"; }

    bw, bliako

      I'm aware that this may be someone's homework, but that may be a good reason to try to make it interesting for all parties. I made life-long friends in combo, what Dr. Jay Goldman at UMN called "fancy counting." He was proud that he had never compiled a computer program. I would have gotten twenty bucks if I could have gotten him to compile:

      ./1.permute.pl : permutations for 851: 8,5,1 8,1,5 5,8,1 5,1,8 1,8,5 1,5,8 $ cat 1.permute.pl #!/usr/bin/perl -w use 5.011; use Algorithm::Combinatorics qw/permutations/; die "Usage : $0 number" unless scalar @ARGV; my @digits = split //, $ARGV[0]; my $iter = permutations( \@digits ); print "$0 : permutations for $ARGV[0]:\n"; while ( my $p = $iter->next ) { print " " . join( ",", @$p ) . "\n"; } $

      I think reasonable people could disagree as to what the "next" permutation is. Is the underlying set the natural numbers? Left to right is big to small? I thought I would take a swing at the next method:

      #!/usr/bin/perl -w
      use 5.011;
      # https://metacpan.org/pod/Algorithm::Combinatorics
      # first method implemented by bliako
      use Algorithm::Combinatorics qw/permutations/;
      
      die "Usage : $0 number" unless scalar @ARGV;
      
      my @digits = split //, $ARGV[0];
      
      my $iter = permutations( \@digits );
      print "$0 : permutations for $ARGV[0]:\n";
      while ( my $p = $iter->next ) {
        print "  " . join( ",", @$p ) . "\n";
      }
      
      # try next method with hungarian symbols
      #
      use utf8;
      my @Erdős = permutations(\@digits);
      say "airdish is";
      say "@Erdős";
      use Data::Dump;
      dd \@Erdős;
      my @descending = sort { $b <=> $a } @Erdős;
      say "descending is";
      dd \@descending;
      $ ./2.permute.pl 372 ./2.permute.pl : permutations for 372: 3,7,2 3,2,7 7,3,2 7,2,3 2,3,7 2,7,3 airdish is ARRAY(0x5621ec17ad00) ARRAY(0x5621ec17ae80) ARRAY(0x5621ec17aec8) ARRA +Y(0x5621ec23e770) ARRAY(0x5621ec2d4d80) ARRAY(0x5621ec2d5158) [[3, 7, 2], [3, 2, 7], [7, 3, 2], [7, 2, 3], [2, 3, 7], [2, 7, 3]] descending is [[2, 7, 3], [2, 3, 7], [7, 2, 3], [7, 3, 2], [3, 2, 7], [3, 7, 2]] $

      Ordering these could turn into a boondoggle pretty quickly. Update: the use of word "method" in this post was technically misleading/misguided, as no objects are created. The word "function" is correct.

        I think reasonable people could disagree as to what the "next" permutation is.

        As seen by this survey of modules: Short survey of modules for combinations and permutations there is indeed disagreement. Lexicographic is the most common. Pari/GP's v2.6 changes include "permtonum/numtoperm now use the standard lexicographic numbering" so we might have some belief that that is a preferred ordering unless there are other requirements (e.g. Gray codes).

        There are lots of possible reasonable orderings, e.g. Jorg Arndt's Algorithms book section 6.1 (Permutations) where numerous methods are shown, or Ruskey and William's Cool-lex ordering from 2009 -- noted earlier in Knuth's Volume 4 Fascicle 3 (2005).

        I don't think most reasonable programmers would agree that "implementation defined and unlike every other implementation" is a good ordering. A number of modules on that list chose that so I guess there is disagreement. Some, like Math::Combinatorics, will give you a different ordering every run.

Re: Next permutation
by BillKSmith (Monsignor) on Feb 25, 2019 at 22:54 UTC
    The book "HIGHER ORDER PERL" ISBN 1558607013 has a chapter on iterators. The examples include several iterators for permutations. One of them will probably meet your requirements. Even if not, you will learn the advantage of an iterator, and how to write your own.
    Bill
Re: Next permutation (lexicographical)
by LanX (Saint) on Feb 26, 2019 at 00:25 UTC

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://1230512]
Approved by stevieb
Front-paged by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others goofing around in the Monastery: (6)
As of 2024-04-22 20:05 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found