Switch indexes, create the next highest number using the same exact 9 digits presented

by

Here’s a more efficient approach, using the algorithm of the 14th century Indian mathematician Narayana Pandita, which can be found in the Wikipedia article on Permutation. This ancient algorithm is still one of the fastest known ways to generate permutations in order, and it is quite robust, in that it properly handles permutations that contain repeated elements.

The code below includes a simple test() function that generates all permutations of an ordered numeric string.

#! /usr/bin/env python

''' Find the next permutation in lexicographic order after a given permutation

    This algorithm, due to Narayana Pandita, is from
    https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

    1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists, 
    the permutation is the last permutation.
    2. Find the largest index k greater than j such that a[j] < a[k].
    3. Swap the value of a[j] with that of a[k].
    4. Reverse the sequence from a[j + 1] up to and including the final element a[n].

    Implemented in Python by PM 2Ring 2015.07.28
'''

import sys

def next_perm(a):
    ''' Advance permutation a to the next one in lexicographic order '''
    n = len(a) - 1
    #1. Find the largest index j such that a[j] < a[j + 1]
    for j in range(n-1, -1, -1):
        if a[j] < a[j + 1]:
            break
    else:
        #This must be the last permutation
        return False

    #2. Find the largest index k greater than j such that a[j] < a[k]
    v = a[j]
    for k in range(n, j, -1):
        if v < a[k]:
            break

    #3. Swap the value of a[j] with that of a[k].
    a[j], a[k] = a[k], a[j]

    #4. Reverse the tail of the sequence
    a[j+1:] = a[j+1:][::-1]

    return True


def test(n):
    ''' Print all permutations of an ordered numeric string (1-based) '''
    a = [str(i) for i in range(1, n+1)]
    i = 0
    while True:
        print('%2d: %s' % (i, ''.join(a)))
        i += 1
        if not next_perm(a):
            break


def main():
    s = sys.argv[1] if len(sys.argv) > 1 else '781623954'
    a = list(s)
    next_perm(a)
    print('%s -> %s' % (s, ''.join(a)))


if __name__ == '__main__':
    #test(4)
    main()

More Related Contents:

  1. Can someone explain what all the codes mean? PYTHON [closed]
  2. look through a very large numbers (1.2e+34) in Python
  3. Create a list of names whose height is higher than 160 – Explanation on nested dicts cycling [closed]
  4. Iterate through pairs of items in a Python list [duplicate]
  5. Breaking out of nested loops [duplicate]
  6. raw_input and timeout [duplicate]
  7. Loop backwards using indices in Python?
  8. When to use “while” or “for” in Python
  9. How to add an integer to each element in a list?
  10. Skip multiple iterations in loop
  11. Pythonic way to combine for-loop and if-statement
  12. Assigning values to variables in a list using a loop
  13. python: restarting a loop
  14. Updating value in iterrow for pandas
  15. Python nested looping Idiom
  16. Understanding for loops in Python
  17. How to increment variable names/Is this a bad idea [duplicate]
  18. Why doesn’t assigning to the loop variable modify the original list? How can I assign back to the list in a loop? [duplicate]
  19. Spark iteration time increasing exponentially when using join
  20. Iterating through a JSON object
  21. Why do you have to call .items() when iterating over a dictionary in Python?
  22. Iterating over a 2 dimensional python list [duplicate]
  23. How do I iterate over the tuples of the items of two or more lists in Python? [duplicate]
  24. Modifying a list while iterating when programming with python [duplicate]
  25. Loop through list with both content and index [duplicate]
  26. Assignment Condition in Python While Loop
  27. Is there a reason Python 3 enumerates slower than Python 2?
  28. Count duplicates between 2 lists
  29. Run an infinite loop in the backgroung in Tkinter
  30. Strange result when removing item from a list while iterating over it in Python

Leave a Comment